HashMap 並發缺陷深度剖析：從死循環到數據丟失的根因與規避

引言：為何 HashMap 非線程安全？

HashMap 作為高頻使用的映射容器，其並發缺陷常被忽視。本文從源碼層面剖析 put/get 機制、擴容遷移邏輯，演示多線程導致 CPU 100% 死循環與數據丟失的根本原因，並給出生產級解決方案。

核心操作源碼解讀

put 流程

public V put(K key, V value) {
    if (key == null) return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

關鍵點：hash() 二次散列、indexFor() 取模定位、鏈表遍歷覆蓋、addEntry() 頭插法並檢查擴容閾值。

get 流程

public V get(Object key) {
    if (key == null) return getForNullKey();
    int hash = hash(key.hashCode());
    for (Entry e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    return null;
}

Entry 節點結構

static class Entry implements Map.Entry {
    final K key;
    V value;
    Entry next;
    final int hash;
}

擴容遷移：並發災難溫床

當 size >= threshold 觸發 resize(2 * table.length)，核心遷移邏輯在 transfer()：

void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) {
        Entry e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry next = e.next;  // 關鍵點：線程掛起點
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];       // 頭插法：反轉鏈表順序
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

頭插法導致鏈表反轉，正是並發環境下形成環形鏈表的元兇。

死循環形成過程圖解

引用陳皓《疫苗：Java HashMap 的死循環》經典推演：

1. 初始狀態：鏈表 3 → 7（table[3] 處）。
2. 線程 A 執行至 next = e.next（e=3, next=7）掛起。
3. 線程 B 完成遷移，新表鏈表變為 7 → 3（反轉）。
4. 線程 A 恢復：e.next = newTable[i] 使 3.next 指向 7；e = next 使 e 指向 7；下輪循環 next = e.next 使 next 指向 3（因 7.next 已指向 3）。
5. 環形鏈表誕生：e.next = newTable[i] 使 3.next 再次指向 7 → 3 ↔ 7 循環。
6. 後果：get(11) 遍歷該桶位陷入 e = e.next 無限循環，CPU 100%。

實戰復現代碼

public class MapThread extends Thread {
    private static AtomicInteger ai = new AtomicInteger(0);
    private static HashMap map = new HashMap<>(1); // 初始容量 1，易觸發擴容

    public void run() {
        while (ai.get() < 100000) {
            map.put(ai.get(), ai.get());
            ai.incrementAndGet();
        }
        System.out.println(Thread.currentThread().getName() + " 線程結束");
    }
}

// 主方法啟動 10 線程並發 put，多次運行易復現死循環
// 改用 ConcurrentHashMap 即可規避

另一隱患：多線程 put 導致數據丟失

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e); // 非原子操作
    if (size++ >= threshold) resize(2 * table.length);
}

兩線程同桶位並發執行，後執行者覆蓋前者頭節點，導致先插入節點斷鏈丟失。

生產級解決方案

核心建議：嚴禁多線程環境直接使用 HashMap，首選 ConcurrentHashMap；若需複合操作原子性，配合 computeIfAbsent、merge 等原子方法或外部鎖。