Java HashMap 工作原理深度解析：從哈希桶到擴容機制的面試必考核心

HashMap 核心原理：Hashing + 鏈表/紅黑樹

HashMap 基於 哈希表 實現，核心操作：

• put(key, value)：計算 key.hashCode() → 定位桶位置 → 儲存 Entry<K,V> (含 key、value、hash、next)
• get(key)：同樣計算 hash 定位桶 → 遍歷鏈表/樹 → 呼叫 key.equals() 比對 → 找到返回 value

關鍵認知：桶中儲存的是 鍵值對 Entry 物件，而非單純 value。這是理解碰撞處理與 get 邏輯的前提。

哈希碰撞與解決機制

碰撞發生條件

兩個不同 Key 的 hashCode() 相同，或計算桶索引後落在同一位置。HashMap 採用 鏈地址法：同桶位置以單向鏈表串連（JDK 8+ 鏈表長度 > 8 且陣列長度 > 64 時轉紅黑樹）。

get 過程中的 equals 比對

// 簡化邏輯
Node<K,V> e = table[index];
while (e != null) {
    if (e.hash == hash && (e.key == key || key.equals(e.key))) {
        return e.value;
    }
    e = e.next;
}

先比 hash 再比 equals()，雙重保險定位精確 Entry。

擴容機制：Rehashing 與併發風險

觸發條件

預設負載因子 loadFactor = 0.75，當 size > threshold (capacity * loadFactor) 時觸發擴容，容量翻倍（2 的冪次）。

Rehashing 過程

1. 建立新陣列 newTable = new Node[newCapacity]
2. 遍歷舊陣列每個桶的鏈表/樹
3. 重新計算每個 Entry 的桶索引：newIndex = (newCapacity - 1) & hash
4. 將 Entry 遷移至新桶（**頭插法**，順序反轉）

多執行緒下的 Race Condition

若兩執行緒同時發現需擴容，並發執行遷移，**頭插法導致鏈表成環**，後續 get/put 進入無限迴圈，CPU 100%。結論：HashMap 非執行緒安全，多執行緒環境必須用 ConcurrentHashMap 或 Collections.synchronizedMap()。

Key 設計最佳實踐

1. 用不可變物件：String、Integer、Long 等 final 類別，hashCode() 可快取，效能最佳
2. 正確重寫 hashCode() 與 equals()：equals() 相等 → hashCode() 必相等；反之不一定
3. 避免可變物件作 Key：放入後修改 Key 內部狀態導致 hash 改變，會找不到原 Entry
4. 自訂類別建議：所有參與 equals() 的欄位皆為 final，或放入 Map 後不再修改

常見面試追問與回答要點

原理圖解摘要

put("key", "value")
    │
    ▼
hashCode() → 計算索引 → table[index]
    │                    │
    │              ┌─────┴─────┐
    │              ▼           ▼
    │         鏈表/樹      新建 Node
    │              │
    ▼         equals() 比對
找到/未找到 → 更新/插入