Java HashMap在链表长度≥8且数组长度≥64时转红黑树，将最坏查找从O(n)降至O(log n)；节点≤6时退化回链表，兼顾性能与空间开销。

Java 中 HashMap 通过在链表过长时转为红黑树，把最坏情况下的查找时间从 O(n) 降到 O(log n)，这是 JDK 1.8 的关键优化。

为什么需要红黑树

哈希冲突无法完全避免。当多个 key 映射到同一个数组下标（桶），它们会以链表形式串在一起。如果大量 key 都哈希到同一桶（比如哈希函数设计不佳或数据分布极端），链表会很长，查找、插入、删除都得遍历，退化成线性时间。

红黑树是自平衡二叉搜索树，能保证任意节点左右子树高度差有限，从而维持较稳定的查找效率。

链表何时转成红黑树

不是链表一变长就立刻树化，而是满足两个条件才触发：

立即学习“Java免费学习笔记（深入）”；

Alibabacloud Sdk Client Initialization For Java

在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。

下载

• 链表长度 ≥ 8（TREEIFY_THRESHOLD = 8）
• 当前哈希表数组长度 ≥ 64（MIN_TREEIFY_CAPACITY = 64）

第二个条件很重要：如果数组太小（比如才 16 或 32），说明整体容量不足，更应优先扩容，而不是树化。只有当数组已经足够大，还出现长链表，才认为是“真冲突”，值得用树结构优化。

红黑树怎么提升查找性能

在桶中是链表时，查找需逐个比较 key（equals + hashCode 匹配）；而转成红黑树后，查找基于 key 的自然顺序或 Comparator 进行二分逻辑跳转：

• 每个 TreeNode 节点含 left/right/parent/红黑标记等字段，支持左旋、右旋、着色等平衡操作
• 查找时从根节点开始，根据 key 比较结果决定向左或向右子树递归，最多比较 log₂(n) 次
• 例如一个长度为 1024 的链表，最坏要查 1024 次；同样规模的红黑树，最多查约 10 次

红黑树也会退化回链表

优化是双向的。当红黑树节点数 ≤ 6（UNTREEIFY_THRESHOLD = 6）时，会自动转回链表。

这通常发生在 resize（扩容）后，元素被重新分配，原桶中节点大量迁出，剩余节点变少。此时链表更轻量，没必要维持树结构开销。