为什么 JDK 1.8 对 HashMap 进行了红黑树的改动？

问题的根源：链表的性能瓶颈

在 JDK 1.8 之前，HashMap 采用"数组 + 链表"的数据结构。当发生哈希冲突时，新元素会被添加到链表的头部或尾部。这种设计在正常情况下工作良好，但存在一个致命缺陷：当大量元素映射到同一个桶时，链表会变得很长，导致查询性能急剧下降。

想象一下，如果一个桶中的链表有 1000 个元素，那么在最坏情况下，查找一个元素需要遍历整个链表，时间复杂度退化为 O(n)，完全失去了哈希表应有的 O(1) 查询优势。

恶意攻击的威胁

更严重的是，这个特性可能被恶意利用。攻击者可以精心构造大量具有相同哈希值的字符串，强制它们映射到 HashMap 的同一个桶中，形成极长的链表。这种哈希碰撞攻击可以让服务器的 CPU 使用率飙升，造成拒绝服务攻击（DoS）。

哈希碰撞（Hash Collision）就是：
两个不同的输入，经过同一个哈希函数计算后，得到了完全相同的哈希值。

红黑树：优雅的解决方案

JDK 1.8 引入红黑树正是为了解决这个问题。新的设计规则如下：

• 阈值控制：当链表长度超过 8 时，自动转换为红黑树
• 动态切换：当红黑树节点数量少于 6 时，重新退化为链表
• 性能保障：红黑树保证了 O(log n) 的查询时间复杂度

这样的设计兼顾了两种数据结构的优势：

• 链表在元素较少时具有更好的空间效率和简单性
• 红黑树在元素较多时提供稳定的查询性能

为什么选择红黑树？

你可能会问，为什么不选择 AVL 树或其他平衡二叉树？答案在于权衡：

1. 相对平衡：红黑树不要求严格平衡，但保证最长路径不超过最短路径的2倍
2. 插入删除效率：相比 AVL 树，红黑树的插入和删除操作需要的旋转次数更少
3. 实现复杂度：在性能和实现复杂度之间找到了最佳平衡点

JDK 1.8 对 HashMap 除红黑树外的其他重要改动

改动维度	JDK 1.7 及之前	JDK 1.8 改进	说明与收益
哈希函数	直接用 key.hashCode()	增加“扰动函数”：h ^ (h >>> 16)	让高位也参与桶下标计算，减少哈希冲突。
插入方式	头插法（新节点插链表头部）	尾插法（新节点插链表尾部）	避免多线程扩容时链表逆序形成环形链表导致死循环。
扩容逻辑	重新计算每个元素的 hash 并取模	利用“(e.hash & oldCap) == 0”高位判位，元素要么留在原索引，要么去 原索引+oldCap	省去 rehash，扩容速度大幅提升。
初始化时机	构造方法立即分配桶数组	懒加载：第一次 put 时才分配数组	减少空 Map 占用的内存。
API 增强	无	新增 computeIfAbsent、merge、forEach 等默认方法	简化常见模式，代码更简洁。
查找优化	直接遍历链表/树	getNode 先快速检查首节点	命中最快路径，减少不必要的遍历。

总结

JDK 1.8 的 HashMap 通过“数组 + 链表 + 红黑树”三重结构，辅以更优的哈希、扩容、插入策略，在极端冲突场景下依然能保持 O(log n) 的查询性能，同时兼顾内存与 CPU 开销，并天然免疫经典的 Hash-DoS 攻击。这一系列改动让 HashMap 在高并发、大数据量环境下表现更加稳定与高效。