jdk1.7 在多线程下扩容可能导致的死循环问题

首先先看看 hashmap 在jdk1.7 下扩容的核心方法

void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; // 遍历旧数组的每一个格子（桶） for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; // 断开旧数组的引用，虽然不是必须的，但有助于GC // 遍历链表，把链表上的节点一个一个摘下来，重新放到新数组里 do { // 【关键点1】先保存下一个节点，防止待会链表断了找不到后面的人 Entry<K,V> next = e.next; // 计算这个节点在新数组中的下标 int i = indexFor(e.hash, newCapacity); // 【关键点2】头插法核心：将当前节点 e 的 next 指向新数组位置原本的头节点 e.next = newTable[i]; // 【关键点3】将新数组该位置的头指针指向 e（e 变成了新的头节点） newTable[i] = e; // 【关键点4】继续处理旧链表的下一个节点 e = next; } while (e != null); } } }

可以看到，jdk1.7 版本下的扩容依靠的是头插法实现元素搬移的

头插法 的特点：假设旧数组某个位置的链表是A -> B -> C。 因为代码逻辑是：每次把新来的元素插到最前面（e.next = newTable[i]然后newTable[i] = e）。 所以搬运到新数组后，顺序会倒置，变成C -> B -> A。

为什么JDK 1.7用头插法？ 设计者当时认为，后插入的数据被访问的概率更高（热点数据），放在头部查得快。但这在多线程下埋下了祸根。

那其实在多线程的情况下就会有问题了，举个例子：

假设有两个线程Thread 1和Thread 2同时在扩容。 旧链表结构：A -> B。 线程 1 执行到你注释的那一行挂起了（Paused）：

Entry<K,V> next = e.next; // 线程1在这里卡住了！ // 此时对于线程1来说： e = A, next = B

接下来可能发生的事情：

1. 线程 2 抢占 CPU 完成了扩容：

• • Thread 2 把A和B都搬到了新数组。
  • 注意：因为是头插法，顺序反了
  • 在新内存里，现在的链表结构是：B -> A（B 指向 A，A 指向 null）。

1. 线程 1 醒来继续执行：

• • Thread 1 里的变量还停留在挂起前的状态：e = A，next = B。
  • Thread 1 开始干活：

• • • 将 A 指向 B
    • 头节点变成 A
    • 此时 A 指向 B，B 指向 A（死循环开始）

1. 线程 1 接着处理 B，B 头插当头节点，此时 B 指向 A，A 指向 B
2. 然后接着处理 A，A 头插当头节点，此时 A 指向 B，B 指向 A
3. 然后循环往复 A，B 轮流当头节点，死循环

如图：