jdk1.7 HashMap为什么会出现死循环

JDK 1.7 的HashMap出现死循环的条件JDK 1.7 的HashMap在多线程并发环境下如果同时触发扩容操作就可能会因为其采用的头插法机制而产生一个环形链表导致程序在调用get()等方法时陷入死循环。JDK 1.7的HashMap在设计上并非线程安全其死循环问题主要由以下几个因素共同导致头插法 (Head Insertion)在 JDK 1.7 及更早版本中HashMap解决哈希冲突的链表采用的是头插法即新加入的元素总是被放在链表的头部原有的元素依次后移。并发扩容(Concurrent Resize)当多个线程同时检测到HashMap需要进行扩容Rehash并且它们都开始执行数据迁移操作时就可能出现并发问题。 头插法让链表倒着走头插法是理解整个问题的关键。在正常情况下单线程环境下HashMap扩容时transfer()方法会将旧数组的每个链表迁移到新数组中。由于使用头插法迁移后的新链表顺序与原链表的顺序完全相反即由A-B-C变成了C-B-A。虽然在单线程中这只是改变了顺序但在多线程环境下这种反转的特性会成为问题的导火索。 死循环的形成一场并发的意外以下是造成死循环的典型过程初始状态假设哈希表中的某个位置有一个链表如A - B - C。线程A启动准备扩容线程A在执行扩容的transfer()方法时刚保存了当前节点eA和它的下一个节点nextB此时它被操作系统挂起让出CPU时间片。线程B完成扩容线程B抢到CPU完成了对整个HashMap的扩容。在它迁移链表时因为头插法新链表被反转为了C - B - A。线程A恢复开始迷路这时线程A被唤醒它继续从之前中断的地方执行。但它手中的地图已经过时它的局部变量e仍然指向节点Anext指向节点B。死循环形成线程A接着执行头插法将节点A插入新表此时意外出现了由于线程B已经执行完毕节点B的next指针现在指向了节点A。这让节点A和节点B之间形成了相互指向的环形链表A - B - A - B ...。这个过程就像两个人在同一个地图上规划路线当一个人修改了路线而另一个人不知道仍按照旧路线走时就可能会在原地打转。✅ JDK 1.8 的修复从 JDK 1.8 开始官方通过以下两个改动解决了这个死循环问题头插法改为尾插法这是最根本的改动。迁移时保持链表的原始顺序从A-B-C迁移后依然是A-B-C从根本上杜绝了链表顺序反转避免了环形链表的形成。引入红黑树优化当链表长度超过阈值默认8且数组长度超过64时链表会转换为红黑树优化了极端情况下的查找性能。 解决方案虽然JDK 1.8解决了死循环问题但HashMap在多线程下仍可能出现数据丢失等问题。因此正确的多线程实践应遵循首选ConcurrentHashMap最推荐的解决方案。它是专为并发设计的线程安全哈希表采用分段锁或CAS等更高效的机制性能远超Hashtable。避免使用Hashtable它虽线程安全但使用全局锁在多线程下性能很差。使用同步锁通过Collections.synchronizedMap()包装或在外部用synchronized进行同步但会降低并发性能。成环的详细步骤用流程图的方式逐步画出 JDK 1.7HashMap在多线程扩容时产生死循环的关键过程。图中使用不同颜色区分线程、节点和危险操作并重点标出环形链表形成的瞬间。 步骤 1初始状态旧数组 正常链表旧数组 table颜色灰色 ┌─────────┐ │ bucket │──→ [A] ──→ [B] ──→ [C] ──→ null └─────────┘ (灰色) (灰色) (灰色) (灰色)链表顺序A → B → C两个线程T1、T2都准备扩容。 步骤 2线程 T1 挂起保存了局部变量T1 进入transfer()方法用头插法迁移链表。它刚读取了当前节点e和下一个节点next就被挂起。T1 局部变量 蓝色标记 e [A] next [B] 旧数组状态未变 ┌─────────┐ │ bucket │──→ [A] ──→ [B] ──→ [C] ──→ null └─────────┘ T1 挂起T2 获得 CPU 开始扩容。 步骤 3线程 T2 完成扩容头插法导致链表反转T2 将旧链表A → B → C用头插法迁移到新数组结果顺序完全反转新数组 newTable 绿色背景 ┌─────────┐ │ bucket │──→ [C] ──→ [B] ──→ [A] ──→ null └─────────┘ 注意B.next 原来指向 C现在 B.next 指向 A。 旧数组不再使用但 T1 还持有旧数组的引用以及过时的e[A]、next[B]。 步骤 4线程 T1 恢复开始迁移死循环形成点T1 继续执行它仍认为e [A]、next [B]但此时[B]在新数组里的next已经指向[A]由 T2 造成。T1 执行头插法逻辑伪代码do{EntryK,Vnexte.next;// T1 已经取好 next Be.nextnewTable[i];// 头插将 e 的 next 指向新数组当前头newTable[i]e;// 将 e 设为新头enext;// 移动 e 到下一个节点}while(e!null);第一轮循环处理 AT1 将A.next指向新数组当前头此时新数组头是 C不对因为 T2 完成后新数组是C→B→A但 T1 开始迁移时它会把 A 插入到新数组的同一个桶位置而这个桶目前已经是C→B→A其实经典案例里T1 和 T2 共用新数组但 T2 已完全迁移完毕新数组里已经是C→B→A。T1 拿到的新数组就是这个样子。T1 又要把 A 再迁移一次导致混乱。更准确的标准解释死循环常见模型是T1 恢复时e A它把 A 头插到新数组然后取next B此时发现 B 的next指向 A因为 T2 反转后B→A于是继续处理 B 时又把 B 头插到 A 前面导致A.next B且B.next A。我们用图来展示这个环形形成的一瞬间T1 开始迁移前新数组已有 T2 迁移的结果 部分 ┌─────────┐ │ bucket │──→ [C] ──→ [B] ──→ [A] ──→ null └─────────┘ T1 插入 A头插法 A.next 新数组当前头即 C 新数组头 A 结果 ┌─────────┐ │ bucket │──→ [A] ─┐ └─────────┘ │ ↓ [C] ──→ [B] ──→ [A] ??? ↑ └──────┘ 注意原来的 [A] 还在链表尾部而 [A] 又被插到了头部。这个图容易乱。我们换一个标准死循环形成的经典场景只涉及 A 和 B 两个节点更清晰 标准环形产生过程A、B 两个节点初始链表旧数组[ A ] → [ B ] → nullT1 挂起时e A, next BT2 扩容完成头插法反转新数组 [ B ] → [ A ] → null ↑ B.next 指向 AT1 恢复执行第一轮处理 AA.next newTable[i] → A.next 指向 B因为 newTable[i] 当前是 B newTable[i] A 此时新数组 [ A ] → [ B ] → [ A ] → null (A.next B, 但 B.next 仍然是 A)具体指针A.next BT1 刚设的B.next AT2 之前设的形成环┌─────────────┐ ↓ ↑ [ A ] ──next──→ [ B ] ──next──┘ 彩色流程图最终死循环点 初始链表棕色 [A] ──→ [B] ──→ null T1 挂起蓝色局部变量 e [A] , next [B] T2 完成扩容绿色新数组头插法反转 newTable: [B] ──→ [A] ──→ null (B.next A) T1 恢复并执行头插红色 危险操作 ① A.next newTable[i] → A.next B ② newTable[i] A 新数组变成 [A] ──→ [B] ──→ [A] ──→ ... ↑ │ └────────┘ B.next 仍然指向 A来自 T2 A.next 现在指向 B来自 T1 死循环点当遍历 get(A) 或 get(B) 时会在 A ↔ B 之间无限循环。✅ 总结关键点用颜色标记初始链表顺序正常。T1 挂起保存了过时的e和next。T2 扩容头插法反转链表B.next → A。T1 恢复头插法再次反转造成A.next B且B.next A。死循环环形链表形成遍历永不结束。这张“彩色流程图”能清晰展示 JDK 1.7HashMap死循环的完整链条 总结JDK 1.7HashMap的死循环是多线程环境下头插法导致的链表反转与并发操作的意外耦合。一个常见的误解是死循环在生成环形链表时就立刻发生。实际上环形链表形成后后续的get()、put()操作一旦遍历到这个环才会导致CPU 100%的死循环。