Java 理論與實踐：構建更好的 HashMap——ConcurrentHashMap 核心原理解析

前言：為什麼需要 ConcurrentHashMap？

Hashtable 與 Collections.synchronizedMap 使用單一全局鎖，嚴重限制並發吞吐量。Doug Lea 的 util.concurrent 包中的 ConcurrentHashMap 採用創新的分段鎖與無鎖讀取技術，實現了高並發、高吞吐量，後被納入 JDK 1.5 java.util.concurrent 並針對 JSR 133 新內存模型優化。

核心優化策略

1. 多個寫鎖（分段鎖）

預設 32 個 Segment，每個守護一部分哈希桶。理論上允許 32 個線程並發寫入，實際並發度受限於哈希分佈但遠超單鎖。

2. 無鎖讀取（樂觀讀）

get() 操作大多數情況下完全無鎖：

• 讀取桶頭指針（可能過期）
• 遍歷不可變鏈表（next、key、hash 均為 final）
• value 為 volatile，可見性有保障
• 若發現 null 值或頭指針變化 → 降級為同步重讀

適用於「讀多寫少、查找多為命中」的典型場景。

3. 不變性設計

Entry 節點除 value 外全 final。插入僅在頭部，刪除通過克隆前綴節點重建鏈表。保證：一旦持有鏈表引用，其結構永不改變，極大簡化無鎖遍歷的正確性證明。

4. 利用 JMM 的 final 與 volatile 語義

• final 字段：新 JMM 保證構造函數結束前對其他線程可見；舊 JMM 無此保證，實現通過「默認值非法」檢測（如 hash=0）觸發同步重試。
• volatile value：寫入即時可見，讀取線程能立即看到更新或刪除（null）。

關鍵操作實現剖析

get()：無鎖快速路徑 + 同步慢速路徑

public Object get(Object key) {
    int hash = hash(key);
    Entry[] tab = table;
    int index = hash & (tab.length - 1);
    Entry first = tab[index];
    for (Entry e = first; e != null; e = e.next) {
        if (e.hash == hash && eq(key, e.key)) {
            Object value = e.value;
            if (value != null) return value; // 命中
            else break; // 值為 null 表示已刪除，需同步重檢
        }
    }
    // 同步重檢
    Segment seg = segments[hash & SEGMENT_MASK];
    synchronized(seg) { ... }
}

remove()：雙階段刪除

1. 同步鎖定 Segment，找到目標節點，將其 value 設為 null（觸發讀線程重試）。
2. 克隆從頭節點到目標節點前的所有節點，接上目標節點的 next，更新桶頭指針。原鏈表節點最終被 GC 回收。

確保迭代器不會重複或遺漏元素。

put()：同步插入/更新

持有 Segment 鎖，查找鍵是否存在：存在則更新 volatile value；不存在則創建新 Entry 插入桶頭。不阻塞其他 Segment 的讀/寫。

弱一致性迭代器

• 構建時同步獲取各桶頭指針快照。
• 遍歷過程中不阻塞寫入，可能不反映尚未到達桶的插入，但保證：已到達桶的更新/刪除可見，每個元素最多返回一次，永不拋出 ConcurrentModificationException。

動態擴容

鏈表長度超過閾值標記擴容。當足夠多桶需擴容時，遞歸獲取所有 Segment 鎖，重新哈希到更大表。對調用者透明。

「無鎖」的本質

volatile 讀寫在硬件層面仍涉及緩存一致性協議（內存屏障），但屬於細粒度、無調度開銷、無 JVM 監視器進出開銷。在「讀多寫少」場景下，實際並發性極高。

結語

ConcurrentHashMap 是並發編程與 JMM 深度結合的經典之作。使用它，從中學習，享受其高性能——但除非你是並發專家，否則請勿嘗試自行實現類似結構。