我們來用通俗易懂的方式解釋一下 Java 8 中 HashMap 的原理，讓你對它的結構、運行機制有清晰的理解。

---

🌳 什么是 HashMap？

HashMap 是 Java 中非常常用的數據結構，用于存儲鍵值對（key-value）。你可以把它理解成一個“大數組”，每個位置可以存儲一個或多個數據。

---

🧱 HashMap 的基本結構

Java 8 中的 HashMap 底層由 數組 + 鏈表 + 紅黑樹 組成：

HashMap└── 數組 table[]     ← 每個元素稱為“桶”├── 鏈表/樹    ← 存儲實際的 key-value 節點（Node）

---

🛠? 核心工作流程

我們來一步步看 HashMap 是怎么工作的：

---

? 插入 put(key, value)

舉個例子：

map.put("apple", 100);

背后做了這些事：

1. 計算 hash 值：

   • 對 key（“apple”）調用 hashCode()，然后做了一些擾動處理。
   • 比如 "apple".hashCode() = 93029210，經過擾動后變成一個新的 hash 值。

2. 計算數組索引：

   • index = hash & (table.length - 1)，定位到數組的某一桶。

3. 判斷該桶是否有元素：

   • 如果沒有：直接放進去。

   • 如果有：判斷 key 是否相同。

     • 相同：替換舊值。
     • 不同：鏈表/紅黑樹追加新節點。

4. 鏈表轉紅黑樹（Java8 新特性）：

   • 當同一個桶內元素數量超過 8 個 且數組長度超過 64，會把鏈表轉成紅黑樹，提高查詢效率。

---

🔍 查詢 get(key)

比如：

map.get("apple");

1. 計算 hash。

2. 定位到數組索引。

3. 在對應的桶里找：

   • 是鏈表：順序比較 key。
   • 是紅黑樹：用樹的方式查找。

---

🔄 發生了哈希沖突怎么辦？

多個不同的 key 計算后可能落到同一個數組位置（桶），這就叫 哈希沖突。Java 8 中：

• 前幾個沖突的 key 用 鏈表 掛在一起；
• 如果沖突太多（鏈表長度 > 8 且數組長度 > 64），鏈表就會轉成 紅黑樹，加快查找速度。

---

📈 擴容機制

HashMap 的默認容量是 16，裝載因子是 0.75，當元素數量 > 16 * 0.75 = 12 時，就會發生 擴容：

1. 擴容為原來容量的 2 倍。
2. 重新計算所有 key 的 hash 值和位置，遷移元素。

這也是為什么我們建議在使用 HashMap 時 預估容量大小，以避免多次擴容影響性能。

---

🧠 為什么要用紅黑樹？

因為鏈表查找是 O(n)，而紅黑樹是 O(log n)，當沖突嚴重時，查詢效率會大幅下降。引入紅黑樹可以在極端情況下保持較好的性能。

---

🔥 小結圖示：

插入：hash → 定位數組桶 → 空就放，有就比較 → 鏈表 / 紅黑樹
查詢：hash → 定位 → 鏈表/樹中查找 key
擴容：元素太多 → 數組翻倍 → 元素重新分布

---

? Java 8 中 HashMap 的優點

特性	優點說明
引入紅黑樹	避免鏈表過長導致查找變慢
擾動函數優化	減少哈希沖突，分布更均勻
結構清晰	數組 + 鏈表 + 紅黑樹，靈活擴展

---

我們來用通俗易懂的語言 + 舉例方式，深入講講 Java 8 中 HashMap 的 擾動函數（hash 擾動函數），幫助你真正理解它的作用和原理。

---

一、什么是擾動函數？

? 定義一句話：

擾動函數是為了讓 hash 值的高位信息也能參與數組下標的計算，從而讓 key 更均勻地分布在 HashMap 的數組中。

---

二、為什么需要擾動函數？

🚨 問題：低位碰撞嚴重！

在 HashMap 中，定位數組下標的方式是這樣的：

index = hash(key) & (table.length - 1)

由于 table.length 是 2 的冪，這樣的 & 操作會只保留 hash 值的低位。

