HashMap 和 ConcurrentHashMap 是 Java 中用于存儲鍵值對（Key-Value）的哈希表實現，但前者是非線程安全的，后者是線程安全的，且兩者的底層原理和設計目標有顯著差異。以下從數據結構、核心機制、線程安全（僅 ConcurrentHashMap） 三個維度詳細解析。

一、HashMap 原理（非線程安全，JDK 1.8+）

1. 底層數據結構

• 數組（哈希桶，Node[] table）：數組的每個元素稱為 “桶”，用于存儲鍵值對的首節點。數組長度（容量，capacity）默認是 16，且始終保持為 2 的冪次方（如 16、32、64...），這是為了通過位運算快速計算元素位置。
• 鏈表（Node 節點）：當多個鍵的哈希值映射到同一個桶時，會形成鏈表（解決哈希沖突）。每個 Node 包含 hash（鍵的哈希值）、key、value、next（下一個節點引用）。
• 紅黑樹（TreeNode 節點）：當鏈表長度超過閾值（默認 8），且數組容量 ≥ 64 時，鏈表會轉為紅黑樹（一種自平衡二叉查找樹）。紅黑樹的查詢時間復雜度為 O (log n)，遠優于鏈表的 O (n)，可優化大量哈希沖突時的查詢效率。

2. 核心機制

（1）哈希值計算與索引定位

1. 計算鍵的哈希值：int hash = hash(key)，其中 hash(key) 是對 key.hashCode() 的二次哈希（通過高位異或低位，減少哈希沖突）：
    

   static final int hash(Object key) {
       int h;
       // key為null時hash為0；否則用hashCode的高16位異或低16位，增強哈希散列性
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }
   

    
    
2. 計算數組索引：int index = (n - 1) & hash，其中 n 是數組容量（table.length）。由于 n 是 2 的冪次方，n-1 的二進制全為 1（如 16-1=15 → 1111），& 運算等價于取模（hash % n），但效率更高。

（2）put 方法流程（核心操作）

1. 若數組 table 未初始化或長度為 0，先觸發擴容（resize()）。
2. 計算 key 的 hash 和 index，檢查索引 index 處的桶是否為空：
   • 若為空，直接創建 Node 插入（table[index] = newNode(hash, key, value, null)）。
   • 若不為空（哈希沖突）：
     • 若桶的首節點與 key 相同（hash 相等且 key.equals() 為 true），直接替換 value。
     • 若首節點是紅黑樹節點（TreeNode），調用樹的插入方法（putTreeVal）。
     • 若首節點是鏈表節點，遍歷鏈表：
       • 若找到相同 key，替換 value；
       • 若未找到，在鏈表尾部插入新節點，插入后若鏈表長度 ≥ 8，觸發鏈表轉紅黑樹（treeifyBin）。
3. 插入后若元素數量（size）超過閾值（threshold = capacity * loadFactor，默認負載因子 loadFactor=0.75），觸發擴容（resize()）。

（3）擴容機制（resize ()）

1. 計算新容量：newCap = oldCap << 1（原容量 × 2，保持 2 的冪次方）。
2. 創建新數組（newTable），容量為 newCap。
3. 將原數組（oldTable）中的元素遷移到新數組：
   • 對于鏈表 / 紅黑樹中的每個節點，重新計算在新數組中的索引（因 newCap 是原容量的 2 倍，新索引要么是原索引，要么是 原索引 + oldCap，無需重新計算 hash，通過 hash & oldCap 判斷高位是否為 1 即可）。
   • 若原節點是鏈表，遷移時可能拆分鏈表為兩個子鏈表（分別對應新索引的兩個位置）；若原節點是紅黑樹，遷移后可能退化為鏈表（若元素數量 < 6）。
4. 替換 table 為 newTable，更新閾值（newThr = newCap * loadFactor）。

（4）線程不安全的原因

• 擴容死循環（JDK 1.7 及之前）：多線程同時擴容時，鏈表遷移可能形成環形鏈表，導致后續查詢時無限循環。
• 數據丟失：多線程同時 put 時，可能覆蓋彼此的插入結果。
• 數據不一致：size 計數未加鎖，可能導致統計結果錯誤。

二、ConcurrentHashMap 原理（線程安全，JDK 1.8+）

1. 底層數據結構（JDK 1.8+）

2. 核心機制（線程安全的關鍵）

（1）線程安全實現：CAS + synchronized

• CAS（Compare-And-Swap）：對于未初始化的桶（table[index] == null），通過 CAS 原子操作嘗試插入新節點（casTabAt 方法），避免加鎖。
• synchronized 鎖：若 CAS 失敗（桶已被其他線程占用，存在哈希沖突），則對桶的首節點（table[index]）加 synchronized 鎖，僅鎖定當前沖突的桶，其他桶仍可被并發訪問，鎖粒度更細。

（2）put 方法流程（線程安全版）

1. 計算 key 的 hash（與 HashMap 相同），若數組未初始化，先通過 CAS 初始化（initTable）。
2. 定位索引 index，檢查桶是否為空：
   • 若為空，通過 casTabAt 方法（CAS）嘗試插入新節點，成功則返回；失敗（被其他線程搶先插入）則重試。
   • 若不為空（存在哈希沖突）：
     • 若桶的首節點是 MOVED 狀態（正在擴容），當前線程協助擴容（helpTransfer），避免擴容線程負載過重。
     • 否則，對首節點加 synchronized 鎖，遍歷鏈表 / 紅黑樹：
       • 若找到相同 key，替換 value（通過 cas 保證原子性）。
       • 若未找到，插入新節點（鏈表尾部或紅黑樹），插入后檢查是否需要轉紅黑樹。
3. 插入后更新 size（通過 addCount 方法，CAS 累加，超過閾值則觸發擴容）。

（3）擴容機制（多線程協同擴容）

1. 當 size 超過閾值時，由某個線程發起擴容（transfer 方法），將數組容量翻倍。
2. 擴容時，原數組（oldTab）被分為多個段，每個線程負責遷移一段（通過 stride 控制，默認每個線程處理 16 個桶）。
3. 其他線程執行 put/get 時，若發現正在擴容（桶的首節點為 MOVED），會協助遷移當前桶的元素，加速擴容過程。
4. 遷移邏輯與 HashMap 類似（新索引 = 原索引 或 原索引 + oldCap），但通過 CAS 標記遷移狀態，避免沖突。

（4）get 方法（無鎖，高效）

• 節點的 value 用 volatile 修飾，保證多線程間的可見性（修改后立即刷新到主內存，讀取時從主內存加載）。
• 紅黑樹的結構修改（如插入、刪除）通過 synchronized 鎖保證原子性，讀取時無需鎖即可獲取最新結構。

3. JDK 1.7 與 1.8 的區別（補充）

三、HashMap 與 ConcurrentHashMap 的核心區別

總結

• HashMap 是單線程場景下的高效哈希表，底層為 “數組 + 鏈表 + 紅黑樹”，通過哈希散列和擴容減少沖突，非線程安全。
• ConcurrentHashMap 是多線程場景下的線程安全實現，JDK 1.8 用 “CAS + synchronized” 保證安全，鎖粒度細，并發性能優異，底層結構與 HashMap 類似，但不支持 null 鍵值，迭代器為弱一致性。