深度解析 Java HashMap 核心原理：從數據結構到擴容機制全景圖

前言

HashMap 是 Java 面試與日常開發最高頻的集合類。本文從數據結構、存取流程、哈希算法、擴容機制、性能參數、Fail-Fast 機制六大維度，結合 JDK 8 源碼（註：文中源碼為 JDK 7 風格，原理一致）深度剖析其內部運作，助你徹底掌握這把「鑰匙」。

一、 核心數據結構：數組 + 鏈表 (+ 紅黑樹 JDK 8)

transient Entry<K,V>[] table 是底層數組，每個槽位是一個 Entry 鏈表頭節點。

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;      // 指向下一個節點，形成鏈表
    final int hash;      // 緩存 key 的 hash 值
    // ...
}

JDK 8 引入紅黑樹：當鏈表長度 ≥ 8 且數組長度 ≥ 64 時轉為樹，查詢複雜度從 O(n) 降為 O(log n)。

二、 存儲流程

1. key == null → 處理為 putForNullKey，固定放索引 0。
2. 計算 hash = hash(key.hashCode())（二次哈希，見下節）。
3. index = indexFor(hash, table.length) 定位槽位。
4. 遍歷鏈表：e.hash == hash && (e.key == key || key.equals(e.key)) → 覆蓋值，返回舊值。
5. 無匹配 → addEntry(hash, key, value, index) 頭插法插入新節點。
6. size 超過 threshold → resize(2 * table.length) 擴容。

三、 關鍵哈希算法

1. 二次哈希

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

將高位信息混合到低位，減少哈希碰撞，尤其針對 hashCode() 只有低位變化的 key（如 Integer）。

2. 索引計算：位運算代替取模

static int indexFor(int h, int length) {
    return h & (length - 1);   // length 必須是 2 的 n 次冪
}

為什麼 length 必須是 2 的冪？

• length - 1 二進制全為 1，h & (length-1) 等價於 h % length，但位運算極快。
• 若 length 非 2 的冪（如 15），length-1 末位為 0，導致最後一位永遠為 0，浪費一半槽位，碰撞率飆升。

四、 擴容與 Rehash

• 觸發條件：size >= threshold = capacity * loadFactor（默認 0.75）。
• 新容量 = 舊容量 × 2（保持 2 的冪）。
• 重新計算每個節點在新數組的索引（e.hash & (newCap-1)），遷移數據——極其消耗 CPU。
• 最佳實踐：預估數據量，構造時指定 initialCapacity 避免多次擴容。

五、 性能參數詳解

• initialCapacity：底層數組長度，會自動調整為 ≥ 該值的最小 2 的冪。
• loadFactor：空間換時間權衡。過大（>0.75）碰撞多、查詢慢；過小（<0.5）記憶體浪費。0.75 是實踐平衡點。
• threshold = (int)(capacity * loadFactor)：觸發擴容的元素數量上限。

六、 Fail-Fast 機制

• modCount 記錄結構性修改次數（put、remove、clear）。
• 迭代器創建時快照 expectedModCount = modCount。
• 迭代過程中檢測 modCount != expectedModCount → 拋出 ConcurrentModificationException。
• 注意：僅用於檢測程式 bug，不能用於並發控制。多線程環境請用 ConcurrentHashMap 或 Collections.synchronizedMap。

七、 總結圖譜

put(key, value)
   │
   ├─ key==null → table[0]
   │
   ├─ hash(key.hashCode()) → 二次哈希
   │
   ├─ indexFor(hash, length) → h & (n-1)
   │
   ├─ 遍歷鏈表/紅黑樹
   │    ├─ key 相等 → 覆蓋 value
   │    └─ 無匹配 → 頭插法新增 Entry
   │
   └─ size++ ≥ threshold → resize(2×) → rehash 所有節點

最佳實踐清單

1. 預估數據量，new HashMap<>(預估尺寸 / 0.75f + 1)。
2. Key 類正確重寫 hashCode() 與 equals()，保證一致性契約。
3. 避免在多線程寫入場景直接使用 HashMap。
4. 頻繁遍歷場景考慮 entrySet() 而非 keySet() + get()。