对线面试官 - 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 | 利用白话文讲解其底层知识点