?? 如果兩個 key 的 hash 值只有高位不同，而低位相同，它們就會落入同一個桶（發生沖突）。

🧠 舉個例子：

hash1 = 0b10110000_00000000_00000000_00000001
hash2 = 0b01010000_00000000_00000000_00000001

雖然高位差很多，但最后的幾位一樣。由于我們只用低位參與數組下標計算，這兩個 key 會落在同一個位置！

? 解決方案：擾動函數

通過擾動函數把 高位信息混合到低位，避免沖突更均勻。

---

三、Java 8 中的擾動函數源碼分析

HashMap 中源碼如下（簡化）：

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

🚀 解釋：

• h = key.hashCode()：拿到 key 的原始 hashCode（32 位整數）。
• h >>> 16：無符號右移 16 位，把高位移動到低位。
• ^：做異或運算，把原來的高位和低位混合起來，讓高位也參與到最終結果中。

---

四、通俗舉例講解

假設我們有兩個 key：

key1.hashCode() = 0b10110000_00000000_00000000_00000001
key2.hashCode() = 0b01010000_00000000_00000000_00000001

它們的低位是一樣的，都會落到相同數組位置，發生 hash 沖突。

有了擾動函數：

擾動結果 = h ^ (h >>> 16)

擾動后：

• key1 的高位會被移到低位并參與混合；
• 即便低位一樣，只要高位不同，擾動后結果就不一樣。

這樣就打亂了 hashCode 的原始規律，使得分布更隨機，降低 hash 沖突概率。

---

五、總結（口訣記憶）

• 🚩 低位計算索引，高位白白浪費。
• 🧠 擾動函數混高低，分布均勻更合理。
• ? 異或右移搞起來，沖突少，效率高。

---

六、動手試一試（簡單代碼示例）

public class HashDisturbExample {public static void main(String[] args) {String key = "apple";int h = key.hashCode();int disturbed = h ^ (h >>> 16);System.out.println("原始 hashCode: " + h);System.out.println("擾動后結果:     " + disturbed);}
}

運行后你會看到兩個不同的值，這說明擾動函數確實改變了 hash 值結構，幫助分布更均勻。

---

? 第一個問題：為什么 table.length 是 2 的冪？

🔧 原因：

為了 優化取模（mod）操作為位運算（&）操作，提升性能！

🧠 解釋：

在 HashMap 中，我們要根據 key 的 hash 值決定存放的位置，也就是數組下標：

index = hash(key) % table.length

如果 table.length 是任意數字，比如 10，那就必須使用 除法運算 %，這是一個比較慢的操作。

而如果 table.length 是 2 的冪，比如 16、32、64，我們就可以寫成：

index = hash(key) & (table.length - 1)

?? 這行代碼的效果和 % 是一樣的，但效率更高！

🧠 舉例說明：

假設 table.length = 16（即 2?），那么 16 的二進制是：

16 = 10000（即 2 的 4 次方）
16 - 1 = 15 = 01111（二進制）

這樣做 & 15 相當于取 hash 值的 低 4 位，效果等同于 hash % 16，而且更快！

---

? 第二個問題：為什么 & 的操作和 % 是一樣的？

🎯 只有在 table.length 是 2 的冪時，才成立！

hash % 16 == hash & (16 - 1)

這是因為 2 的冪次減 1 得到的是全 1 的二進制位數。比如：

table.length	二進制	table.length - 1	二進制
8	1000	7	0111
16	10000	15	01111
32	100000	31	011111

當你對一個數 x 執行 x & (n - 1)，就等于 取 x 的低幾位，這等價于 x % n（當 n 是 2 的冪時）。

? 舉個例子：

hash = 0b101010        // 十進制 42
table.length = 16      // 2?
mask = 16 - 1 = 15 = 0b111142 % 16 = 10
42 & 15 = 0b101010 & 0b1111 = 0b1010 = 10 ?

結果一樣，但是 & 運算效率遠高于 % 運算。

---

? 第三個問題：為什么是“低位”參與運算？

📌 因為 hash & (table.length - 1) 只保留 低位信息！

