無鎖 HashMap 原理深度解析：CAS、鏈表有序化、懶惰擴容與 Java 實現難點

為什麼需要無鎖 HashMap？

傳統方案對比：

無鎖目標：零阻塞、零上下文切換、可線性擴展。核心難點在於擴容時的多指針原子更新。

基石：CAS (Compare-And-Swap)

CPU 指令級原子操作：CAS(addr, expected, new) → 若 `*addr == expected` 則 `*addr = new` 返回 true，否則 false。
Java 暴露：`AtomicReference`、`AtomicInteger`、`AtomicLong`、`VarHandle` (JDK 9+)。

// 經典 CAS 循環模式
AtomicInteger counter = new AtomicInteger(0);
public void increment() {
    for (;;) {
        int old = counter.get();
        int newVal = old + 1;
        if (counter.compareAndSet(old, newVal)) return;
        // 失敗自旋重試
    }
}

無鎖鏈表：插入與刪除

鏈表節點：

class Node {
    final K key;
    volatile V value;          // 值可更新
    final int hash;
    final AtomicReference> next = new AtomicReference<>(); // CAS 修改 next
}

插入 (有序鏈表)

1. 找到插入位置前驅節點 pred 和後繼節點 succ (按 hash 有序)。
2. 創建新節點 newNode，newNode.next.set(succ)。
3. CAS 更新前驅 next：pred.next.compareAndSet(succ, newNode)。
4. 失敗則重試 (從頭查找或從 pred 繼續)。

刪除

1. 找到待刪節點 target 及其前驅 pred、後繼 succ。
2. CAS 更新前驅 next：pred.next.compareAndSet(target, succ)。
3. 失敗重試。

關鍵：僅修改 一個 `next` 指針，CAS 即可保證原子性。

核心難題：無鎖擴容

傳統擴容的三指針問題

擴容需將舊桶節點遷移到新桶：

// 需同時原子更新三個指針！
predOld.next = succOld      // 從舊鏈移除
predNew.next = node         // 插入新鏈
node.next = succNew

CAS 只能原子更新單個內存地址，無法同時驗證更新三個指針 → 無法直接無鎖遷移。

突破口：有序鏈表 + 懶惰擴容 + 不移動節點

核心洞見：如果節點在鏈表中永遠按 hash 逆序排列，擴容時無需移動節點，只需新增桶頭哨兵節點！

1. Hash 逆序映射

定義 revHash = Integer.reverse(hashCode) | 1 (最高位置 1 區分正常節點與哨兵)。
桶索引 = revHash & (size - 1) (size 為 2 的冪)。
隨著 size 加倍 (2^i → 2^(i+1))，索引只增加一位二進制位，節點相對順序完全不變。

2. 哨兵節點分組

每個桶頭設置一個哨兵節點，`hash = Integer.reverse(bucketIndex)`，最低位為 0。
正常節點最低位為 1 → 哨兵永遠排在組首。
組內節點按 `revHash` 遞增有序。

3. 擴容 = 新增桶頭哨兵

size 翻倍時，原桶 `j` 分裂為 `j` 和 `j + oldSize` 兩組。
無需移動任何節點，只需在新桶位置創建新哨兵節點，並插入到原鏈表中正確位置 (即原哨兵與第一個屬於新組的節點之間)。
原鏈表節點的 `next` 指針完全不變！

完整數據結構設計

class LockFreeHashMap {
    // 桶數組：AtomicReference 數組，支持 CAS 更新桶頭
    private final AtomicReference>[] buckets;
    // 當前使用的桶數量 (2 的冪)，擴容時 CAS 更新
    private final AtomicInteger size = new AtomicInteger(2); // 初始 2
    // 總節點數 (不含哨兵)
    private final LongAdder count = new LongAdder();
    
    // 負載因子閾值
    private static final double LOAD_FACTOR = 0.75;
}

核心操作流程

1. 桶初始化 (懶惰、遞歸)

private Node initBucket(int bucketIdx) {
    // 父桶索引：去掉最高位
    int parentIdx = bucketIdx ^ Integer.highestOneBit(bucketIdx);
    Node parentHead = buckets[parentIdx].get();
    if (parentHead == null) {
        parentHead = initBucket(parentIdx); // 遞歸初始化父桶
    }
    // 創建哨兵
    Node sentinel = new Node<>(null, null, Integer.reverse(bucketIdx) & ~1);
    // 插入到父鏈表正確位置 (CAS 循環)
    return insertIntoList(parentHead, sentinel);
}

