一文教你如何应对Java面试中HashMap相关的面试题？

欢迎大家来到IT世界,在知识的湖畔探索吧!

欢迎大家来到IT世界,在知识的湖畔探索吧!

HashMap数据结构实现原理作为面试八股文中被面试官提问最高的面试题，咱也不知道面试官为什么就那么爱问，可能是因为涉及到内容比较多，也可能是面试官自己都还没有搞清楚。但不管出于什么原因。咱就是爱总结。下面我们就来介绍一下HashMap中常见的一些面试题。

简单介绍 一下HashMap的数据结构？

  对于数据结构的提问是面试环节中必不可少的点，首先得明确我们是否知道HashMap的数据结构，其次也是对我们算法和数据结构了解程度的掌握，当然这都是笔者瞎想的，面试官当然不会这么专业，考虑到从侧面来旁敲侧击一下。

  首先HashMap的树结构是数组+链表/红黑树(哈希桶)结构。所谓的哈希桶，就是指HashMap中的那个数组结构，每个数组元素被称为桶(bucket)，然后每个桶采用的数据结构是链表还是红黑树则是由数据条件决定。哈希表的大小是确定的，但是可以通过resize操作来实现扩容。

transient Node<K,V>[] table;

欢迎大家来到IT世界,在知识的湖畔探索吧!

  对于HashMap桶结构采用什么样的数据结构来存储数据上面提到需要满足一定的条件，那么这个条件是什么呢？自然就是存储数据的多少了。这个转换操作是从Java8之后开始引入的，在HashMap处理哈希冲突的时候，会将哈希值相同的数据存储到同一个桶bucket中，在早期的版本中，当桶中需要存储多个元素的时候，这些元素就会以链表的形式存储到桶中。但是这样一来，随着哈希冲突增加，桶中的元素过多的时候，就会导致查找数据的时间复杂度变成O(n)，也就是说时间复杂度与链表长度成正比了。

  为了避免这种性能退化，所以从Java8开始，在HashMap中的链表的长度达到了某个阈值之后，就会将链表转换成红黑树，因为红黑树是一种自平衡的查找二叉树，所以在数据查找、插入和删除方面性能较好，处理的时间复杂度为O(logn)，从而显著的提升了HashMap数据结构在哈希冲突较高的情况下的查找性能。

  这里需要注意一下，这里的数据存储结构的变化是针对链表操作的，而不是针对外部的数组结构。这是在面试过程中很多人会被面试官所问住的地方，很多人会认为这里的数据存储结构的变化是针对HashMap整个的数据结构的变化，其实并不是，在数据没有出现哈希冲突的情况下，还是会先往数组中进行存储。

介绍一下HashMap中链表转换为红黑树的条件？

  很多人在被问到这个问题的时候，会不知道如何回答，首先可能是对HashMap的数据存储结构不熟悉，其次就是确实没有研究过链表转换红黑树的条件。其实在上面的介绍中，我们也提到了这个转换条件与存储数据的多少有关。

• 桶元素的数量：当某个桶中的元素个数超过了TREEIFY_THRESHOLD值的时候，默认情况下这个值为8，也就是说桶中的元素超过了8个元素之后那么HashMap就会尝试将链表存储转换为红黑树存储，很多面试官在这里会问到一个问题就是为什么这个容量会被设置为8。为什么不是6或者是12呢？其实这个问题Java官方给出的解释就是经过验证之后觉得8的性能最好，所以就设置为8了，如果硬要给它一个原因的话，那就只能从哈希表这种数据存储的结构上去说了，但是最终得出的结论就是8的性能最好。
• 桶的大小：在HashMap中并不是只要链表容量大于8的时候就会进行转换，我们知道在HashMap的数据存储结构中，会将数据先放入一个数组中，也就是说开始存储数据的时候，如果数据冲突不是特别多的时候，这些数据都会按照顺序存储在这个数组中，因为数组的特点就是存储和查询效率都比较高，可以直接通过定位获取到数据，或者是插入数据。只有当数组的容量超过MIN_TREEIFY_CAPACITY值，默认情况下是64的时候，才会执行链表到红黑树的转换，这是因为，如果过早的进行数据结构的转换，在数据量较小的情况下，并不会体现出数组与红黑树组合的性能优势，反而这种存储效果并不会被数组加链表的方式性能更优。
• 同样的既然有链表转换红黑树，那么自然有红黑树转换为链表的条件。在HashMap通过红黑树存储数据的时候势必会带来树结构维护的高成本，所以在某个条件下红黑树还是会被转换成链表。随着红黑树中的元素减少，当元素数量降低到UNTREEIFY_THRESHOLD值默认是6的时候，HashMap会将红黑树转换为链表，这种方式可以有效的防止红黑树在数据元素较少的时候带来的性能上的损耗，这个时候，就没有桶数据的限制了。

  其实从这里衍生出来的面试题会有很多，如下所示。

