HashMap 扩容时的链表与红黑树:树化阈值为什么是 8
问题背景:一次 put 之后,桶里发生了什么
HashMap 的底层结构可以概括为“数组 + 链表 + 红黑树”。每次 put 先计算扰动后的哈希值,再用 (n - 1) & hash 定位数组下标。如果目标桶为空,直接放入新节点;如果桶里已经有节点,就沿链表比较 hash 和 equals,相同则覆盖,不同则追加到链表尾部。当某个桶的链表过长时,JDK 8 会把它转换成红黑树,将最坏情况下的线性查找降为对数查找。
这里有两个容易混淆的“阈值”。一个是扩容阈值:默认容量 16、负载因子 0.75,元素数超过 12 时扩容。另一个是树化阈值:某个桶里的节点数达到条件后,链表转成红黑树。前者衡量整个表的拥挤程度,后者只衡量单个桶的碰撞程度。即使 HashMap 的总元素很少,只要若干 key 的哈希值恰好落在同一个桶,也可能触发树化;反过来,表很大时,单个桶通常不会很长,树化并不常见。
标题中的“扩容时”并非说只有扩容才会树化,而是因为两者在源码里确实会互相影响。treeifyBin 会先检查表长度是否达到 MIN_TREEIFY_CAPACITY(64):如果还没达到,它不会立刻建树,而是调用 resize() 扩大表,希望把碰撞的节点分散到更多桶里。只有表长足够、链表仍然很长时,才真正进行树化。
链表到红黑树:三个常量与一个前置条件
JDK 8 的 HashMap 定义了三个关键常量:
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
putVal 在链表尾部追加节点后,会执行类似下面的判断:
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
binCount 从 0 开始,并且不把链表头节点计入,所以这个条件对应的是“桶里已有 8 个节点,正在追加下一个节点”的场景。源码注释的表述也是:向一个至少已有 TREEIFY_THRESHOLD 个节点的桶添加元素时,尝试转成树。不要把它误解成“HashMap 的 size 到 8 就树化”,size 和单个桶的长度完全是两件事。
treeifyBin 也不是无条件建树。它的逻辑可以简化为:
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else
// 把当前桶的 Node 链表替换成 TreeNode 链表,再调用 treeify
因此,一个容量只有 16 的 HashMap,即使某个桶里堆了 9 个节点,也会先扩容到 32;如果仍然不够 64,再继续扩容。扩容后元素会重新分布,很多碰撞会自然消失。只有容量达到 64 且桶仍然过长,才会真正生成红黑树。这也是为什么“树化阈值 8”不能脱离“最小树化容量 64”单独理解。
当删除元素使树节点减少到 UNTREEIFY_THRESHOLD(6)时,HashMap 会把树退回链表。树化和退化采用不同的阈值,是为了留出一段缓冲区间,避免桶大小在 7、8 之间反复变化时频繁转换结构。
为什么是 8:泊松分布与成本模型
阈值取 8,不是拍脑袋,而是基于“正常哈希下长链表极其罕见”这一概率假设。JDK 源码注释给出了一个泊松分布模型:在默认负载因子和随机哈希的理想情况下,桶内节点数 k 的出现频率大约为
exp(-0.5) * 0.5^k / k!
按这个模型,桶内有 8 个节点的概率约为 0.00000006,也就是千万分之一级别;超过 8 个节点的概率更低。换句话说,只要 hashCode 分布正常,树化本身就应该是一条极少走的路径。
红黑树节点比普通链表节点重得多。TreeNode 除了 hash、key、value、next,还要维护 parent、left、right、prev 和颜色信息,内存开销大约是普通节点的两倍。查找方面,8 个节点的链表平均比较 4 次,红黑树最坏约 3 次,差距并不大;但树化、插入和删除时的旋转、着色、维护父指针都更复杂。因此,只有在链表长到“正常哈希几乎不会出现”的长度时,才值得付出这些额外成本。
8 这个值还和退化阈值 6 配合。若只有一个阈值,桶大小在阈值附近抖动时会不断在链表和树之间切换;6 与 8 之间留出两个节点的滞回区间,可以显著减少结构转换。对于哈希值全部相同的极端 key,红黑树能把查找从 O(n) 降为 O(log n),但它仍然是“补救措施”,不是鼓励使用糟糕的 hashCode。
代码示例:观察一个桶如何变成 TreeNode
下面的程序用 10 个哈希值都为 1、但 equals 不同的 key 制造碰撞,再通过反射查看 HashMap 内部桶的类型。为了跳过“小表先扩容”的分支,构造时直接指定容量 64。
import java.lang.reflect.Field;
import java.util.HashMap;
import java.util.Map;
public class TreeifyDemo {
static final class Key {
final int id;
Key(int id) { this.id = id; }
@Override public int hashCode() { return 1; }
@Override public boolean equals(Object o) {
return o instanceof Key && ((Key) o).id == id;
}
}
public static void main(String[] args) throws Exception {
Map<Key, Integer> map = new HashMap<>(64);
for (int i = 0; i < 10; i++) {
map.put(new Key(i), i);
}
Field tableField = HashMap.class.getDeclaredField("table");
tableField.setAccessible(true);
Object[] table = (Object[]) tableField.get(map);
int index = (table.length - 1) & 1;
Object bin = table[index];
System.out.println("table.length = " + table.length);
System.out.println("bin class = " + bin.getClass().getName());
int count = 0;
for (Object p = bin; p != null; p = next(p)) count++;
System.out.println("bin size = " + count);
}
private static Object next(Object node) throws Exception {
for (Class<?> c = node.getClass(); c != null; c = c.getSuperclass()) {
try {
Field f = c.getDeclaredField("next");
f.setAccessible(true);
return f.get(node);
} catch (NoSuchFieldException ignored) {
// 继续向父类查找
}
}
throw new NoSuchFieldException("next");
}
}
JDK 9 及以上运行时需要开放 java.util 的反射权限:
java --add-opens java.base/java.util=ALL-UNNAMED TreeifyDemo
典型输出如下:
table.length = 64
bin class = java.util.HashMap$TreeNode
bin size = 10
如果把构造容量改成 16,并去掉最小容量 64 的前置条件,程序会看到表先扩容,桶类型可能仍然不是 TreeNode;这正好说明树化不是“桶长度一到 8 就立刻发生”。
实践建议与踩坑
第一,优先保证 hashCode 的质量。树化只能缓解碰撞,不能消除碰撞带来的内存和比较成本。可变对象作为 key 时,放入 HashMap 后不要再修改参与 hashCode 或 equals 计算的字段,否则连节点都定位不到,更谈不上树化。
第二,容量规划要按预期元素数计算。若已知要放 n 个元素,可以使用 new HashMap<>((int) (n / 0.75f) + 1),避免反复扩容;但这只是减少 resize,不会改变单个桶的树化阈值。容量仍然是 2 的幂,HashMap 会通过 tableSizeFor 向上取整。
第三,不要依赖“第 8 个节点一定树化”这种说法做业务判断。真实条件是桶内已有 8 个节点后继续追加、且表容量至少为 64;容量不足时会先扩容。删除时则以 6 为退化阈值,二者之间存在滞回。
第四,树化不是线程安全的补救。HashMap 本身不支持并发写,JDK 8 虽然不会再像 JDK 7 那样在并发扩容时轻易形成环形链表,但并发 put 仍可能丢数据、覆盖节点或破坏结构。并发场景应使用 ConcurrentHashMap,而不是指望红黑树解决竞态问题。
- 点赞
- 收藏
- 关注作者
评论(0)