【Java】JDK 7 HashMap 头插法在并发情况下的成环问题

article/2025/9/30 2:02:31

CONTENT

- 问题描述
- 成因详解
- 总结
- Reference

问题描述

JDK 7 的 HashMap 解决冲突用的是拉链法，在拉链的时候用的是头插，每次在链表的头部插入新元素。resize() 的时候用的依然是头插，头插的话，如果某个下标中的链表在新的 table 中依然索引到同一个下标中，那么原链表的顺序会反转。因为链表是顺序访问的，那么每次访问一个节点，会把当前节点插到新 table 链表的头部，这样原链表的最后一个元素在 resize() 后，就变成新链表的头部了（如果它们索引到新 table 的同一个下标中）。这在并发的情况下可能产生环。

成因详解

resize() 核心代码，去掉了一些与本问题不相关的部分。

        for (Entry<K,V> e : table) { // e 是每一个链表的头节点while(null != e) {Entry<K,V> next = e.next; // 当前节点 e 的下一个节点 nextint i = indexFor(e.hash, newCapacity); // i 是 e 在新 table 中的索引e.next = newTable[i]; // 头插法，当前节点的 next 是当前新 table 对应索引的头节点newTable[i] = e; // 更新 新 table 对应索引的头节点e = next; // 旧 table 当前链表的下一个节点}}

一个简单的情况，map 当前处于扩容边缘，再添加一个 Entry 就得扩容。现在有两个线程，Thread1 要 put，Thread2 也要 put，那么如果没有锁，就可能会出现环。

Thread1 先扩容，执行到 e=e0;next=e1; 的时候，Thread2 开始执行扩容，Thread2 完成扩容之后，Thread1 继续执行，即下图中的前两格。那么当前出现了一个现象，e1 的 next 变成 e0 了，e0 的 next 变成 null 了。

然后 Thread1 继续执行，e0 的 next 变成 null，newTable1[i]=e0; 并且此时 e1 指向 e0。next 没有变，还是最开始指向的 next=e1;

继续下一次循环，这时 e=e1; 重点：next=e0;，继续执行，可以得到 e1 指向 e0，newTable1[i]=e1; 的结果，如果不继续循环这就是对的，但是此时 next=e0;。
在这里插入图片描述
最后 e=e0;，这时问题便发生了，e0.next=newTable1[i];，这时的 newTable1[i] 就是 e1，所以此时 e0 指向了 e1，而 e1 还指向 e0，这时就成环了。