为解决哈希冲突严重时链表过长导致的O(1)→O(n)性能退化，JDK 1.8引入红黑树，将最坏时间复杂度降至O(log n)；选用红黑树而非AVL树或跳表，因其在查找、插入、删除间更均衡，旋转次数少、维护成本低，且适配HashMap内存局部性与单线程高频操作特性。
主要是为了解决哈希冲突严重时链表过长导致的性能退化问题。当大量键的 hashCode 分布不均、频繁落在同一个桶（bucket）里，链表就会变长，get、put、remove 等操作最坏时间复杂度会从 O(1) 退化到 O(n)。红黑树把最坏情况压到 O(log n)，显著提升了高冲突场景下的稳定性。
为什么选红黑树，而不是 AVL 树或跳表？
红黑树在查找、插入、删除三者间做了更均衡的取舍：
- AVL 树虽然查找更快，但每次插入/删除可能引发多次旋转，同步开销大，尤其在
ConcurrentHashMap这类并发容器中会加剧写等待 - 红黑树允许更大程度的“近似平衡”，插入和删除平均只需最多 2 次旋转，响应更轻量
- 跳表虽适合并发，但需要额外随机数和多层指针，在 HashMap 这种内存局部性敏感、单线程操作频繁的场景下，空间与缓存效率不如红黑树
为什么阈值设为 8，且要求数组长度 ≥64？
这不是拍脑袋定的数字，而是基于泊松分布和实测权衡的结果：
- 理想哈希下，桶中元素数量服从泊松分布；λ=0.5 时，链表长度 ≥8 的概率约为 0.00000006，极低——说明真到 8，大概率是哈希质量差或数据异常，必须干预
- 数组长度
- 阈值 8 是大量 JMH 基准测试后确定的拐点：小于 8 时链表更快；大于 8 后红黑树的 O(log n) 优势开始明显盖过其节点体积和构造成本
红黑树如何与原有结构共存？
HashMap 并没有“替换底层结构”，而是在单个桶内动态切换存储形态：
-
Node和TreeNode是同级类，TreeNode继承自Node，复用部分字段 - 桶中实际存储的是
Node类型引用，运行时通过instanceof判断走链表逻辑还是树逻辑 - 当链表转红黑树后，若后续删除过多导致节点 ≤6，还会自动退化回链表，避免“震荡”
本质上，这是 JDK 团队用工程思维做的精准优化：不追求理论最优，而是在真实负载、典型硬件、常见哈希实现下，让绝大多数场景更快，极端情况不失控。