• 介绍一下HashMap的put数据的过程？
• 介绍一下HashMap的扩容过程？
• 介绍一下HashMap进行了扩容之后，数据位置会被重新计算么等问题？

  其实这里我们只需要了解两个点就可以轻松回答上面这些问题？第一个点就是清楚HashMap中的数据是怎么样被存储到数组中的？第二个点就是HashMap的扩容是针对数组还是链表、是在什么条件下触发的扩容机制？下面我们就来分析一下这两个问题。

HashMap中的数据是如何进行存储的？

  在往HashMap中存储数据的时候会用到put()函数，并且我们知道HashMap的数据结构是一个KV键值对，在上面的介绍中，我们提到过HashMap得内部存储是依赖一个桶数组，也就是说数组的每个位置被称为一个桶，每个桶就是用来存储这个KV键值对的，在HashMap中，键的存储位置是通过一个哈希函数来进行计算的，然后会将键的哈希值映射到数组的索引位置，如下所示。

欢迎大家来到IT世界,在知识的湖畔探索吧!int index = (n - 1) & hash; // n 是数组的长度，& 操作保证索引在 0 到 n-1 的范围内 

  这里为了避免数组越界，所以将得到的长度减一，保证了的到的索引值会在0到n-1这个数据范围内，其实这个原理很好理解，从数学原理的角度上我们向往五个位置上安排7个人的话为了就可以用所在位置与5整除求余数的方式来进行安排那么势必会有1和2两个位置会有两个人，这里原理也是一样的。

  如果经过了计算之后，发现数组中的对应位置没有元素也就是一个空桶的话那么就会将键值直接进行插入，那么如果该位置已经存在数据的话，那么就要用到链表或者是红黑树来解决哈希冲突问题，这里涉及到一个知识点，就是如果产生了冲突，那么该数组位置存储的是第一个元素的键值还是指向链表的指针？这里留作一个讨论问题，有兴趣的读者可以思考一下，答案也是显而易见的。

  到这里，我们就清楚的知道了HashMap中的元素是如何被存储到其中的，那么我们就清楚了上面提到的第一个问题，就是需要通过一个哈希函数来进行位置的选定，既然知道了这个，那么我们就来说说下一个问题，如何进行扩容。

HashMap的扩容机制？

  根据上面的内容，其实我们也可以知道，经过了哈希函数的计算之后，数组中的元素一定是会被全覆盖的，那么既然是全覆盖不如就直接进行红黑树存储解决冲突就好了为什么还要进行扩容呢？其实这个问题也是面试官经常会问到的问题。在我们设计一个数据存储结构的时候，其设计的初衷就是为了让这个数据结构的性能更强，其实Hash表这种数据结构最大的优势就是可以通过哈希函数直接定位的数据的位置。实现快速精确的查找，如果像是之前说的那样只是存储而不考虑性能那么完全可以将HashMap的数据结构直接改成红黑树不就完了。

  所以这里才需要对HashMap进行扩容，HashMap的扩容是基于如下的条件才触发的。

• 负载因子：在HashMap中有一个负载因子的概念，它的作用就是指定当前元素与数组容量的一个比值，也就是说这个比值越大那么就表示它所能容纳的不产生哈希冲突的元素就越多。在默认情况下这个负载因子为0.75，也就是说当16个数组元素存储到12个的时候，就有可能会引起哈希冲突，导致HashMap的数据存储效率下降，这个时候就需要进行数组扩容了。
• 在HashMap中默认的数组容量是16也就是说当数组中的元素存储达到12个的时候，那么就会引起数组扩容，既然是数组扩容了，那么这个时候因为容量变化了，所以原来的HashMap中的数据元素需要重新计算HashMap值来存储到新的位置中。

  如下所示，是扩容机制触发的条件。

if (size > threshold) { resize(); }

  其中，threshold 是扩容的阈值，它的计算方式为

欢迎大家来到IT世界,在知识的湖畔探索吧!threshold = capacity * load factor

  即当 size 超过 threshold 时，就会触发扩容。

  我们只需要掌握一个核心思想就可以清楚HashMap的扩容机制，扩展数组的大小并将原数组中的所有元素重新计算哈希值并放入新的数组中。也就是说所有存储在原哈希表中的键值对需要重新计算哈希值并放入新数组中。因为数组容量增加了，元素的哈希值在重新计算时会映射到新的桶位置。这意味着元素会按照新的数组长度重新定位，这个过程被称为 rehash。

  这里需要注意，这个时候的扩容并不会涉及到红黑树到链表或者是链表到红黑树的转换，只有当数组长度达到64，链表数据达到8的时候，才会触发数据结构转换。

总结

  了解了上面的原理之后，无论面试官问什么样的问题都可以游刃有余的回答了，例如比较常见的如何计算Hash值、如何扩容、扩容之后红黑树和链表是否发生了变化？如何预先设置HashMap的初始容量？如果存储的数据都是一样的那么如何是否会触发链表转换机制？