HashMap 是 Java 集合框架中使用頻率最高、面試考察最深的數據結構。本文基於 JDK 8 源碼，系統剖析其存儲結構、核心字段、構造器、雜湊算法、put/get 流程、擴容機制，並重點解讀 JDK 8 引入的「鏈表轉紅黑樹」關鍵優化及其防禦 HashDoS 攻擊的原理。
數組 + 鏈表 + 紅黑樹 (JDK 8+)
transient Node<K,V>[] table：雜湊桶數組，長度永遠為 2 的冪次。// Node 節點定義 (JDK 8)
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 雜湊值緩存
final K key; // Key 不可變
V value; // Value 可變
Node<K,V> next; // 鏈表指針 / 樹節點指針
// ... 構造器、getter、equals、hashCode、toString
}
// TreeNode 繼承 Node，增加紅黑樹屬性
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent, left, right, prev;
boolean red;
// ... 樹操作邏輯
}
| 字段 | 默認值 | 含義 |
|---|---|---|
DEFAULT_INITIAL_CAPACITY | 16 (1<<4) | 默認初始容量，必須為 2 的冪 |
MAXIMUM_CAPACITY | 1<<30 | 最大容量上限 |
DEFAULT_LOAD_FACTOR | 0.75f | 負載因子：空間利用率與查詢速度平衡點 |
TREEIFY_THRESHOLD | 8 | 鏈表轉樹閾值 |
UNTREEIFY_THRESHOLD | 6 | 樹轉鏈表閾值 (擴容時) |
MIN_TREEIFY_CAPACITY | 64 | 允許樹化的最小數組長度 |
// 1. 計算 key 的雜湊值 (攪拌高低位，減少衝突)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 2. 計算數組索引 (位運算替代取模，要求 length 為 2 的冪)
static int indexFor(int h, int length) {
return h & (length - 1); // 等價於 h % length，但極快
}
h & (length-1) 等價於取模運算。若 length=2^n，則 length-1 二進制全為 1 (如 15=1111)，& 操作能均勻分佈低位雜湊值。若 length 為奇數，length-1 末位為 0，導致索引末位恆為 0，浪費一半桶位。
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(...);
// 計算 ≥ initialCapacity 的最小 2 的冪次
int capacity = 1;
while (capacity < initialCapacity) capacity <<= 1;
this.loadFactor = loadFactor;
this.threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// table 延遲到首次 put 時初始化 (lazy initialization)
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 1. 延遲初始化 table
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2. 計算索引，桶為空直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 3. 遍歷鏈表/樹，檢查 Key 是否存在
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p; // Key 存在，覆蓋值
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 紅黑樹插入
else {
// 鏈表遍歷
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 4. 達到樹化閾值，轉為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
// Key 存在
break;
}
p = e;
}
}
// 5. 覆蓋舊值
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 6. 尺寸超過閾值，擴容
if (++size > threshold) resize();
afterNodeInsertion(evict);
return null;
}
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; }
newCap = oldCap << 1; // 容量翻倍
} else if (oldThr > 0) // 有初始化參數但未分配 table
newCap = oldThr;
else // 無參構造器
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(newCap * loadFactor);
threshold = newThr;
Node<K,V>[] newTab = (Node<K,V>[]) new Node[newCap];
table = newTab;
// 核心：重新雜湊分佈 (JDK 8 優化：無需重新計算 hash，利用高位掩碼)
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e = oldTab[j];
if (e == null) continue;
if (e.next == null) // 單節點直接遷移
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) // 紅黑樹拆分遷移
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 鏈表拆分遷移 (保持原序)
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) { // 高位為 0，留在原索引
if (loTail == null) loHead = e;
else loTail.next = e;
loTail = e;
} else { // 高位為 1，索引 + oldCap
if (hiTail == null) hiHead = e;
else hiTail.next = e;
hiTail = e;
}
e = next;
} while (e != null);
if (loTail != null) { loTail.next = null; newTab[j] = loHead; }
if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; }
}
}
}
return newTab;
}
e.hash & oldCap 判斷高位，將鏈表一分為二 (lo/hi)，無需重新計算 hash，且保持原鏈表順序 (避免 JDK 7 頭插法導致的倒序與併發死循環)。
TREEIFY_THRESHOLD (8)MIN_TREEIFY_CAPACITY (64) — 小數組優先擴容而非樹化惡意構造大量 hashCode() 相同但 equals() 不同的 Key，導致所有條目落入同一桶，退化為鏈表，查詢從 O(1) 變為 O(n)，造成 CPU 100% (拒絕服務)。
JDK 8 引入樹化後，即使極端衝突，查找性能也呈對數級增長，有效緩解 HashDoS。
紅黑樹需比較大小決定左右子樹。若 hash 相同且 Key 實現 Comparable，按自然序插入；否則可能退化性能。建議自定義 Key 實現 Comparable。
public V get(Object key) {
Node<K,V> e = getNode(hash(key), key);
return (e == null) ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key); // 樹查找 O(log n)
do { // 鏈表查找 O(n)
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
| 知識點 | 核心結論 |
|---|---|
| 底層結構 | 數組 + 鏈表/紅黑樹 (JDK 8)，拉鏈法解決衝突 |
| 容量規則 | 永遠為 2 的冪，默認 16，最大 1<<30 |
| 負載因子 | 默認 0.75，空間換時間，可通過構造器指定 |
| 擴容觸發 | size > threshold (capacity * loadFactor)，擴容 2 倍 |
| JDK 8 優化 | 高位掩碼擴容保序、鏈表樹化防 HashDoS、延遲初始化 |
| Null 支援 | 允許 1 個 null Key (固定 table[0])，多個 null Value |
| 線程安全 | 非線程安全，多線程用 ConcurrentHashMap |
| 性能建議 | 預估數據量指定 initialCapacity 避免頻繁擴容重雜湊 |
