JDK7 vs JDK8 的 HashMap 結構變化

在 JDK7 及更早版本，HashMap 采用 數組 + 鏈表 結構，當哈希沖突較多時，鏈表可能變得很長，導致查詢性能從 O(1) 退化到 O(n)。

在 JDK8，為了優化鏈表查詢性能，引入了紅黑樹：

• 仍然采用 數組 作為底層存儲。
• 當某個桶中的鏈表長度 超過 8，并且 table 的大小 ≥ 64 時，鏈表轉換為 紅黑樹。
• 這樣，在極端情況下，查詢性能從 O(n) 降低到O(log n)。

Java8 中哈希表的紅黑樹優化機制

從JDK8開始，為了優化哈希沖突情況下的查找性能，當哈希桶中的鏈表長度超過 8 時，鏈表會轉換為紅黑樹。紅黑樹是一種自平衡二叉搜索樹，將最壞情況下的查找復雜度從 O(n) 降低到 O(log n)。（如果沒引入紅黑樹，則最壞查找復雜度是O(n)）

當樹中元素數量低于 6 時，紅黑樹會退化回鏈表，以減少不必要的樹操作開銷，提高小規模數據場景下的性能。

HashMap 添加元素的完整流程解析

1. 計算 key 的哈希值并確定索引

• 通過 key.hashCode() 計算出哈希值。
• 采用 (哈希值 & (table.length - 1)) 計算索引，以確定 key 應該存放在 table 數組中的那個位置。

---

2. 檢查該索引位置是否已有元素

• 如果該索引位置為空（table[index] == null），說明當前 key 沒有發生哈希沖突，直接存入該位置，并檢查是否需要擴容。【在 HashMap 里，負載因子（loadFactor）默認值是 0.75，表示當元素個數達到 容量 * 0.75 時，就會觸發擴容】
• 如果該索引位置已有元素，說明發生了哈希沖突，進入下一步處理。

---

3. 處理哈希沖突

在索引位置已有元素的情況下，需要判斷該 key 是否已經存在：

• 如果 key 與已有節點的 key 相同，說明是更新操作，直接替換 value。
• 如果 key 不同，說明該索引位置是個鏈表或紅黑樹，需要進一步處理。

---

4. 判斷當前存儲結構（鏈表還是紅黑樹）

• 如果該索引處存儲的是紅黑樹，按照紅黑樹的插入規則執行插入操作，流程結束。
• 如果是鏈表，則遍歷鏈表：
  • 如果鏈表中存在相同的 key，則更新 value，流程結束。
  • 如果鏈表中沒有相同 key，則在鏈表末尾插入新節點，并繼續下一步處理。

---

5. 判斷鏈表長度是否超過 8

• 如果鏈表長度 ≤ 8，不做額外處理。
• 如果鏈表長度 > 8，則需要判斷是否轉換為紅黑樹：
  • 如果 table 長度 >= 64，則將鏈表轉換為紅黑樹，流程結束。
  • 如果 table 長度 < 64，則不轉換為紅黑樹，而是觸發擴容（見步驟 7）。

---

6. 觸發擴容的判斷

在完成插入后，需要判斷是否需要擴容：

• size >= 閾值（threshold = table.length * 0.75） 時觸發擴容。
• 擴容是基于整個 HashMap 的大小，而不是單個鏈表的長度，即使單個鏈表過長，也不會單獨擴容，而是考慮整體 size。

---

7. 進行擴容

• 擴容策略：table 容量翻倍（如 16 → 32，32 → 64）。
• 調整擴容閾值：新閾值 = 新容量 * 0.75。
• 重新計算 key 的索引：
  • 由于 table.length 發生變化，所有 key 需要重新計算索引并遷移到新的 table。
  • HashMap 采用高位 & 低位拆分的方式優化了 rehash 過程，使得某些 key 的新索引保持不變，而另一些 key 需要移動到新位置。

---

8. 遷移元素

• 舊 table 的數據逐個遷移到新 table。
• 遷移規則：
  • 計算 oldIndex = hash & (oldCapacity - 1)，newIndex = hash & (newCapacity - 1)。
  • 低位不變，高位索引變化，減少數據遷移的計算量。

流程圖

---

補充

HashMap 的初始容量與負載因子優化

HashMap 的默認初始容量為 16，負載因子為 0.75，這一組合在性能與空間之間取得了平衡。較高的負載因子（如 1.0）可減少空間浪費，但會增加哈希沖突的概率；較低的負載因子則減少哈希沖突，但會增加內存開銷。 （如果可預估 HashMap 的存儲需求，建議提前設置合適的初始容量，以減少動態擴容帶來的性能損耗。）

?覺得有用的可以留個關注~~?