Java HashMap在并发扩容时出现死链的put操作

在多线程环境中使用 java.util.HashMap 会导致严重问题，其中最经典的就是在扩容期间执行 put 操作，可能导致链表形成环路（死链）。一旦形成死链，后续对这个位置的 get 或 put 操作将陷入无限循环，占用 100% 的 CPU，导致系统完全无响应。本文将带你一步步理解这一问题的根源、如何复现，以及正确的解决方案。

1. 问题现象与核心原因

识别症状：在多线程高并发场景下，对同一个 HashMap 实例进行频繁的 put 操作，程序突然卡死，线程栈显示死在 HashMap.get() 或 HashMap.put() 方法内部的循环中。

根本原因：HashMap 不是线程安全的。其内部 resize()（扩容）方法在并发执行时，会导致链表的节点顺序被多个线程同时修改，从而形成环形链表。

关键点：死链只发生在数组扩容（即创建新数组并迁移旧数据）的过程中。单纯的并发 put（未触发扩容）会导致数据丢失或覆盖，但通常不会死循环。

2. 问题复现指南

以下步骤将指导你编写一个可以稳定复现此问题的 Java 程序。

1. 准备环境：确保已安装 JDK 8 或更早版本（JDK 8 的 HashMap 实现是问题的经典案例）。新版 JDK（如 JDK 8+的 ConcurrentHashMap 或 JDK 8 优化后的 HashMap）已部分修复此问题，但理解原理至关重要。

2. 创建测试类：新建一个 Java 文件，例如 HashMapDeadlockDemo.java。

3. 编写复现代码：在文件中输入以下核心代码结构。代码故意设置一个较小的初始容量和负载因子，以轻易触发扩容。

   import java.util.HashMap;
   import java.util.Map;
   import java.util.concurrent.atomic.AtomicInteger;
   
   public class HashMapDeadlockDemo {
       // 使用一个较小的初始容量和负载因子，强制频繁扩容
       private static final int INITIAL_CAPACITY = 4;
       private static final float LOAD_FACTOR = 0.75f;
       private static Map<Integer, Integer> map = new HashMap<>(INITIAL_CAPACITY, LOAD_FACTOR);
       private static AtomicInteger keyGenerator = new AtomicInteger(0);
   
       public static void main(String[] args) {
           // 启动多个线程，持续进行 put 操作
           for (int i = 0; i < 10; i++) {
               new Thread(() -> {
                   while (true) {
                       int key = keyGenerator.incrementAndGet();
                       map.put(key, key);
                       // 简单打印以观察进度，可注释掉
                       // System.out.println(Thread.currentThread().getName() + " put: " + key);
                   }
               }, "Thread-" + i).start();
           }
       }
   }

4. 执行与观察：编译并运行此程序。在大多数情况下，程序不会立即死锁。你可以增加线程数量（例如改为100个线程），或者减小初始容量（例如改为2）来增加触发死锁的概率。当死锁发生时，你会观察到所有线程卡死，CPU 使用率飙升。

3. 深入源码：死链是如何形成的

理解死链需要查看 JDK 8 之前的 HashMap.put 和 HashMap.resize 源码。我们将场景简化为两个线程（T1， T2）同时对同一个桶（bucket）的链表进行扩容迁移。

关键代码片段（HashMap.java JDK 7/8 风格）：

void addEntry(int hash, K key, V value, int bucketIndex) {
    // 1. 检查是否需要扩容
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
}

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    // ... 省略部分检查
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable); // 核心迁移方法
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

// 这是形成死链的关键方法
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; // 置空旧数组槽位
            do {
                Entry<K,V> next = e.next; // 1. 暂存下一个节点
                int i = indexFor(e.hash, newCapacity); // 2. 计算新位置
                e.next = newTable[i]; // 3. 将当前节点的 next 指向新桶的头节点
                newTable[i] = e; // 4. 将当前节点插入新桶的头部
                e = next; // 5. 处理下一个节点
            } while (e != null);
        }
    }
}

4. 并发扩容的逐步死链分析

假设旧数组某桶有一个简单的链表：A -> B -> null。两个线程 T1 和 T2 同时执行 transfer 方法。

1. 初始状态：旧桶链表为 A -> B -> null。
2. T1 执行到步骤1后挂起：T1 执行 Entry next = e.next;，此时 e 是节点 A，next 是节点 B。然后 T1 被操作系统挂起。
3. T2 完成整个迁移：T2 获得 CPU 时间片，它完整执行了 transfer 方法，将链表 A -> B 迁移到了新数组。由于是头插法，新链表顺序会反转，变为 B -> A -> null（在新数组的某个桶 i 中）。
4. T1 恢复执行：T1 从挂起点继续执行。
   • T1 的 e 仍然是节点 A，它的 next（步骤1暂存的）仍然是节点 B。
   • 关键步骤3：e.next = newTable[i];。此时 newTable[i] 的值已经被 T2 设置为了节点 B（因为 T2 先完成了迁移）。所以，节点 A 的 next 指针被设置为指向节点 B。
   • 关键步骤4：newTable[i] = e;。将节点 A 作为新桶的头节点。
   • 此时，新桶的链表结构变为：A -> B。但请注意，节点 B 的 next 指针在哪里？在 T2 的迁移过程中，节点 B 的 next 已经被设置为节点 A（因为 T2 先迁移了 A，然后 B 指向了 A）。所以，实际内存中的引用关系是：A.next -> B 且 B.next -> A。一个环形链表诞生了。
5. 进入死循环：当后续任何线程调用 get 方法，遍历这个桶的链表时，就会陷入 A -> B -> A -> B ... 的无限循环。

5. 根本解决方案

避免此问题的唯一方法是不要在多线程环境下使用 HashMap。请根据场景选择以下替代方案。

1. 使用 Collections.synchronizedMap：

   • 做法：通过工具类包装 HashMap，使其所有方法都同步。
   • 示例：Map<K, V> safeMap = Collections.synchronizedMap(new HashMap<>());
   • 缺点：粒度太粗，所有操作（包括读）都互斥，性能低下。

2. 使用 ConcurrentHashMap (首选)：

   • 做法：直接使用 java.util.concurrent.ConcurrentHashMap。它通过分段锁（JDK 7）或 CAS + synchronized（JDK 8+）实现高并发安全，且读操作通常无锁。
   • 示例：ConcurrentHashMap<K, V> concurrentMap = new ConcurrentHashMap<>();
   • 优点：高性能，高吞吐量，是并发场景的标准答案。

3. 使用 Hashtable (不推荐)：

   • 做法：一个古老的线程安全 Map 实现。
   • 缺点：全表锁，性能极差，已不推荐使用。

4. 使用 Collections.unmodifiableMap：

   • 做法：如果 Map 在初始化后不需要修改，可以在构建完成后将其包装为不可变映射。
   • 示例：

     Map<K, V> tempMap = new HashMap<>();
     // ... 填充 tempMap
     Map<K, V> immutableMap = Collections.unmodifiableMap(tempMap);
     // 将 immutableMap 共享给多个线程

   • 适用场景：读多写无。

结论：在任何涉及多线程访问 Map 的场景，请优先使用 ConcurrentHashMap。它不仅避免了死链问题，还提供了更高的并发性能。