你剛剛也看到了，舉個例子：

hash = 0b10110000_00000000_00000000_00001101
table.length = 16 (即 2?)，mask = 0b00000000_00000000_00000000_00001111

執行 &：

hash & mask =
0b10110000_00000000_00000000_00001101
&
0b00000000_00000000_00000000_00001111
=
0b00000000_00000000_00000000_00001101 => 13

?? 所以只有 低 4 位被保留下來，高位被舍棄了！

---

🤔 那高位的 hash 值不是白計算了嗎？

是的，如果不做處理，高位信息就浪費了，這就是為啥我們需要：

🚀 擾動函數：h ^ (h >>> 16)

它會把高 16 位的信息也混入低 16 位中，確保高位不會被浪費。

---

? 總結歸納：

問題	解答
為什么 table.length 是 2 的冪？	為了將取模 % 優化成更快的 & 位運算。
為什么 & 可以代替 %？	當除數是 2 的冪時，x & (n - 1) 等價于 x % n，而效率更高。
為什么是低位參與？	因為 & 操作只保留了低位的信息（如 & 15 保留低 4 位），高位信息被忽略。

---

🧠 為什么要擴容？

HashMap 是通過數組 + 鏈表（或紅黑樹）來存儲鍵值對的。它的性能依賴于：

鍵值對在數組中的分布是否均勻（沖突少）

如果 HashMap 存放的元素太多，沖突越來越多，鏈表變長，性能會急劇下降，所以需要：

擴容（resize）：將原數組變大，把原來的元素“重新分布”到新的數組中。

---

?? HashMap 擴容時機

HashMap 會在滿足以下條件時擴容：

當前元素個數 > 閾值（threshold） = 容量 × 負載因子（loadFactor）

• 默認初始容量是 16
• 默認負載因子是 0.75
• 所以默認第一次擴容是在元素數量超過 16 × 0.75 = 12 時發生

---

🚀 擴容做了什么？

當發生擴容時，HashMap 會做幾件事：

1. 將數組容量擴大為 原來的兩倍
2. 創建一個新的數組（新的 table）
3. 重新計算每個鍵值對的索引（index）
4. 將所有舊元素 “搬家” 到新數組中

---

📊 舉個例子來說明

假設你有一個容量為 4 的 HashMap，插入了 3 個元素（已接近 0.75 的閾值）：

原數組（長度4）：
index 0: [A -> 1]
index 1: [B -> 2]
index 2: [C -> 3]
index 3: null

你再插入一個元素 D -> 4，此時元素數目為 4，超過 4 × 0.75 = 3，觸發擴容。

擴容過程：

• 數組變為長度 8
• 所有鍵的 hash 會重新計算 index
• 每個鍵值對會根據新的 index 放到新數組中，分布更均勻

擴容后數組（長度8）：
index 0: null
index 1: [A -> 1]
index 2: null
index 3: [C -> 3]
index 4: null
index 5: [B -> 2]
index 6: [D -> 4]
index 7: null

這樣就避免了原來在小數組中“擁擠”的問題。

---

🔁 元素“搬家”的優化：位運算重分布

Java 8 做了一個優化，在擴容時 不再重新計算 hash 值，而是通過如下邏輯判斷元素是留在原位置還是移動到“新位置”：

// 假設 oldCap 是原數組長度，newCap = oldCap * 2
if ((e.hash & oldCap) == 0) {// 留在原地
} else {// 移動到原位置 + oldCap
}

這個技巧利用了 2 的冪次 的特性，通過 hash & oldCap 直接判斷是否需要挪動，提高了效率！

---

💡 為什么擴容不是一開始就做得很大？

為了節省內存。HashMap 的容量和負載因子設計是為了在性能和內存之間做權衡。

---

? 總結：HashMap 擴容機制

步驟	內容
擴容時機	元素個數 > 閾值（容量 × 負載因子）
擴容操作	數組變為原來的兩倍
元素處理	每個元素根據新數組重新定位（高效位運算）
優化手段	hash & oldCap 判斷是否搬家
目的	降低 hash 沖突，提高查詢性能