HashMap 源碼深度解析：數據結構、擴容機制、Hash 算法、負載因子、線程安全

HashMap 源碼深度解析：數據結構、擴容機制、Hash 算法、負載因子、線程安全

核心數據結構

• JDK 7：數組 + 鏈表（Entry<K,V>[] table）
• JDK 8+：數組 + 鏈表/紅黑樹（鏈表長度 > 8 且數組 > 64 樹化）

本文基於 JDK 7 源碼（經典教學版）逐行剖析。

關鍵字段

static final int DEFAULT_INITIAL_CAPACITY = 16;  // 必須 2^n
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
transient Entry<K,V>[] table;
transient int size;
int threshold;           // capacity * loadFactor
final float loadFactor;
transient volatile int modCount;  // fail-fast

構造函數鏈

• HashMap()：默認 16/0.75，threshold=12；
• HashMap(int cap)：指定容量，自動向上取 2 的冪；
• HashMap(int cap, float lf)：完全自定義，參數校驗；
• HashMap(Map<? extends K,? extends V> m)：複製構造，預分配容量避免擴容。

核心方法逐行解析

put(K, V)

1. key==null → putForNullKey()（固定放 table[0]）；
2. hash(key.hashCode()) 計算擾動 hash；
3. indexFor(hash, table.length) 定位桶索引；
4. 遍歷鏈表：e.hash == hash && (e.key==key || key.equals(e.key)) → 替換 value，返回舊值；
5. 無匹配 → addEntry() 頭插法插入新 Entry，modCount++，size++；
6. 若 size > threshold → resize(2*capacity)。

hash(int h) 擾動函數

h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);

目的：將高位信息混入低位，減少碰撞，配合 & (length-1) 實現近似均勻分布。

indexFor(int h, int length)

return h & (length - 1);

為何 capacity 必須 2^n？
length-1 二進制全為 1（如 15=1111），& 運算相當於取模，且極快。驗證：1000 個 key 在 capacity=16 時均勻分佈 16 桶；capacity=50 時僅落入 8 個桶，嚴重失衡。

resize(int newCap) & transfer()

• 創建新數組，遍歷舊數組每個桶；
• 對每個 Entry 重新計算 indexFor(e.hash, newCap)（rehash）；
• 頭插法掛入新桶（注意：多線程下頭插法會導致鏈表成環，JDK 8 改為尾插法）。

get(Object key)

• null key → getForNullKey() 掃 table[0]；
• 非 null → hash → indexFor → 遍歷鏈表匹配 key → 返回 value 或 null。

remove(Object key)

• 定位桶，雙指針 prev/e 遍歷；
• 找到後 prev.next = e.next 或 table[i] = e.next 斷鏈；
• modCount++、size--、調用 recordRemoval()。

負載因子權衡

• 默認 0.75：時間/空間折中；
• 較大 → 空間利用率高，但碰撞多、查詢慢；
• 較小 → 碰撞少、查詢快，但內存浪費、擴容頻繁。

線程安全警示

HashMap 非線程安全，多線程下：

• 擴容導致鏈表成環（JDK 7），CPU 100% 死循環；
• 數據覆蓋丟失。

替代方案：

• JDK 7：Collections.synchronizedMap() 或 Hashtable（鎖整張表，性能差）；
• JDK 8+：ConcurrentHashMap（CAS + synchronized 細粒度鎖，高並發首選）。

最佳實踐清單

1. 預估數據量 → new HashMap((int)(n/0.75)+1) 避免擴容；
2. 容量給 2 的冪（或依賴構造函數自動向上取整）；
3. 高並發場景直接用 ConcurrentHashMap；
4. Key 類正確重寫 hashCode()/equals()，遵守協定：equals 真 → hashCode 必相等。