HashMap 核心原理與源碼深度解析：從存儲結構到擴容機制

概述

HashMap 是 Java 集合框架中使用頻率最高的鍵值對容器，基於數組 + 鏈表（JDK 1.7）實現，採用拉鏈法解決哈希衝突。本文結合源碼（以 JDK 1.7 為基準，原理通用）深度剖析其核心字段、關鍵方法、擴容機制及迭代器設計，助你構建完整的內心模型。

一、 存儲結構與核心字段

圖中紫色區域為哈希表（Entry[] table），每個數組元素是一個單向鏈表的頭節點。當不同 key 經過哈希計算落到同一索引時，以鏈表形式存儲。

核心字段（節選自源碼）

// 默認初始容量 16，必須是 2 的冪次
static final int DEFAULT_INITIAL_CAPACITY = 16;
// 最大容量 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默認加載因子 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 存儲數據的 Entry 數組
transient Entry[] table;
// 實際鍵值對數量
transient int size;
// 擴容閾值 = capacity * loadFactor
int threshold;
// 加載因子
final float loadFactor;
// 修改次數，用於 fail-fast
transient volatile int modCount;

Entry 節點結構

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;  // 指向下一個節點
    final int hash;  // key 的哈希值緩存

    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v; next = n; key = k; hash = h;
    }
    // ... getKey, getValue, setValue, equals, hashCode 等
}

每個 Entry 保存 key、value、hash 及 next 指針，構成單向鏈表。hash 字段緩存鍵的哈希值，避免查找時重複計算。

二、 構造方法與初始化

HashMap 提供四個構造器，核心邏輯統一在 HashMap(int initialCapacity, float loadFactor) 中：

1. 參數校驗：容量非負、不超過最大值；加載因子 > 0 且非 NaN。
2. 容量規範化：將指定容量向上調整為最近的 2 的冪次（如 10 → 16），利用位運算 capacity <<= 1 實現。
3. 初始化閾值：threshold = (int)(capacity * loadFactor)。
4. 創建數組：table = new Entry[capacity]。

關鍵點：默認構造器不立即創建數組，而是延遲到首次 put 時（JDK 1.7 行為），但提供的源碼中直接初始化了默認大小數組。

三、 核心方法源碼解析

1. 哈希計算與索引定位

// 擾動函數：高位參與運算，降低衝突
static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

// 索引計算：位與運算替代取模，前提是 length 為 2 的冪次
static int indexFor(int h, int length) {
    return h & (length - 1);
}

hash() 經過多次右移異或，使高位信息混合到低位，配合 indexFor 的 & (length-1)，實現均勻分佈。

2. get(key) 獲取流程

public V get(Object key) {
    if (key == null) return getForNullKey(); // null key 固定放 table[0]
    int hash = hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    return null;
}

1. key 為 null 直接查 table[0] 鏈表。
2. 計算 hash → 定位索引 → 遍歷鏈表比較 hash 與 key.equals()。
3. 命中返回 value，否則返回 null。

3. put(key, value) 存放流程

public V put(K key, V value) {
    if (key == null) return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    // 1. 檢查鏈表中是否已存在相同 key
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue; // 覆蓋舊值
        }
    }
    // 2. 不存在則新增節點（頭插法）
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

addEntry 採用頭插法：新節點的 next 指向原頭節點，再將新節點置為數組該位置的新頭。插入後檢查 size >= threshold 觸發擴容。

4. 擴容機制 resize()

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable); // 重新哈希遷移
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null; // 幫助 GC
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity); // 重新計算索引
                e.next = newTable[i]; // 頭插法遷移
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

關鍵細節：

• 容量翻倍（2 * oldCapacity），保持 2 的冪次。
• transfer 遍歷舊數組，對每個節點重新計算索引（因 length 變化），頭插法放入新數組。
• 頭插法會導致鏈表順序反轉，多線程環境下可能產生環形鏈表（JDK 1.8 改為尾插法並引入紅黑樹優化）。

5. 刪除 remove(key)

本質是單向鏈表節點刪除：定位索引 → 遍歷鏈表找到目標節點 → 修改前驅節點的 next 指針跳過目標節點 → size--、modCount++。提供 removeEntryForKey 和 removeMapping 兩種入口。

四、 迭代器與 Fail-Fast 機制

HashMap 通過內部類 HashIterator 實現三種迭代器（KeyIterator、ValueIterator、EntryIterator）。

核心邏輯

private abstract class HashIterator<E> implements Iterator<E> {
    Entry<K,V> next;        // 下一個待返回節點
    int expectedModCount = modCount; // 快照
    int index;             // 當前數組索引
    Entry<K,V> current;    // 當前返回的節點

    HashIterator() {
        if (size > 0) {
            Entry[] t = table;
            while (index < t.length && (next = t[index++]) == null); // 找到第一個非空桶
        }
    }

    final Entry<K,V> nextEntry() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException(); // fail-fast
        Entry<K,V> e = next;
        if (e == null) throw new NoSuchElementException();
        // 移動到下一個節點：優先走鏈表 next，否則掃描數組下一個非空桶
        if ((next = e.next) == null) {
            Entry[] t = table;
            while (index < t.length && (next = t[index++]) == null);
        }
        current = e;
        return e;
    }
    // remove() 通過 current.key 調用 HashMap.removeEntryForKey，並同步 expectedModCount
}

遍歷順序：按數組索引從 0 到 length-1，每個桶內按鏈表順序（頭到尾）。

Fail-Fast：構造迭代器時拍攝 modCount 快照，每次 nextEntry() 檢查是否一致。若在迭代過程中結構性修改（put/remove/clear），modCount 變化拋出 ConcurrentModificationException。注意：iterator.remove() 會同步更新快照，是安全的刪除方式。

五、 序列化支持

HashMap 實現 Serializable，但 table 為 transient。自定義 writeObject/readObject：

• 寫入：先寫默認字段，再寫 table.length、size，最後遍歷 entrySet 依次寫入 key、value。
• 讀取：讀取默認字段、桶數量、size，創建新數組，循環讀取 key/value 調用 putForCreate 重建（不檢閲擴容、不增加 modCount）。

六、 關鍵設計總結

七、 面試高頻考點速記

• 為什麼容量必須是 2 的冪次？ 使 h & (length-1) 等價於取模，且分佈均勻。
• JDK 1.7 vs 1.8 差異？ 1.8 引入紅黑樹（鏈表長度 ≥ 8 且容量 ≥ 64 轉樹）、尾插法遷移、鏈表節點改為 Node/TreeNode、擴容優化（不重新計算 hash，用 (e.hash & oldCap) == 0 判斷留原位或移動）。
• HashMap 為什麼線程不安全？ 多線程並發 put 導致擴容時頭插法形成環形鏈表，get 陷入死循環；size 更新非原子；modCount 非 volatile 可見性問題。
• 如何自定義 Key？ 必須重寫 hashCode() 和 equals()，且滿足「相等對象 hashCode 相等」；Key 最好不可變（如 String、Integer）。

結語

深入理解 HashMap 源碼，不僅能應對面試，更能在實際開發中合理設置初始容量、加載因子，避免頻繁擴容與哈希衝突，寫出高性能代碼。建議對照 JDK 1.8 源碼對比學習，掌握紅黑樹優化與擴容遷移的新邏輯。