HashMap 扩容时的链表与红黑树:树化阈值为什么是 8

举报
yd_254127822 发表于 2026/11/15 11:50:52 2026/11/15
【摘要】 从 JDK 8 的 putVal 与 treeifyBin 源码出发,说明桶内链表转红黑树的实际触发条件,结合泊松分布解释树化阈值 8 与退化阈值 6 的成本权衡,并给出可复现实验与容量规划建议。

问题背景:一次 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,而不是指望红黑树解决竞态问题。

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0)

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。