Java 集合框架深度剖析：HashMap 底層實現與源碼解讀

HashMap 類繼承體系與核心介面

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

繼承 AbstractMap，實現 Map、Cloneable、Serializable。非線程安全，可用 Collections.synchronizedMap() 包裝。

核心數據結構：數組 + 鏈表（拉鏈法）

底層維護一個 Entry<K,V>[] table 數組，每個槽位是單向鏈表頭節點。鍵的 hashCode() 經擾動函數計算 hash 值，再透過 indexFor(hash, length) 定位索引。Hash 碰撞時掛載至鏈表。

Entry 節點結構

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key; V value; Entry<K,V> next; int hash;
    Entry(int h, K k, V v, Entry<K,V> n) { ... }
    // getKey, getValue, setValue, equals, hashCode, toString...
}

next 指向下一節點，形成鏈表。新增節點時採用頭插法：table[i] = new Entry(hash, key, value, oldEntry)，最新節點始終位於鏈表頭。

關鍵屬性與設計考量

• DEFAULT_INITIAL_CAPACITY = 16：預設容量，必須是 2 的冪。
• MAXIMUM_CAPACITY = 1 << 30：最大容量上限。
• DEFAULT_LOAD_FACTOR = 0.75f：負載因子，平衡「空間利用率」與「碰撞概率」。
• threshold = capacity * loadFactor：擴容門檻。
• modCount：修改次數，支援 fail-fast 迭代器。

為何容量必須是 2 的冪？ indexFor 使用 h & (length - 1) 代替取模運算。若 length 為 2 的冪，length-1 低位全為 1，& 運算等同於取模且效率極高；同時保證索引分布均勻（奇數索引也會被使用），避免浪費一半空間。

構造方法與延遲初始化

構造方法僅記錄參數，真正初始化 table 發生在首次 put 時（inflateTable(threshold)）。此時將初始容量調整為最近的 2 的冪，重新計算 threshold，分配數組。

核心方法源碼解析

put(K key, V value)

1. 若 table 為空，調用 inflateTable 初始化。
2. key 為 null 時調用 putForNullKey，固定存放 table[0]。
3. 計算 hash：hash(key) 經擾動函數（高位參與運算）降低碰撞。
4. indexFor(hash, table.length) 獲取索引。
5. 遍歷該槽位鏈表：若 key 相同（== 或 equals()），替換 value 並返回舊值。
6. 否則 addEntry 頭插新節點，size++，檢查是否需擴容（size >= threshold 且槽位非空）。

擴容機制 resize(newCapacity)

• 新容量為舊容量 2 倍（不超過最大值）。
• 重新計算所有現有節點在新數組中的索引（Rehash），遷移數據。
• 因容量變化，索引公式結果改變，原本碰撞的節點可能分離，降低鏈表長度。

get(Object key)

1. key 為 null 直接查 table[0] 鏈表。
2. 否則計算 hash、索引，遍歷鏈表比對 hash 與 key，命中返回 value，否則返回 null。

其他常用方法

• remove(key)：定位節點，從鏈表移除，size--，返回被刪除值。
• keySet() / values() / entrySet()：返回視圖集合，底層迭代器遍歷 table 及鏈表。
• containsKey/Value：同上邏輯查找。