核心數據結構
Node[] table // transient，桶數組，長度永遠是 2 的冪次
│
├─ Node (單向鏈表節點) // hash 衝突時鏈接
│ final int hash; K key; V value; Node next;
│
└─ TreeNode (紅黑樹節點，繼承 Node) // 鏈表長度 ≥ 8 且 table ≥ 64 時樹化
TreeNode parent; left; right; prev; boolean red;
關鍵常量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
static final int MAXIMUM_CAPACITY = 1 << 30; // 1073741824
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; // 最小樹化容量
hash 擾動函數
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
高 16 位參與低位運算，減少哈希碰撞，提升低位熵值。
putVal 核心流程
- 若
table == null → resize() 初始化
- 計算
i = (n-1) & hash 定位桶索引
- 桶為空 →
newNode 直接放入
- 桶非空 → 遍歷鏈表/樹：
- hash 相等且 key 相同（
== 或 equals()） → 覆蓋舊值，返回 oldValue
- 鏈表末尾 →
newNode 掛尾部
- 鏈表長度達
TREEIFY_THRESHOLD → treeifyBin() 樹化
++size > threshold → resize() 擴容
resize() 擴容遷移
- 新容量 = 舊容量 * 2
- 遷移策略：同桶節點分裂為「低位」與「高位」兩條鏈表
(e.hash & oldCap) == 0 → 留在原索引- 否則 → 移至
原索引 + oldCap
- 無需重新計算 hash，極大提升擴容效能
get 流程
- 計算 hash、索引
- 桶為樹 →
getTreeNode() 紅黑樹查找 O(log n)
- 桶為鏈表 → 遍歷比較
equals()
- 找到返回 value，否則 null
自定義 Key 正確實現
public final class UserId {
private final long value;
public UserId(long value) { this.value = value; }
@Override public int hashCode() {
return Long.hashCode(value); // 或 (int)(value ^ (value >>> 32))
}
@Override public boolean equals(Object obj) {
return obj instanceof UserId other && this.value == other.value;
}
}
鐵律：equals() 相等 ⇒ hashCode() 必相等。違反將導致 get/put/remove 失效。
JDK 17/21 新特性
- JDK 17：無結構性變更，效能微調
- JDK 21：
HashMap.newHashMap(int mappings) 靜態工廠，預計算容量避免多次擴容
效能調優建議
