JDK 7 HashMap 并发死循环：环形链表

一、背景

JDK 7 HashMap 扩容时 transfer 用头插法，多线程并发扩容会形成环形链表。

二、JDK 7 扩容流程

void transfer(Entry[] newTable) {
    Entry[] src = table;
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        while (e != null) {
            Entry<K,V> next = e.next;
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];   // 头插
            newTable[i] = e;
            e = next;
        }
    }
}

三、怎么形成环

假设一个桶里有 a → b（a.next = b）：

线程 1 扩容

1. 取 a，放进新表桶：newTable[0] = a。
2. 取 b，头插：b.next = a，newTable[0] = b。
3. 结果：b → a。

线程 2 在同一时刻

线程 2 还在旧表遍历，e = a，next = b。

如果线程 1 已经把 a 和 b 放到新表，但线程 2 的 e 和 next 引用还在：

1. 线程 2 处理 a：a.next = newTable[0]（可能是 b），newTable[0] = a。
2. 线程 2 处理 b：b.next = newTable[0]（是 a），newTable[0] = b。
3. 结果：a.next = b，b.next = a → 环。

四、为什么是头插法

头插法把同一桶的元素倒序：旧表 a → b，新表 b → a。两个线程同时倒序，容易成环。

JDK 8 改成尾插法，不会成环，但还有数据覆盖问题。

五、后果

• get() 时遍历链表，遇到环死循环，CPU 100%。
• 多线程 put 丢数据。

六、JDK 8 修复

• 用尾插法，不再倒序。
• 链表长度 ≥ 8 转红黑树。
• 但 HashMap 仍然不是线程安全的，多线程下可能丢数据。并发用 ConcurrentHashMap。

不要在多线程下用 HashMap

• JDK 7：死循环 CPU 100%。
• JDK 8：数据覆盖。
• 多线程用 ConcurrentHashMap 或 Collections.synchronizedMap。