HashMap链表转红黑树是在链表长度≥8且数组长度≥64时触发的性能优化机制，将查找从O(n)降为O(log n)，避免哈希冲突导致的性能雪崩。
Java 中 HashMap 通过链表转红黑树，本质是在哈希冲突严重时，把线性查找降级为对数级查找，从而避免性能雪崩。这不是简单“换结构”，而是有明确触发条件和设计权衡的自动优化机制。
链表查找慢在哪？
当多个 key 落入同一个桶（数组索引），它们以单向链表形式串联。查找时需从头遍历，最坏情况要比较全部节点——时间复杂度 O(n)。比如链表长度达 100，平均要查 50 次；到 1000，就退化成类似遍历 ArrayList 的开销。
而红黑树是自平衡二叉搜索树，所有操作（查、插、删）都稳定在 O(log n)。链表长度 100 时，log₂100 ≈ 7 次比较；长度 1000 也只需约 10 次。这种差距在线上高并发、大数据量场景中直接影响响应延迟。
转树不是随时发生，必须同时满足两个硬条件
HashMap 不会因为链表一变长就立刻树化，它只在以下两个条件都成立时才执行 treeifyBin()：
- 当前桶中链表节点数 ≥ 8（TREEIFY_THRESHOLD = 8）
- 整个 HashMap 底层数组长度 ≥ 64（MIN_TREEIFY_CAPACITY = 64）
如果数组长度还不到 64，即使链表已满 8 个节点，也会优先触发 resize() 扩容（比如从 32 扩到 64），靠增大桶数量来自然分散冲突——这比建树更轻量、更治本。
为什么设 64 这个下限？
这是空间与时间的精细取舍：
- 小容量数组（如 16 或 32）里出现长链表，大概率不是数据真冲突，而是哈希分布没摊开，扩容就能解决
- 红黑树节点比普通 Node 多存 parent、left、right、prev 和 color 字段，内存占用明显更高
- 在桶数少时，log n 优势不明显（log₂8 ≈ 3，和遍历 8 个节点差不了多少），但额外开销却实实在在
- 只有当数组足够大（≥64），还持续出现 ≥8 的链表，才说明是 key 的 hashCode() 实现有问题或数据存在强偏态，值得用树来兜底
树化后查找怎么变快？
红黑树节点 TreeNode 保留了链表的 next 指针，也新增了 left/right/parent 等字段，支持按 key 的自然顺序或 compareTo() 进行二分比较。get() 查找时：
- 先定位桶位置（数组索引）
- 若该桶是 TreeNode 类型，就走红黑树的查找路径：根据 key 的 hash 和 Comparable 接口逐层比大小，向左或向右子树推进
- 最多比较 log₂N 次即可命中或确认不存在
相比链表逐个 equals()，省去了大量无效字符串比较或对象哈希码计算，尤其在 key 是 String、Long 等高频类型时效果显著。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
