关于后端:为什么HashMap会产生死循环

2次阅读

共计 1209 个字符，预计需要花费 4 分钟才能阅读完成。

面试合集：https://gitee.com/mydb/interview

HashMap 死循环是一个比拟常见、比拟经典的问题，在日常的面试中呈现的频率比拟高，所以接下来咱们通过图解的形式，带大家彻底了解死循环的起因。

死循环问题产生在 JDK 1.7 版本中，造成这个问题次要是因为 HashMap 本身的运行机制，加上并发操作，从而导致了死循环。
在 JDK 1.7 中 HashMap 的底层数据实现是数组 + 链表的形式，如下图所示：

而 HashMap 在数据增加时应用的是头插入，如下图所示：

HashMap 失常状况下的扩容实现如下图所示：

旧 HashMap 的节点会顺次转移到新 HashMap 中，旧 HashMap 转移的程序是 A、B、C，而新 HashMap 应用的是头插法，所以最终在新 HashMap 中的程序是 C、B、A，也就是上图展现的那样。有了这些前置常识之后，咱们来看死循环是如何诞生的？

死循环是因为并发 HashMap 扩容导致的，并发扩容的第一步，线程 T1 和线程 T2 要对 HashMap 进行扩容操作，此时 T1 和 T2 指向的是链表的头结点元素 A，而 T1 和 T2 的下一个节点，也就是 T1.next 和 T2.next 指向的是 B 节点，如下图所示：

死循环的第二步操作是，线程 T2 工夫片用完进入休眠状态，而线程 T1 开始执行扩容操作，始终到线程 T1 扩容实现后，线程 T2 才被唤醒，扩容之后的场景如下图所示：

从上图可知线程 T1 执行之后，因为是头插法，所以 HashMap 的程序曾经产生了扭转，但线程 T2 对于产生的所有是不可知的，所以它的指向元素仍然没变，如上图展现的那样，T2 指向的是 A 元素，T2.next 指向的节点是 B 元素。

当线程 T1 执行完，而线程 T2 复原执行时，死循环就建设了，如下图所示：

因为 T1 执行完扩容之后 B 节点的下一个节点是 A，而 T2 线程指向的首节点是 A，第二个节点是 B，这个程序刚好和 T1 扩完容完之后的节点程序是相同的。T1 执行完之后的程序是 B 到 A，而 T2 的程序是 A 到 B，这样 A 节点和 B 节点就造成死循环了 ，这就是 HashMap 死循环导致的起因。

HashMap 死循环的罕用解决方案有以下 3 个：

应用线程平安容器 ConcurrentHashMap 代替（举荐应用此计划）。
应用线程平安容器 Hashtable 代替（性能低，不倡议应用）。
应用 synchronized 或 Lock 加锁 HashMap 之后，再进行操作，相当于多线程排队执行（比拟麻烦，也不倡议应用）。

总结

HashMap 死循环产生在 JDK 1.7 版本中，造成死循环的起因是 HashMap 在 JDK 1.7 应用的是头插法，头插法 + 链表 + 多线程并发 + HashMap 扩容，这几个点加在一起就造成了 HashMap 的死循环，解决死锁能够采纳线程平安容器 ConcurrentHashMap 代替。