当前位置：首页 > news >正文

头插法多线程不可用的原因

news 2026/4/27 2:15:59

为什么头插法多线程下不可用？我们以HashMap扩容时用的头插法举例子:

JDK 1.7 HashMap 扩容时的头插法迁移逻辑

// 旧数组Entry[]oldTable=table;// 新数组（容量翻倍）Entry[]newTable=newEntry[oldCapacity*2];// 遍历旧数组的每个桶for(inti=0;i<oldTable.length;i++){// 拿到当前桶的头节点eEntry<K,V>e=oldTable[i];// 如果这个桶不为空，就遍历链表while(e!=null){// 【关键1】先保存e的下一个节点next// 因为接下来要修改e的next指针，不保存就会丢失后面的链表Entry<K,V>next=e.next;// 【关键2】计算e在新数组中的索引intnewIndex=indexFor(e.hash,newTable.length);// 【关键3】头插法：把e插入到新数组newIndex位置的链表头部// 步骤1：e的next指向新数组当前的头节点e.next=newTable[newIndex];// 步骤2：新数组的头指针指向enewTable[newIndex]=e;// 【关键4】处理下一个节点e=next;}}// 扩容完成，把table指向新数组table=newTable;

一、单线程下：头插法迁移的完整演示

我们用最简单的例子，一步一步看单线程下头插法是如何工作的。

初始状态

旧数组容量 = 2
桶 0 的链表：A → B → null
假设 A 和 B 的 hash 值在新数组（容量 = 4）中计算出的索引都是 0（这样它们会被迁移到同一个桶）

执行迁移代码步骤

第一次循环（e = A）

next = e.next→next = B（保存 A 的下一个节点）
计算新索引：newIndex = 0
头插法插入 A 到新数组桶 0：
- e.next = newTable[0]→A.next = null（因为新数组桶 0 现在是空的）
- newTable[0] = A→ 新数组桶 0：A → null
e = next→e = B（准备处理下一个节点）

当前状态

旧数组桶 0：A → B → null（还没修改）
新数组桶 0：A → null

第二次循环（e = B）

next = e.next→next = null（保存 B 的下一个节点）
计算新索引：newIndex = 0
头插法插入 B 到新数组桶 0：
- e.next = newTable[0]→B.next = A（新数组桶 0 当前的头是 A）
- newTable[0] = B→ 新数组桶 0：B → A → null
e = next→e = null（循环结束）

最终状态

旧数组桶 0：A → B → null
新数组桶 0：B → A → null

关键点：原来的链表A → B，经过头插法迁移后，变成了B → A，顺序完全反转了。这是头插法最核心的特点，也是多线程并发下可能产生死循环的根源。

二、多线程下：死循环是如何一步步形成的？

现在我们有了头插法的基础，再回头看死循环，就会一目了然。

场景

还是用上面的例子：旧数组桶 0 的链表A → B → null，两个线程 T1 和 T2 同时扩容。

步骤 1：T1 执行到一半被挂起

T1 开始执行迁移代码，执行完第一次循环的第一步：

Entry<K,V>e=oldTable[i];// e = Awhile(e!=null){Entry<K,V>next=e.next;// next = B// 就在这里！T1的CPU时间片用完了，被挂起// 后面的代码还没执行intnewIndex=indexFor(e.hash,newTable.length);...}

此时 T1 的栈中保存着：

e = A
next = B

T1 还没有修改任何节点的 next 指针。

步骤 2：T2 完整完成了迁移

T2 获得 CPU 时间片，完整执行了整个迁移过程，和我们上面单线程的演示一样。

T2 执行完成后：

T2 的新数组桶 0：B → A → null
全局的节点指针被修改了：
- B.next = A
- A.next = null

这是最关键的一步！节点是存在于堆内存中的，所有线程共享。T2 修改了 A 和 B 的 next 指针，T1 对此完全不知情。

步骤 3：T1 被唤醒，继续执行

T1 从挂起的地方恢复执行，它的栈中还是：

e = A
next = B

T1 会继续执行它剩下的代码：

T1 继续执行第一次循环（e = A）

// 已经执行过的：Entry<K,V> next = e.next; // next = BintnewIndex=indexFor(e.hash,newTable.length);// newIndex = 0// 头插法插入A到T1自己的新数组桶0e.next=newTable[newIndex];// A.next = null（T1的新数组桶0是空的）newTable[newIndex]=e;// T1的新数组桶0：A → nulle=next;// e = B（准备处理下一个节点）

当前 T1 的状态：

T1 的新数组桶 0：A → null
e = B

T1 执行第二次循环（e = B）

Entry<K,V>next=e.next;// 【致命一步！】// 现在e是B，B的next已经被T2改成了A！// 所以 next = A，而不是我们预期的null！intnewIndex=indexFor(e.hash,newTable.length);// newIndex = 0// 头插法插入B到T1的新数组桶0e.next=newTable[newIndex];// B.next = A（T1的新数组桶0当前头是A）newTable[newIndex]=e;// T1的新数组桶0：B → A → nulle=next;// e = A（准备处理下一个节点）

当前 T1 的状态：

T1 的新数组桶 0：B → A → null
e = A

T1 执行第三次循环（e = A）

Entry<K,V>next=e.next;// A.next = null（这个是对的）intnewIndex=indexFor(e.hash,newTable.length);// newIndex = 0// 头插法插入A到T1的新数组桶0e.next=newTable[newIndex];// A.next = B（T1的新数组桶0当前头是B）newTable[newIndex]=e;// T1的新数组桶0：A → B → A → ...e=next;// e = null（循环结束）