Java 8 引入了 HashMap 中的树化，以减轻基于冲突的拒绝服务攻击。阈值 8 源于 泊松分布，其负载因子为 0.75，单个桶中包含 8 个或更多元素的概率约为 0.00000606（6 × 10⁻⁶）。这种统计稀有性确保仅在绝对必要时将链表转换为 红黑树（它消耗的内存大约是标准 Node 的两倍），以维护 O(log n) 的查找复杂度。
该实现在内存效率和攻击抵御能力之间取得平衡。一个 TreeNode 对象在使用压缩 OOP 的 64 位 JVM 上需要 48 字节，而标准 Node 则为 32 字节，主要是由于额外的父节点、左节点、右节点和前一个节点的引用以及一个颜色标志。这个阈值代表了在恶意冲突中 O(n) 遍历的成本超过树结构内存开销的拐点。
// 在 HashMap.java 中定义常量 static final int TREEIFY_THRESHOLD = 8; static final int UNTREEIFY_THRESHOLD = 6; static final int MIN_TREEIFY_CAPACITY = 64;
一个流量大的 电子商务平台 在闪购期间经历了灾难性的延迟峰值。调查发现攻击者提交了带有成千上万故意制作的查询参数的 HTTP 请求，旨在生成相同的 hashCode() 值，导致用于参数解析的 HashMap 实例退化为具有 O(n) 访问时间的链表。
// HashDoS 攻击的模拟 Map<String, String> vulnerableMap = new HashMap<>(); for (int i = 0; i < 10000; i++) { // 生成相同 hash 码的构造键 vulnerableMap.put(createCollidingKey(i), "malicious_value"); } // 查找时间：JDK 7 中为 O(n)，在 JDK 8 及以上为 O(log n)
评估了几种补救策略。
在 web 服务器级别考虑了 速率限制，因为它可以减缓可疑的流量模式。然而，这种方法被证明无效，因为合法的闪购流量也会生成高请求量，使得在高收入期间区分变得不可能，同时可能阻止有效客户。
限制参数计数到 100 的 输入验证 被作为一种简单的修复方案以防止哈希洪水提议。但产品经理拒绝了这个解决方案，因为他们希望在其目录搜索接口中支持复杂的过滤矩阵，而安全工程师指出，攻击者仍然可以在 50 个精心选择的参数内实现冲突。
短暂考虑迁移到 ConcurrentHashMap，假设其并发结构可能以不同的方式处理冲突。然而，由于 ConcurrentHashMap 采用相同的树化机制，应对攻击时当运行低于树化阈值时会遭受类似 O(n) 的退化，因此没有缓解作用。
工程团队选择了双管齐下的方法。他们将平台升级到 JDK 8，利用自动树化机制，当冲突超过 8 的阈值时，将链表转换为 红黑树。这确保了即使是恶意输入也能实现 O(log n) 的查找性能，而不是线性退化。此外，他们实施了一个 servlet 过滤器，对传入请求的哈希分布熵进行计算，拒绝那些具有可疑冲突模式的请求，避免映射构建。
部署后的指标显示，即使在持续攻击下，响应时间仍保持在 50 毫秒以下。CPU 利用率在高峰流量期间保持在 40% 以下，而之前的实现则在攻击开始几分钟内饱和了所有核心。该平台成功处理了闪购，无服务降级，验证了依赖 JVM 内部冲突处理而非外部速率限制的架构决策。
为什么阈值在 6 个元素处转回链表而不是 7 或 8？
UNTREEIFY_THRESHOLD 为 6 防止在波动的工作负载中在数据结构之间振荡。如果删除操作使树减少到 7 个元素，维护树结构会避免立即的重新转换成本。6 元素的边界提供了滞后效应，确保树构建的成本（需要分配新的 TreeNode 对象和重新平衡）在足够长的时间内摊销。
泊松分布如何具体证明数字 8 的合理性？
在默认负载因子 0.75 下，每个桶中元素的期望数量遵循泊松分布，其中 λ 等于 0.5。概率质量函数产生 P(0) = 0.6065, P(1) = 0.3033, P(2) = 0.0758，呈指数下降。达到 8 个元素的概率为 0.5⁸/8! × e^(-0.5) ≈ 6.0 × 10⁻⁶。这代表着百万分之六的机会，意味着 TreeNode 对象的内存惩罚影响正常操作中不到 0.0006% 的桶。
维护树化桶与链表相比的实际内存开销是多少？
一个标准的 HashMap.Node 消耗 32 字节（对象头、哈希整数、对键的引用、对值的引用、对下一个的引用）。一个 TreeNode 继承自 LinkedHashMap.Entry，而 LinkedHashMap.Entry 又继承自 Node，继承了额外的字段：父节点、左节点、右节点、前一个节点以及一个 boolean 红色标志。这导致在使用压缩 OOP 的 64 位 JVM 上每个条目需要 48 字节，外加 LinkedHashMap 的开销。对于一个包含 8 个元素的桶，树化结构大约需要 384 字节，而链表仅需 256 字节，代表着 50% 的增加，而考虑到此类冲突的稀有性，这仍然是可以接受的。