2. Get 操作

public V get(K key) {
    int h = spread(key.hashCode());
    int idx = h & (size.get() - 1);
    Node head = buckets[idx].get();
    if (head == null) return null; // 桶未初始化
    
    int revHash = Integer.reverse(h) | 1;
    for (Node p = head.next.get(); p != null; p = p.next.get()) {
        if (p.hash == revHash && key.equals(p.key)) return p.value;
        if (p.hash > revHash) break; // 有序優化：提前結束
    }
    return null;
}

3. Put 操作

public V put(K key, V value) {
    int h = spread(key.hashCode());
    int revHash = Integer.reverse(h) | 1;
    
    for (;;) {
        int curSize = size.get();
        int idx = revHash & (curSize - 1);
        
        // 懶惰初始化桶
        Node head = buckets[idx].get();
        if (head == null) {
            initBucket(idx);
            continue; // 重試
        }
        
        // 在鏈表中查找/插入
        Node pred = head;
        Node curr = pred.next.get();
        while (curr != null && curr.hash < revHash) {
            pred = curr;
            curr = curr.next.get();
        }
        
        if (curr != null && curr.hash == revHash && key.equals(curr.key)) {
            // 更新值 (CAS)
            V oldVal = curr.value;
            if (curr.value == oldVal || UNSAFE.compareAndSwapObject(curr, valueOffset, oldVal, value)) {
                return oldVal;
            }
            continue; // CAS 失敗重試
        }
        
        // 插入新節點
        Node newNode = new Node<>(key, value, revHash);
        newNode.next.set(curr);
        if (pred.next.compareAndSet(curr, newNode)) {
            count.increment();
            // 擴容檢查
            if (count.sum() > curSize * LOAD_FACTOR) {
                tryResize(curSize);
            }
            return null;
        }
        // CAS 失敗重試
    }
}

4. 擴容協調

private void tryResize(int oldSize) {
    // 嘗試 CAS 更新 size (只有成功者執行擴容)
    if (size.compareAndSet(oldSize, oldSize << 1)) {
        int newSize = oldSize << 1;
        // 為新桶創建哨兵 (並行可由多線程協作完成)
        for (int i = oldSize; i < newSize; i++) {
            initBucket(i); // 失敗不影響，下次訪問會重試
        }
    }
    // 失敗者不執行擴容，繼續正常操作 (新 size 已生效)
}

關鍵優化細節

• 分塊懶惰初始化：桶數組大固定 (如 2^20)，但只初始化訪問過的桶，避免啟動時大量分配。
• LongAdder 計數：高併發下優於 AtomicLong，減少緩存行爭用。
• Unsafe.compareAndSwapObject：直接操作 `value` 字段偏移量，避免 `AtomicReference` 開銷 (JDK 9+ 用 `VarHandle`)。
• 迭代器弱一致性：遍歷時不加鎖，允許並發修改，可能看見部分更新。

與 ConcurrentHashMap (JDK 8+) 對比

為什麼 JDK 沒有內置無鎖 HashMap？

1. ABA 問題：CAS 重試時節點可能被刪除又重新分配相同地址，需 Hazard Pointer/Epoch GC 解決，JVM 無內置支持。
2. 內存回收極難：無鎖結構無法確定何時安全釋放節點內存，Java 依賴 GC，但 GC 不感知無鎖邏輯。
3. 工程收益比：CHM 已經足夠快，無鎖帶來的吞吐提升在大多數業務場景邊際效益遞減，不值得複雜度代價。
4. 調試/監控困難：無鎖結構狀態瞬息萬變，難以提供一致性快照視圖。

總結

無鎖 HashMap 是並發數據結構的「珠穆朗瑪峰」：CAS 單指針原子性 + 有序鏈表消除多指針移動 + 懶惰分塊初始化 + 哨兵節點分組。理解其設計精髓——將「移動節點」轉化為「插入哨兵」，是掌握無鎖編程精髓的關鍵。雖然生產環境首選 `ConcurrentHashMap`，但研究無鎖 HashMap 能深度理解 CAS、內存模型、無鎖同步、擴容協調等核心難題，為設計高性能無鎖隊列、跳表、B+樹打下堅實基礎。