JDK 並發容器深度解析：ConcurrentHashMap —— 分段鎖與 CAS 的經典實現

概覽：ConcurrentHashMap 為什麼快？

• 分段鎖：默認 16 個 Segment，寫操作僅鎖住目標 Segment，讀完全無鎖。
• 懶初始化：僅 segments[0] 立即創建，其餘首次 put 時創建，節省內存。
• 弱一致性讀：volatile 字段 + final 字段 + Unsafe.putOrderedObject 保證可見性，無需加鎖。
• 擴容優化：僅擴容當前 Segment，不阻塞其他 Segment；舊節點 next 指針不變可重用。

適用場景：高併發緩存、計數器、會話存儲、多線程 Map 操作通用選擇。

一、核心數據結構

1.1 Segment 數組：分段鎖的基本單元

final Segment[] segments;  // 2 的冪次長度，默認 16
static final class Segment extends ReentrantLock implements Serializable {
    transient volatile HashEntry[] table;  // 哈希桶數組
    transient int count;          // 元素數量（寫鎖保護）
    transient int modCount;       // 修改次數（用於 size/isEmpty 一致性檢查）
    transient int threshold;      // 擴容閾值 = capacity * loadFactor
    final float loadFactor;       // 所有 Segment 共享

    Segment(float lf, int threshold, HashEntry[] tab) { ... }
}

1.2 HashEntry：鍵值節點

static final class HashEntry {
    final int hash;               // 擴容時不變，可重用
    final K key;                  // 不可變
    volatile V value;             // 可見性保證
    volatile HashEntry next; // 鏈表指針，volatile + putOrderedObject

    HashEntry(int hash, K key, V value, HashEntry next) { ... }
    // lazySet 寫入 next，配合鎖釋放保證有序性
    final void setNext(HashEntry n) {
        UNSAFE.putOrderedObject(this, nextOffset, n);
    }
}

1.3 關鍵參數計算

定位公式：

int hash = hash(key);                    // 再哈希散列高低位
int segmentIndex = (hash >>> segmentShift) & segmentMask;  // 高位定 Segment
int bucketIndex  = (table.length - 1) & hash;               // 低位定桶

二、構造器：參數遞歸與懶初始化

public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
    // 參數校驗、計算 2 的冪次 ssize (Segment 數)
    int sshift = 0, ssize = 1;
    while (ssize < concurrencyLevel) { ++sshift; ssize <<= 1; }
    this.segmentShift = 32 - sshift;
    this.segmentMask  = ssize - 1;

    // 計算每 Segment 容量 cap
    int c = initialCapacity / ssize; if (c * ssize < initialCapacity) ++c;
    int cap = MIN_SEGMENT_TABLE_CAPACITY; while (cap < c) cap <<= 1;

    // 創建 segments[0] 並有序寫入 segments 數組
    Segment s0 = new Segment<>(loadFactor, (int)(cap * loadFactor), new HashEntry[cap]);
    Segment[] ss = (Segment[]) new Segment[ssize];
    UNSAFE.putOrderedObject(ss, SBASE, s0);  // 有序寫入，保證可見性
    this.segments = ss;
}

其他構造器均委托至此構造器，最後可選 putAll(m)。

三、核心操作流程

3.1 讀操作 get(key) —— 完全無鎖

public V get(Object key) {
    int h = hash(key);
    // 1. 定位 Segment（volatile 讀）
    long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
    Segment seg = (Segment) UNSAFE.getObjectVolatile(segments, u);
    if (seg == null || seg.table == null) return null;

    // 2. 定位桶（volatile 讀 table 引用）
    HashEntry[] tab = seg.table;
    HashEntry e = (HashEntry) UNSAFE.getObjectVolatile
        (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);

    // 3. 遍歷鏈表（volatile 讀 next/value）
    for (; e != null; e = e.next) {
        K k; if ((k = e.key) == key || (e.hash == h && key.equals(k)))
            return e.value;  // volatile 讀 value
    }
    return null;
}

可見性保證鏈：
putOrderedObject(table, idx, node) (寫) → unlock() (釋放鎖，內存屏障) → getObjectVolatile(table, idx) (讀) → e.value (volatile 讀)

3.2 寫操作 put(key, value) —— 分段鎖 + 自旋獲取

