Java HashMap 什么时候会树化：链表桶、容量阈值与碰撞处理

线上缓存键出现集中碰撞时，很多人第一反应是“桶里节点超过 8 个就会树化”。这个说法少了一个关键条件：HashMap 还要看数组容量。容量不足时，它会优先扩容，而不是马上把链表改成红黑树。

HashMap 的树化是两个阈值共同作用的结果：桶内节点达到 TREEIFY_THRESHOLD，并且数组容量至少达到 MIN_TREEIFY_CAPACITY；否则通常先走 resize。

HashMap 为什么不在第一次碰撞时就树化

HashMap 的数组槽位由哈希值定位。不同 key 落到同一个槽位后，桶里会先挂成链表。少量碰撞时，链表结构简单，插入和读取的额外成本都有限；如果数组本身很小，碰撞密集也可能只是因为容量不足。

因此实现把两个判断放在一起。源码中的 TREEIFY_THRESHOLD 是 8，MIN_TREEIFY_CAPACITY 是 64。达到前一个条件时，如果容量还不到后一个条件，就把机会留给扩容，让元素重新分散到更大的数组中。

先看节点数，再看数组容量

这条判断可以记成“节点数到线，容量再验一次”。节点数没有达到 TREEIFY_THRESHOLD，继续使用链表；节点数达到后，如果当前容量小于 MIN_TREEIFY_CAPACITY，执行 resize；只有两个条件都满足，才进入树化逻辑。

这里别急着把 8 当成性能承诺。它是 JDK 实现里的决策阈值，不是说第 8 个元素一定完成树化，也不是说第 7 个元素的查询就一定很快。扩容、哈希分布和桶内实际节点数量都会影响最终状态。

插入时链表桶怎样切换成红黑树

插入从 putVal 进入。它先根据哈希值找到数组槽位：空槽位直接放入 Node；已有节点时，代码沿着桶结构查找相同 key，或者把新节点接到链表尾部。碰撞节点数达到判断点后，桶才可能转换为树结构。

树化后，桶中的节点不再只是普通链表节点，而是使用 TreeNode 维护红黑树关系。这个变化只发生在对应桶，不会把整个 HashMap 变成一棵树。其他没有碰撞的桶仍然按普通节点存放。

get 读取时会识别桶的节点类型

读取调用 get 后，仍然先通过哈希值定位桶。若桶头是普通 Node，就按链表检查 key；若桶已经是树桶，则转入 TreeNode 的树查找。也就是说，树化的收益只影响发生碰撞的那个桶，不改变其他槽位的读取方式。

删除也可能让树桶里的节点数量下降。实现会根据结构状态决定是否退回链表，不能把“曾经树化过”理解成永久状态。应用层只需要正确实现 key 的 equals 与 hashCode，不应该依赖某个桶一定保持红黑树。

用一个小实验观察扩容优先于树化

下面的示例故意使用相同哈希值的 key，方便观察碰撞；它只用于理解桶结构，不代表生产代码应该这样设计 key。

import java.util.HashMap;
import java.util.Map;

final class SameHashKey {
    private final int id;

    SameHashKey(int id) {
        this.id = id;
    }

    @Override
    public int hashCode() {
        return 7;
    }

    @Override
    public boolean equals(Object other) {
        return other instanceof SameHashKey key && id == key.id;
    }
}

Map cache = new HashMap();
for (int id = 0; id 

这个程序能制造碰撞，但仅打印 size() 并不能证明某个桶已经树化。要验证实现细节，需要在受控实验中结合调试器查看桶节点类型，并确认使用的 JDK 版本源码；不要把内部字段反射到业务代码里。

实际项目里应该记住的三个边界

• 容量边界：小容量下碰撞增多时，扩容可能先发生；不要只盯着桶长度。
• 键边界：equals 和 hashCode 必须保持契约一致，错误实现会造成查找失败，树化也救不了错误的键语义。
• 并发边界：HashMap 不是并发容器。多个线程同时写入时，应根据场景考虑 ConcurrentHashMap 或外部同步。

相关问题

HashMap 桶长度超过 8 就一定树化吗？

不一定。还要看数组容量是否达到 MIN_TREEIFY_CAPACITY，容量较小时通常先扩容。

树化会让整个 HashMap 都变成红黑树吗？

不会。只有发生大量碰撞的具体桶会切换结构，其他桶仍按自身节点类型工作。

为什么不能靠调小阈值解决坏哈希函数？

阈值只能改变结构切换时机，不能修复错误的 hashCode 分布或不一致的 equals 实现。先修正键契约，再评估容量和容器选择。

小结

HashMap 树化并不是单一的“碰撞次数开关”。插入路径先观察桶内节点，再结合数组容量决定扩容还是树化；读取路径则由 get 根据桶节点类型选择链表或树查找。理解这条边界后，调优时就不会把实现阈值误当成业务保证。