JDK 8 HashMap:数组 + 链表 + 红黑树
Node<K,V>[] table(桶数组)
┌─────┐
│ [0] │ → null
├─────┤
│ [1] │ → Node(K1,V1) → Node(K2,V2) → null (链表,长度<8)
├─────┤
│ [2] │ → null
├─────┤
│ [3] │ → TreeNode(K3,V3) (红黑树,链表长度≥8且数组≥64)
│ │ ╱ ╲
│ │ TreeNode(K4,V4) TreeNode(K5,V5)
│ │ ╱ ╲ ╱ ╲
│ │ ... ... ... ...
├─────┤
│ [4] │ → Node(K6,V6) → null
├─────┤
│ ... │
└─────┘
核心参数:
DEFAULT_INITIAL_CAPACITY = 16 // 默认初始容量
DEFAULT_LOAD_FACTOR = 0.75f // 负载因子
TREEIFY_THRESHOLD = 8 // 链表→红黑树阈值
UNTREEIFY_THRESHOLD = 6 // 红黑树→链表阈值
MIN_TREEIFY_CAPACITY = 64 // 树化的最小数组容量
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 为什么不直接用 hashCode % length?
// 1. 扰动:高16位异或低16位,让高位也参与定位计算
// 2. 减少冲突:hashCode可能低位变化不大,扰动后分布更均匀
// 3. 定位桶:(n - 1) & hash,等价于 hash % n(n为2的幂时)
// 示例:
// hashCode = 0x12345678
// h >>> 16 = 0x00001234
// hash = 0x12345678 ^ 0x00001234 = 0x1234444C
// index = 0x1234444C & 0x0000000F = 0x0C = 12(假设n=16)
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// ① 初始化table(延迟初始化)
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// ② 定位桶,如果桶为空直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// ③ 桶中第一个Node的key匹配 → 找到更新目标
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// ④ 桶头是TreeNode → 红黑树插入
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); // 尾插法!
// 链表长度达到8 → 尝试树化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1是因为binCount从0开始
treeifyBin(tab, hash); // 注意:不一定真的树化!
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// ⑥ 找到已存在的key → 更新value
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // LinkedHashMap回调
return oldValue;
}
}
++modCount;
// ⑦ 检查是否需要扩容
if (++size > threshold) // threshold = capacity * loadFactor
resize();
afterNodeInsertion(evict);
return null;
}
putVal流程图:
┌──────────────────────────────────────────────────────────────┐
│ putVal(key, value) │
├──────────────────────────────────────────────────────────────┤
│ │
│ 1. table为空? → resize()初始化 │
│ │
│ 2. tab[index]为空? → 直接插入新Node │
│ │否 │
│ ▼ │
│ 3. 头节点key匹配? → 记录e,后续更新value │
│ │否 │
│ ▼ │
│ 4. 头节点是TreeNode? → putTreeVal红黑树插入 │
│ │否(链表) │
│ ▼ │
│ 5. 遍历链表: │
│ ├── 找到相同key → 记录e,后续更新value │
│ └── 遍历到尾部 → 尾插法插入新Node │
│ └── 链表长度≥8? → treeifyBin() │
│ │
│ 6. e != null → 更新旧值,返回旧值 │
│ │
│ 7. ++size > threshold → resize()扩容 │
│ │
└──────────────────────────────────────────────────────────────┘
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 关键判断!数组长度 < 64 → 只扩容不树化
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize(); // 优先扩容而不是树化!
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 链表转红黑树
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
// 树化双条件:
// 1. 链表长度 ≥ 8(TREEIFY_THRESHOLD)
// 2. 数组长度 ≥ 64(MIN_TREEIFY_CAPACITY)
// 两个条件同时满足才真正树化!
// 只满足条件1 → 只扩容不树化
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) { // 已达最大容量
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 扩容为2倍
else if ((newCap = oldCap << 1) <= MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // threshold也翻倍
}
// ... 初始化分支省略 ...
// 数据迁移
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
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 {
// 链表拆分:高位链和低位链(JDK 8优化!)
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) {
// 低位链:原位置不变
if (loTail == null) loHead = e;
else loTail.next = e;
loTail = e;
} else {
// 高位链:新位置 = 原位置 + 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;
}
为什么容量必须是2的幂:
1. 定位桶的公式:index = (n - 1) & hash
当n为2的幂时,n-1的二进制全为1(如15=1111)
等价于 hash % n,但位运算比取模快得多
2. 扩容时hash重计算优化:
新容量 = 2 * 旧容量
节点在新数组中的位置只有两种可能:
- 原位置(hash & oldCap == 0)
- 原位置 + oldCap(hash & oldCap != 0)
示例(oldCap=16, newCap=32):
hash=21 (0b10101)
oldIndex = 21 & 15 = 5 (0b00101 & 0b01111 = 0b00101)
newIndex = 21 & 31 = 21 (0b10101 & 0b11111 = 0b10101)
或者 = 5 + 16 = 21
只需要看hash的第5位(oldCap对应的位)是0还是1!
JDK 7 死链问题(并发扩容时链表成环):
扩容时使用"头插法"(transfer方法):
原链表:A → B → C(插入顺序)
扩容后新链表:C → B → A(反序)
两个线程同时扩容:
线程1:取出A,准备插入新表...(被挂起)
线程2:完成扩容,新链表 C → B → A
线程1恢复:
取A → A.next指向新表的B → B.next指向A
结果:A ⇄ B(环形链表!)
后续get()操作会死循环!
┌─── JDK 7 transfer 头插法 ───┐
│ │
│ while(null != e) { │
│ Entry<K,V> next = e.next; │
│ e.next = newTable[i]; │ ← 头插:新节点指向链表头
│ newTable[i] = e; │ ← 更新链表头
│ e = next; │
│ } │
└──────────────────────────────┘
JDK 8 修复:改用"尾插法" + 高低位拆分
尾插法保证链表顺序不变 → 不会成环
高低位拆分(loHead/loTail, hiHead/hiTail) → 不需要遍历链表重新hash
但注意:JDK 8的HashMap仍然不是线程安全的!
并发put可能导致数据丢失(两个线程同时往同一个空桶插入,后者的CAS覆盖前者)
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);
// 链表遍历
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
Q1: HashMap的key可以是null吗?
可以。null的hash固定为0,存储在table[0]的桶中。但只能有一个null key(因为key不能重复)。value也可以为null。
Q2: 为什么负载因子是0.75?
是时间和空间的折中。太大(如1.0)→ 空间利用率高但冲突多,查找慢;太小(如0.5)→ 冲突少但浪费空间。0.75是统计学上的良好平衡点,且threshold = capacity * 0.75保证是整数(capacity是2的幂)。
Q3: HashMap和HashTable的区别?
(1) HashMap非线程安全,HashTable线程安全(synchronized);(2) HashMap允许null key/value,HashTable不允许;(3) HashMap初始容量16,HashTable 11;(4) HashMap用2的幂+位运算定位,HashTable用素数+取模;(5) HashMap有红黑树优化,HashTable没有。
Q4: hashCode()和equals()的关系?
equals相等的两个对象,hashCode必须相等。hashCode相等的两个对象,equals不一定相等。HashMap先比较hashCode(hash),再比较equals。如果只重写equals不重写hashCode,两个"相等"的对象可能散列到不同桶中,导致get找不到。
Q5: 红黑树的时间复杂度为什么比链表好?
链表查找O(n),红黑树查找O(log n)。当链表长度为8时,红黑树查找最多3次比较。但红黑树节点占用更多内存(TreeNode比Node大),所以只在链表较长时才树化。
1. 手动推演:容量16,依次put key="A"(hash=65), "B"(hash=66), "Q"(hash=81),画出table结构。
2. 为什么树化条件要求数组长度≥64?如果数组长度只有16就树化,会有什么问题?
3. 编写一个测试:创建HashMap,重写key的hashCode让多个key落到同一个桶,观察链表到红黑树的转换。
4. 解释为什么重写equals()必须同时重写hashCode(),用HashMap的put/get流程说明。
5. 比较JDK 7和JDK 8 HashMap扩容的rehash策略差异,解释为什么JDK 8更高效。