一、前言

結論：并發場景下，CHM 是唯一“能扛流量又能打”的哈希表實現。

二、數據結構演進史

1. JDK 1.5 分段鎖（Segment）16 個可重入鎖，理論并發度 16。
2. JDK 1.8 桶級鎖 + CAS拋棄 Segment，直接 synchronized 鎖單個首節點，沖突時才加鎖；擴容時多線程協同遷移，CPU 利用率拉滿。

三、JDK 1.8 核心成員變量速覽

// 位標識
staticfinalint MOVED     = -1; // ForwardingNode
staticfinalint TREEBIN   = -2; // 紅黑樹根
staticfinalint RESERVED  = -3; // computeIfAbsent 占位

transientvolatile Node<K,V>[] table;      // 主哈希桶
privatetransientvolatile Node<K,V>[] nextTable; // 擴容目標數組
privatetransientvolatilelong baseCount; // 無沖突時直接累加
privatetransientvolatileint sizeCtl;    // 控制標識：負數=正在擴容/-1=初始化/n=擴容閾值

四、put 流程（含并發控制）

1. 空表首次初始化通過 CAS 將 sizeCtl 從 0 改為 -1，單線程建表，其余線程 Thread.yield() 自旋等待。
2. 計算哈希spread(key.hashCode()) 再散列，減少哈希碰撞。
3. 定位桶(n - 1) & hash，與 HashMap 一致。
4. 桶為空CAS 插入新節點，失敗則自旋。
5. 桶非空首節點 hash == MOVED → 幫忙擴容 (helpTransfer)。否則 synchronized 鎖定首節點，再按鏈表/紅黑樹邏輯插入或更新。
6. 計數 + 檢查擴容addCount(1L, binCount)，若超過 sizeCtl 則觸發 transfer。

五、get 流程——全程無鎖

1. 計算哈希定位桶。
2. 首節點匹配直接返回。
3. 紅黑樹則按樹查找；鏈表順序遍歷。
4. 遇到 ForwardingNode 去 nextTable 重新查找。

可見性保障：Node.val 用 volatile 修飾；擴容時舊表只讀，新表發布前通過 Unsafe 的 volatile 寫保證。

六、擴容（transfer）——多線程協同搬運

1. 步長 stride根據 CPU 核數計算每次遷移的桶數（最小 16），減少競爭。
2. 全局進度索引 transferIndex從高位往低位分配任務包，CAS 搶占。
3. 搬運算法對單個桶加 synchronized，構建新鏈表/樹，插入到新表，舊桶頭插 ForwardingNode 占位。
4. 幫助擴容插入時發現 MOVED，當前線程領取stride步任務，加快遷移。

七、線程安全計數器

• baseCount：無競爭時直接累加。
• **CounterCell[]**：高并發時分散到數組，類似 LongAdder，最終 sumCount() 匯總。

八、紅黑樹與鏈表互轉閾值

九、實戰踩坑指南

1. 復合操作非原子

if (!map.containsKey(k)) map.put(k, v); // 仍有競態

正確姿勢：putIfAbsent(k, v) 或 computeIfAbsent。

1. 遍歷一致性Iterator 弱一致性：創建后其他線程增刪改不拋 ConcurrentModificationException，但未必可見。
2. 自定義對象作為 key必須保證不可變且正確實現 hashCode/equals，否則擴容前后定位桶不一致導致“幽靈丟失”。
3. 批量操作forEach、search、reduce 支持并行化，可指定 parallelismThreshold，在大數據量場景比串行循環快 2~3 倍。

十、性能壓測對比（1.8 vs 1.7 vs Hashtable）

測試場景：32 線程，各執行 1 千萬次 put。

結論：1.8 桶級鎖 + 協同擴容，比 1.7 分段鎖再提 45%+。

十一、面試高頻追問

1. 為什么 1.8 放棄 Segment？粒度太粗，且維護 16 個數組指針占用內存；桶級鎖已能滿足極高并發。
2. synchronized 性能差？1.8 對 synchronized 做了大量偏向鎖/輕量鎖優化，鎖定時間極短（僅鏈表/樹操作），CAS 失敗概率低。
3. CAS 自旋浪費 CPU？僅在空桶寫入失敗時自旋，沖突概率極低；擴容幫忙機制反而提升吞吐。
4. 與 ConcurrentSkipListMap 區別？后者基于跳表，保證有序但 O(log n)；CHM 無序 O(1)，并發度更高。