为什么 JDK 1.8 对 HashMap 进行了红黑树的改动？
- 标签：Java 集合、Java
🏛 业务架构师
这个改动我更愿意从故障防御的角度讲。HashMap 查询是 O(1) 的前提是 hash 分布均匀，但两种业务现实会打破它：
- 数据特征劣化：比如把用户 ID、设备指纹这类本身分布聚集的对象做 key，hash 碰撞集中在一个桶，链表演化成 O(n) 的线性扫描；
- 恶意碰撞攻击：攻击者构造一批 hash 值相同的参数打你的接口（hash collision DoS），把 Web 服务的响应时间拖垮。
JDK 1.8 引入红黑树后，单桶链表超过 8 且表容量够大就树化，最坏查询稳定在 O(logn)——100 万个元素退化后也就是 20 次比较。这是把"最坏情况"从不可接受变成可接受，属于典型的保底设计。
业务上的启示有两点：一是接口面向外部输入且用 HashMap 承载时，树化机制就是抗攻击的保险，但也提醒我们要在网关层做参数去重和限流，不能把保险丝当常态依赖；二是 hash 扰动函数（高 16 位异或低 16 位）也在让分布更均匀，自定义 key 的 hashCode 质量同样值得评审。性能优化要为最坏情况买单，而不是只看平均值，这是我评估技术方案时的一贯标准。
🏗 系统架构师
本质是防御哈希碰撞攻击。HashMap 最坏 O(n) 的根源是所有 key 落到同一个桶，攻击者可以构造一批哈希相同的 key 让服务端查询从毫秒级退化到秒级（Hash DoS）。引入红黑树后链表超过 8 且数组 ≥ 64 时树化，最坏查询/删除稳定在 O(log n)，8 个节点也就 3 次比较，把最坏情况的下限兜住了。
为什么阈值是 8：泊松分布下正常 hash 每个桶节点数达到 8 的概率约千万分之六，树化本质是兜底保险而非常态路径，所以退化阈值设 6 留出滞后带，避免在 7、8 之间反复增删导致树和链表来回抖动——这是很经典的迟滞设计，我做限流、缓存过期策略时也常用同样的滞后窗口防止临界震荡。
容量小于 64 时优先扩容而不是树化，因为小表冲突大概率是容量问题，扩容比树化代价更低、收益更直接。
💻 全栈开发专家
直接结论：防止 hash 碰撞极端情况下链表过长导致查询退化为 O(n)，树化后最坏 O(log n)。两个背景：
- 正常情况下 hash 分布均匀（泊松分布参数 0.5），一个桶里挂 8 个节点的概率约千万分之六，树化其实是兜底。
- 真正的场景是恶意 hash 碰撞攻击：服务端如果用用户传入的参数拼 Map，攻击者可以构造一批 hashCode 相同的 key（比如相同的字符串），把所有节点堆到一个桶里，让接口从 O(1) 变 O(n)，CPU 直接打满——这本质是一种 DoS。我在做网关参数解析时专门考虑过这个。
树化有两个条件，链表长度 ≥ 8 且数组长度 ≥ 64，数组不够 64 时优先扩容而不是树化（因为小表碰撞多半是容量问题）。退化阈值是 6 而不是 8，留了缓冲防止在 7、8 之间反复增删导致树和链表来回转换抖动。
节点内部用的是 TreeNode，比较先比 hash，再比 Comparable，没实现 Comparable 只能挨个比，所以有序类型的 key（如 Integer、String）树化收益最高。