深入解析 Java HashMap 核心原理與源碼實現

HashMap 整體結構概覽

HashMap 是 Java 集合框架中最常用的鍵值對存儲結構。其底層採用數組 + 鏈表的方式實現：數組稱為「哈希桶」，每個桶中儲存一個單向鏈表，鏈表節點為 Map.Entry 對象，封裝了 Key-Value 鍵值對。當多個鍵經過哈希函數計算後落入同一個桶時，會發生「哈希衝突」，此時便通過鏈表串聯解決。

核心屬性與構造器

查看 JDK 1.6 源碼，HashMap 定義了以下關鍵字段：

• DEFAULT_INITIAL_CAPACITY = 16：默認初始容量（必須是 2 的冪）
• MAXIMUM_CAPACITY = 1 << 30：最大容量上限
• DEFAULT_LOAD_FACTOR = 0.75f：默認負載因子
• threshold：擴容閾值 = capacity × loadFactor
• table：儲存 Entry 的數組
• size：當前鍵值對數量

構造器中會將傳入的 initialCapacity 向上取整為 2 的冪，並計算 threshold。例如默認情況下：16 × 0.75 = 12，當元素數量超過 12 時觸發擴容（rehash）。

關鍵方法源碼解讀

1. hash() 方法——擾動函數

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

此方法對 key.hashCode() 進行二次擾動，將高位信息混合到低位，減少哈希衝突，使數據在桶中分佈更均勻。

2. indexFor() 方法——桶索引定位

static int indexFor(int h, int length) {
    return h & (length - 1);  // length 為 2 的冪，等價於 h % length 但效率更高
}

3. get() 方法流程

1. 若 key 為 null，直接檢索 table[0] 鏈表
2. 計算 hash 值，定位桶索引
3. 遍歷該桶鏈表，比對 hash 值與 key（使用 == 或 equals()）
4. 命中返回 value，否則返回 null

4. put() 方法流程

1. key 為 null 時調用 putForNullKey()，固定放入 table[0]
2. 非 null key：計算 hash、定位桶、遍歷鏈表
3. 若發現相同 key（hash 相等且 key.equals()），替換舊值並返回舊值
4. 否則創建新 Entry，插入鏈表頭部（JDK 1.6 為頭插法），size++，檢查是否需擴容

負載因子與擴容機制

負載因子衡量數組使用程度，默認 0.75 是時間與空間的折中。擴容時會創建兩倍大小的新數組，並將所有 Entry 重新計算索引遷移，這是耗時操作，故預估數據量時應適當設定初始容量。

為何基本類型不能直接作 Key？

HashMap 僅接受對象引用。基本類型需使用包裝類（如 Integer、Long），否則無法調用 hashCode() 與 equals()。此外，null key 固定映射到 hash 0（即 table[0]）。

transient 關鍵字說明

transient Entry[] table 表示該字段不參與序列化。HashMap 實現了自定義的 writeObject/readObject，序列化時僅保存 size、鍵值對數據，反序列化時重建 table，避免序列化整個稀疏數組。