为什么jdk17将链表的转红黑树的阈值从8调整到6

要理解这个改动，我们需要先回顾一下HashMap中为什么需要引入红黑树。

背景：为什么需要“树化”？

在JDK 8之前，HashMap的每个桶（bucket）完全由链表实现。虽然链表在一般情况下表现良好，但如果发生大量的哈希碰撞（即多个key的hash值都映射到了同一个桶），链表会变得非常长。此时，查询、插入操作的时间复杂度会从理想的O(1)退化为O(n)，严重影响性能。

为了解决这个问题，JDK 8引入了重大改进：当链表长度超过一定阈值时，会将其转换为红黑树。红黑树是一种自平衡的二叉搜索树，其查询、插入、删除的最坏时间复杂度都能保持在O(log n)。这样，即使在最坏的情况下，性能也不会退化得太严重。

原来的逻辑：阈值8和退化阈值6

在JDK 8到JDK 16中，这个树化（treeify）的阈值是 8。同时，还有一个与之配对的解除树化（untreeify） 的阈值 6。

• 树化（链表 -> 红黑树）: 当单个桶中的链表长度 > 8 时，触发转换。
• 解除树化（红黑树 -> 链表）: 当在进行扩容（resize）或删除操作后，单个桶中的元素数量 ≤ 6 时，触发转换。

为什么要设置两个不同的阈值？ 这是为了避免在临界值附近发生频繁的、昂贵的结构转换。想象一下，如果阈值都是7，那么当一个桶的元素数量在7附近频繁增减时，HashMap会不断地在链表和红黑树之间来回转换，这个转换过程本身就有性能开销（创建树节点、调整平衡等）。设置一个2的差值（8和6），提供了一个“缓冲带”，防止了这种抖动。

JDK 17的改动：将树化阈值从8改为6

现在，核心问题来了：既然8和6的缓冲带设计得很好，为什么JDK 17还要把树化阈值从8降到6呢？

根本原因：为了更早地预防性能退化，尤其是在哈希碰撞被恶意构造的攻击场景下。

1. 更早干预，防止链表过长：
   • 虽然红黑树的查询效率是O(log n)，但转换本身是有成本的。链表在长度很短时（比如6），其遍历速度可能比遍历一颗小型红黑树更快（因为红黑树需要更多的指针寻址和平衡操作）。
   • 但是，当链表长度从6增长到7、8时，其性能下降的曲线开始变得陡峭。在长度为6时进行树化，可以确保在性能出现明显下降之前，就将其转换为更稳定数据结构。这是一种“用略微提前的、可预知的转换成本，去规避潜在的、更大的性能风险”的策略。
2. 增强对抗哈希碰撞拒绝服务（Hash Collision DoS）攻击的能力：
   • 这是非常重要的一点。在早期，很多语言（包括Java）的哈希表实现容易受到一种攻击：攻击者通过精心构造大量具有相同哈希值的key，使哈希表退化为一条长长的链表，导致CPU利用率飙升，服务器无法响应其他请求，从而实现拒绝服务攻击。
   • JDK 8引入红黑树的主要目的之一就是解决这个问题。将树化阈值从8降低到6，意味着攻击者需要制造更多的碰撞（更多的key）才能让哈希表达到性能开始退化的链表长度。即使达到了，链表也只会到6就被转换成了树，其查询效率被控制在O(log n)的安全范围内。这大大增加了攻击的难度和成本，提升了安全性。
3. 权衡转换开销与性能收益：
   • JDK开发者通过大量的测试和性能分析发现，在大多数现代硬件和实际应用场景中，在链表长度为6时进行树化，所带来的性能收益（稳定的O(log n)）已经超过了树化操作本身的开销。
   • 换句话说，他们发现这个“盈亏平衡点”比之前认为的（8）要更早。在长度为6时转换，整体收益更高。

总结

JDK 17将链表转红黑树的阈值从8调整为6，是一项经过深思熟虑的优化：

• 目的：进一步优化最坏情况下的性能，提升对哈希碰撞攻击的防御能力。
• 机制：更早地（在链表长度为6时）进行干预，防止链表变得过长，从而避免性能退化。
• 设计：它仍然与解除树化的阈值（保持为6）有一个缓冲带（现在是 树化 > 6，解除树化 <= 6），避免了在临界点频繁转换。

这个改动体现了Java持续优化其核心库，尤其是在安全性和极端情况性能方面的重视。对于普通开发者来说，这个改动是完全透明的，你不需要修改任何代码，就能享受到它带来的潜在性能和安全性的提升。