| 版本 | 核心結構 | 衝突解決 | 擴容機制 |
|---|---|---|---|
| JDK 7 | 數組 + 鏈表 | 頭插法，易形成環導致死循環 | rehash 全量遷移，需重新計算 hash |
| JDK 8 | 數組 + 鏈表 + 紅黑樹 | 尾插法保持順序，鏈表長>8 轉樹 | 無需 rehash，按高位分流到原索引或原索引+oldCap |
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8; // 鏈表轉樹閾值
static final int UNTREEIFY_THRESHOLD = 6; // 樹退化為鏈表閾值
static final int MIN_TREEIFY_CAPACITY = 64; // 數組長度<64 時優先擴容而非轉樹static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}設計精妙處：
^ (h >>> 16)），降低 hashCode 分佈不均導致的碰撞(n - 1) & hash 等價於取模，位運算極快
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. 延遲初始化：首次 put 時才創建數組
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);
// 3. 發生碰撞
else {
Node<K,V> e; K k;
// 3.1 key 相同（hash碰撞且equals相等），覆蓋值
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 3.2 已是樹節點，走樹插入邏輯
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 3.3 鏈表節點，遍歷鏈表
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 達到樹化閾值，觸發 treeifyBin
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 4. 覆蓋舊值邏輯
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 5. 尺寸檢查擴容
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 = 0;
// 計算新容量（2倍）和新閾值
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; }
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
} else if (oldThr > 0) newCap = oldThr;
else { newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); }
// 創建新數組
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 遷移數據：關鍵優化點
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
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，移到 j + oldCap
if (hiTail == null) hiHead = e;
else hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) { loTail.next = null; newTab[j] = loHead; }
if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; }
}
}
}
}
return newTab;
}新容量 newCap = oldCap * 2，只有新增的一個高位 bit 不同：
hash & (oldCap - 1) = 索引 jhash & (newCap - 1) = j 或 j + oldCap(e.hash & oldCap) == 0 即可決定去向，無需重新計算 hashCodeTREEIFY_THRESHOLD)MIN_TREEIFY_CAPACITY)，否則優先擴容final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) { x.parent = null; x.red = false; root = x; }
else {
K k = x.key; int h = x.hash; Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk = p.key;
if ((ph = p.hash) > h) dir = -1;
else if (ph < h) dir = 1;
else if ((kc == null && (kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk); // hash相同且不可比較時，用identityHashCode斷 tie
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0) xp.left = x; else xp.right = x;
root = balanceInsertion(root, x); // 關鍵：插入後修復紅黑樹性質
break;
}
}
}
}
moveRootToFront(tab, root);
}修復操作：變色 + 左旋/右旋，將插入點向上傳遞直到根。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == 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(k)
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}| 場景 | JDK 7 | JDK 8 |
|---|---|---|
| 海量碰撞（惡意攻擊） | 鏈表退化 O(n)，CPU 100% | 紅黑樹 O(log n)，抗攻擊 |
| 擴容遷移 | rehash 全量計算 | 零 rehash，位運算分流 |
| 並發 put | 頭插法易成環死循環 | 尾插法無環，但仍非線程安全 |
| 內存佔用 | 較小 | TreeNode 額外字段，略大 |
new HashMap<>(expectedSize) 避免多次擴容HashMap 從 JDK 7 到 JDK 8 的進化，是演算法與工程權衡的教科書級案例：空間換時間、位運算替除模、紅黑樹抗退化、零 rehash 遷移，每一處優化都直擊性能痛點。