public V put(K key, V value) {
    if (value == null) throw new NullPointerException();
    int hash = hash(key);
    int j = (hash >>> segmentShift) & segmentMask;
    // 1. 獲取或創建 Segment（懶初始化）
    Segment seg = (Segment) UNSAFE.getObject(segments, (j< node = tryLock() ? null : scanAndLockForPut(key, hash, value);
    V oldValue;
    try {
        HashEntry[] tab = table;
        int index = (tab.length - 1) & hash;
        HashEntry first = entryAt(tab, index);  // volatile 讀

        // 3. 遍歷鏈表查找或插入
        for (HashEntry e = first;;) {
            if (e != null) {
                K k; if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {
                    oldValue = e.value;
                    if (!onlyIfAbsent) { e.value = value; ++modCount; }
                    break;
                }
                e = e.next;
            } else {
                // 4. 鏈表頭插法插入新節點
                if (node != null) node.setNext(first);
                else node = new HashEntry<>(hash, key, value, first);
                int c = count + 1;
                if (c > threshold && tab.length < MAXIMUM_CAPACITY)
                    rehash(node);  // 擴容
                else
                    setEntryAt(tab, index, node);  // putOrderedObject 寫入
                ++modCount; count = c; oldValue = null;
                break;
            }
        }
    } finally { unlock(); }
    return oldValue;
}

3.3 自旋獲取鎖並預熱 scanAndLockForPut

private HashEntry scanAndLockForPut(K key, int hash, V value) {
    HashEntry first = entryForHash(this, hash);
    HashEntry e = first, node = null;
    int retries = -1;
    while (!tryLock()) {
        if (retries < 0) {
            if (e == null) { if (node == null) node = new HashEntry<>(hash, key, value, null); retries = 0; }
            else if (key.equals(e.key)) retries = 0;
            else e = e.next;
        } else if (++retries > MAX_SCAN_RETRIES) { lock(); break; }
        else if ((retries & 1) == 0 && (first = entryForHash(this, hash)) != first) { e = first; retries = -1; }
    }
    return node;
}

多核下自旋避免線程上下文切換，同時提前遍歷/創建節點，減少持鎖時間。

3.4 刪除 remove(key)

final V remove(Object key, int hash, Object value) {
    if (!tryLock()) scanAndLock(key, hash);  // 自旋獲取鎖
    V oldValue = null;
    try {
        HashEntry[] tab = table;
        int index = (tab.length - 1) & hash;
        HashEntry e = entryAt(tab, index), pred = null;
        while (e != null) {
            K k; HashEntry next = e.next;
            if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {
                V v = e.value;
                if (value == null || value == v || value.equals(v)) {
                    if (pred == null) setEntryAt(tab, index, next);  // 刪除頭節點
                    else pred.setNext(next);                         // 刪除中間節點
                    ++modCount; --count; oldValue = v;
                }
                break;
            }
            pred = e; e = next;
        }
    } finally { unlock(); }
    return oldValue;
}

3.5 擴容 rehash(node) —— 僅擴容當前 Segment

private void rehash(HashEntry node) {
    HashEntry[] oldTable = table;
    int oldCap = oldTable.length, newCap = oldCap << 1;
    threshold = (int)(newCap * loadFactor);
    HashEntry[] newTable = new HashEntry[newCap];
    int sizeMask = newCap - 1;

    // 遍歷舊桶，重用同桶節點鏈尾部
    for (int i = 0; i < oldCap; i++) {
        HashEntry e = oldTable[i];
        if (e != null) {
            HashEntry next = e.next;
            int idx = e.hash & sizeMask;
            if (next == null) newTable[idx] = e;  // 單節點直接重用
            else {
                // 找到最後一個索引不變的節點 lastRun
                HashEntry lastRun = e, lastIdx = idx;
                for (HashEntry last = next; last != null; last = last.next) {
                    int k = last.hash & sizeMask;
                    if (k != lastIdx) { lastIdx = k; lastRun = last; }
                }
                newTable[lastIdx] = lastRun;  // 重用尾部鏈
                // 克隆前段節點
                for (HashEntry p = e; p != lastRun; p = p.next) {
                    V v = p.value; int h = p.hash; int k = h & sizeMask;
                    HashEntry n = newTable[k];
                    newTable[k] = new HashEntry<>(h, p.key, v, n);
                }
            }
        }
    }
    // 插入觸發擴容的新節點
    int nodeIndex = node.hash & sizeMask;
    node.setNext(newTable[nodeIndex]);
    newTable[nodeIndex] = node;
    table = newTable;  // volatile 寫入新 table 引用
}

優化點：默認負載因子下僅 1/6 節點需克隆，其餘重用 next 鏈尾部。

3.6 size() / isEmpty() —— 兩階段無鎖嘗試 + 全局鎖回退

public int size() {
    final Segment[] segments = this.segments;
    long last = 0L; int retries = -1;
    try {
        for (;;) {
            if (++retries == RETRIES_BEFORE_LOCK) {  // 默認 2 次
                for (int j=0; j seg = segmentAt(segments, j);
                if (seg != null) { sum += seg.modCount; int c = seg.count; if (c<0 || (size+=c)<0) overflow=true; }
            }
            if (sum == last) break;  // 兩次 modCount 相同，視為穩定
            last = sum;
        }
    } finally {
        if (retries > RETRIES_BEFORE_LOCK) for (int j=0; j

abstract class HashIterator {
    int nextSegmentIndex = segments.length - 1;
    int nextTableIndex = -1;
    HashEntry[] currentTable;
    HashEntry nextEntry, lastReturned;

    final void advance() {
        while (true) {
            if (nextTableIndex >= 0) {
                if ((nextEntry = entryAt(currentTable, nextTableIndex--)) != null) break;
            } else if (nextSegmentIndex >= 0) {
                Segment seg = segmentAt(segments, nextSegmentIndex--);
                if (seg != null && (currentTable = seg.table) != null)
                    nextTableIndex = currentTable.length - 1;
            } else break;
        }
    }
    // ... nextEntry(), hasNext(), remove() ...
}