JDK 8中HashMap在链表长度≥8且数组长度≥64时转红黑树以优化查找性能至O(log n)，否则扩容；树化由treeifyBin()触发，先检查容量再决定扩容或建树，并支持退化回链表。
HashMap在JDK 8里为什么用红黑树替代链表
当同一个桶（bucket）里的元素太多，链表查找会退化成 O(n)，JDK 8 改成在链表长度 ≥ 8 且数组长度 ≥ 64 时，把链表转成红黑树，把最坏查找降到 O(log n)。这不是一上来就上树——它得先确保数组够大、冲突真密集，否则小数组+短链表转树反而更慢。
常见错误现象：ConcurrentModificationException 不是因为红黑树，但遍历时若结构被并发修改，树节点和链表节点的 next 字段行为不一致，可能让迭代器更早暴露问题；另外，hashCode 实现不合理时，哪怕数组很大，也会人为制造长链/树，让优化失效。
- 触发条件必须同时满足：
binCount >= TREEIFY_THRESHOLD（8）且tab.length >= MIN_TREEIFY_CAPACITY（64） - 如果数组太小（比如初始容量设为 16），即使某个桶挂了 10 个元素，也不会转树，只会扩容
- 红黑树节点比链表节点内存开销大，所以 JDK 8 还加了反向逻辑：resize 后若树中节点 ≤ 6，会退化回链表（
UNTREEIFY_THRESHOLD = 6）
treeifyBin() 方法到底干了什么
treeifyBin() 是真正执行链表→红黑树转换的入口，但它不是无脑转——它先检查数组长度是否达标，不达标就优先调用 resize()。也就是说，你看到日志或调试里进了 treeifyBin()，不代表马上建树，大概率是去扩容了。
使用场景：高频写入 + hashCode 分布差（比如大量对象返回相同哈希值），又没预估好初始容量，就容易频繁触发这个流程。
立即学习“Java免费学习笔记（深入）”；
- 该方法在
putVal()末尾被调用，属于“事后补救”，不是 put 前的预判 - 转换过程会重新计算每个节点在树中的位置（基于 key 的
hashCode和树内比较逻辑），不是简单把链表指针改造成树指针 - 注意：只有
key实现了Comparable或者传了Comparator，树内排序才有意义；否则会抛ClassCastException
红黑树节点和链表节点混存带来的兼容性影响
HashMap 内部用一个统一的 Node 类型做链表节点，而红黑树用的是额外的 TreeNode 子类。它们共享部分字段（如 hash、key、value），但 TreeNode 多了 parent、left、right、red 等字段。这意味着：同一桶里可能同时存在 Node 和 TreeNode，但实际不会——转树后整个桶只存 TreeNode，退化时才全变回 Node。
容易踩的坑：自己写遍历逻辑（比如反射读取 table 字段）时，假设所有节点都是 Node，遇到 TreeNode 就可能 NPE 或类型转换失败；还有人误以为 TreeNode 的 next 字段还能像链表一样串起来用，其实它只在树结构无效时才维护这条链（用于退化）。
-
TreeNode继承自Node，所以能塞进table数组，但多了树相关字段，单个对象内存占用约多 32–40 字节（取决于 JVM 对象头和对齐） - 序列化时，
TreeNode会被自动扁平化成链表形式写入，反序列化后仍是普通Node，不保留树结构 - 如果你用
Unsafe直接操作内存或做对象图分析，要注意TreeNode的字段布局和Node不同
什么时候不该依赖红黑树优化
红黑树不是银弹。如果你的 key 类型 hashCode 天然分散（比如 UUID、Long 值），或者你主动设了足够大的初始容量（如 new HashMap(1024)），那几乎不会触发树化——这时候花时间研究 treeifyBin 的细节，不如检查 key 的 equals/hashCode 是否一致，或者是不是有大量 null key/value 导致意外行为。
性能上，树化本身有开销：要新建对象、重哈希、构建平衡树，单次 put 可能从纳秒级跳到微秒级；而一次 resize 往往比一次 treeify 更重。所以别为了“看起来高级”强行凑条件测试树逻辑。
- 单元测试里硬编码
System.setProperty("jdk.map.althashing.threshold", "0")没用，JDK 8 已移除该开关 - 用 JMH 做性能对比时，记得预热并排除 GC 干扰；单纯跑 100 次 put 看不出树和链表差别
- 线上监控发现
java.util.HashMap$TreeNode实例数突增，第一反应不该是“树生效了”，而是查 key 的hashCode是否异常集中，或是否有恶意构造的哈希碰撞攻击
红黑树机制藏得深，但真正影响你代码行为的，往往还是那个没重写的 hashCode，或者忘了设初始容量的 new HashMap()。
