对线面试官 - HashMap

面试官：HashMap 了解吗？能简单说说它的底层实现吗？

派大星：有过了解，首先对于 HashMap 在 1.7 之前是采用的数组+链表，并且根节点是一个 entry 节点，它的一个内部类。数据插入过程采用的是一个头插法。头插法会在扩容的过程中调用 resize 方法，然后又调用 transfer 方法，把里面的一些 entry 进行了一些 rehash，这个过程可能会造成链表的一个循环死循环，也就是死链。最后一点就是由于它没有加锁，也会导致在多线程并发的情况下是线程不安全的。

派大星：HashMap 在 1.8 之后就进行了升级优化，变成了一个又链表+ 数组+红黑树的一个数据结构，并且把原来的 entry 节点换成了 Node 节点，头插法优化成了尾插法。虽然它的插入方法有所改变但是插入顺序没有发生改变，所以不会出现 1.7 的一个死链。

面试官：不错，上面看你有提到死链的问题，能简单说说 1.7 为什么会有死链的产生吗？

派大星：好的。由于 1.7 之前的数组+链表的数据结构和头插法的原因导致了在并发情况下可能会出现死链的情况。具体的表现形式为：当 HashMap 需要扩容的时候会将旧的 HashMap 的节点依次转移到新的 HashMap 中，假设旧的 HashMap 的链表是 A、B、C，而新的 HashMap 由于采用的是头插法所以最终新的 HashMap 里面的链表顺序为 C、B、A 。如图所示：

在这样的一个背景下，当在多线程并发的情况下，第一步假设线程 T1 和 T2 要对 HashMap 进行一个扩容操作看，此时 T1 和 T2 指向的都是链表的头节点 A，并且 T1 和 T2 的下一个节点(T1.next 和 T2.next)指向的都是 B 节点。当线程 T2 时间片用完进入到休眠状态，而线程 T1 开始执行扩容操作一直到 T1 扩容完成后，线程 T2 才会被唤醒。这个时候最大的问题是线程 T2 的指向还没有变，因为是头插法，所以新的 HashMap 的顺序已经改变了。但对线程 T2 来说它是不知道的。所以它的指向元素没有发生改变。如图：

这个时候线程 T2 如果恢复，死循环就开始了。因为 T1 执行完扩容之后 B 节点的下一个节点是 A，而线程 T2 的指向的首节点是 A，下一个节点是 B。这个顺序与新的 HashMap 节点顺序正好相反。T1 执行完之后的顺序是 B 到 A，而 T2 的顺序是 A 到 B，这样 A 节点和 B 节点就形成了死循环

面试官：针对 HashMap 的死链问题有什么样的解决方案嘛？

派大星：可以升级为 JDK1.8，或者通过以下方式解决。

• 使用线程安全容器 ConcurrentHashMap 替代（推荐使用此方案）。

• 使用线程安全容器 Hashtable 替代（性能低，不建议使用）。

• 使用 synchronized 或 Lock 加锁 HashMap 之后，再进行操作，相当于多线程排队执行（比较麻烦，也不建议使用）。

面试官：JDK1.7 到 1.8HashMap 有什么其它的变化嘛？或者说 JDK1.8 的 HashMap 做了哪些性能优化？

派大星：Hash 算法的优化概括来说

• 就是主要表现在对每个 Hash 值，在它的低 16 位中，让高低 16 位进行了异或运算，让它的低 16 位融合了高低 16 位的特征。从而尽量避免一些可能会出现的 hash 冲突，会导致元素进入数组的同一个位置

• 寻址算法的优化：使用与运算代替了取模，提升性能。

• 同时为了提升链表的优化性能增加了红黑树的数据结构，来提高 HashMap 的综合性能。

简单来说就是 HashMap 在 put、get 的时候进行了 hash 算法的优化，避免了 hash 冲突，同时寻址算法也进行了优化。

面试官：你刚刚提到 JDK1.8 的 HashMap 增加了一个红黑树的数据结构。为什么采用红黑树，而不是其它的数据结构呢？

派大星：以典型的 AVL 树为例，AVL 树是一种高度平衡的二叉树，所以查找效率非常高，但是有就有弊，AVL 树为了维持这种高度的平衡，就要付出很大的代价，就是每次插入、删除都要做调整，比较复杂且耗时，所以综合考虑虽然红黑树读取略逊于 AVL 树，但是维护强于 AVL，空间开销与 AVL 类似，内容极多时略优于 AVL，维护优于 AVL，所以红黑树是有着良好的稳定性和完整的功能综合实力强，在诸如 STL 的场景中需要稳定的表现。

面试官：不错不错。回答的很好。

派大星：嗯呢，具体的关于 HashMap 的其它底层实现原理，比如 HashMap 如何扩容及以上问题的一些细节都可参考之前的文章：

文章地址：

HashMap | 利用白话文讲解其底层知识点_java 编程_派大星_InfoQ写作社区