Java HashMap 源碼深度解析：佈局、擴容、Put/Get 流程與自定義 Key 最佳實踐

一、核心數據結構

transient Node<K,V>[] table; // 桶數組，長度為 2 的冪次
transient int size;            // 鍵值對數量
int threshold;                 // 擴容閾值 = capacity * loadFactor
final float loadFactor;        // 負載因子，默認 0.75f
transient int modCount;        // 結構修改次數，用於 fail-fast

Node 為單向鏈表節點（JDK 8+ 高桶轉紅黑樹）：int hash; K key; V value; Node<K,V> next;

二、構造函數鏈

public HashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); }
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0) throw new IllegalArgumentException();
    if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException();
    this.loadFactor = loadFactor;
    this.threshold = initialCapacity; // 延遲初始化，首次 put 時才創建 table
}

三、put(K, V) 核心流程

1. 延遲初始化：table == EMPTY_TABLE → inflateTable(threshold) 創建桶數組。
2. Key 為 null：直接調用 putForNullKey(value)，固定放入 table[0]。
3. 計算 hash：hash(key) → key.hashCode() ^ (h >>> 16)（高位混合，減少碰撞）。
4. 定位桶索引：index = (n - 1) & hash（n 為 2 的冪次，等價取模但更快）。
5. 遍歷鏈表/樹：比較 hash 與 key.equals(k)，找到則覆蓋舊值並返回舊值。
6. 新增節點：addEntry(hash, key, value, index) → 頭插法（JDK 7）或尾插法（JDK 8+）。
7. 擴容檢查：if (++size > threshold) resize(newCapacity)。

四、resize 擴容機制

void resize(int newCapacity) {
    Node[] oldTable = table;
    if (oldTable.length == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; }
    Node[] newTable = new Node[newCapacity];
    transfer(newTable); // 重新計算每個節點在新桶的位置並遷移
    table = newTable;
    threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

關鍵點：擴容為 2 倍，重新哈希分佈，JDK 8+ 利用 hash & oldCap 判斷節點留在原桶還是遷移到 oldIndex + oldCap，避免全量重新計算 hash。

五、get(Object key) 查找流程

1. Key 為 null → getForNullKey() 直接取 table[0] 鏈表首節點。
2. 計算 hash → 定位桶索引。
3. 遍歷該桶鏈表/樹，e.hash == hash && (e.key == key || key.equals(e.key)) 命中返回 e.value。
4. 未命中返回 null。

時間複雜度：理想情況 O(1)，極端碰撞 O(n)（JDK 8+ 樹化後 O(log n)）。

六、自定義對象作為 Key 的正確姿勢

class User {
    private int idNumber;
    public User(int id) { this.idNumber = id; }

    @Override public int hashCode() { return idNumber; }
    @Override public boolean equals(Object obj) {
        return obj instanceof User && idNumber == ((User) obj).idNumber;
    }
}

// 測試
Map<User, String> map = new HashMap<>();
map.put(new User(3), "張三");
System.out.println(map.get(new User(3))); // 張三（同 hashCode + equals 視為同一 key）

鐵律：equals() 為 true 的兩個對象，hashCode() 必須相等。違反會導致「能 put 進去，卻 get 不出來」。

七、equals() 五大契約

1. 自反性：x.equals(x) == true
2. 對稱性：x.equals(y) == y.equals(x)
3. 傳遞性：x.equals(y) && y.equals(z) → x.equals(z)
4. 一致性：多次調用結果不變（除非依賴字段被修改）。
5. 非空性：x.equals(null) == false

八、性能調優建議

• 預估數據量大時，構造時指定 new HashMap<>(expectedSize)，避免多次擴容。
• 負載因子 0.75 是時空折中；只讀/查詢多可適當調大（如 0.9），寫入多可調小（如 0.5）。
• 高併發場景請用 ConcurrentHashMap，HashMap 非線程安全。