跳到主要内容

哈希冲突、树化与退化条件

两个键映射到同一个桶时就发生哈希冲突。HashMap 先用短链表处理普通冲突；当前 OpenJDK 在桶过长且表容量足够时转为红黑树，以限制极端查找成本。

1. 冲突是哈希表的正常状态​

数组桶数量有限，键空间远大于桶数量，不同键进入同一桶不可避免。正确实现不要求哈希完全无冲突，而是让分布尽量均匀，并在冲突后继续确认键是否相等。

record CollisionKey(int id) {
    @Override
    public int hashCode() {
        return 1;
    }
}

所有 CollisionKey 都会产生同一哈希，但 id 不同的对象仍不相等。HashMap 必须在同一桶中保存它们。

坏哈希会把平均 O(1) 查找变成长桶查找，并增加 equals 调用次数。业务键应让常见输入尽量均匀分布。

2. 短冲突使用链表​

链表节点结构简单，对少量元素的遍历开销较低。树节点需要更多引用和维护逻辑，因此桶里只有几个元素时直接树化并不划算。

当前实现向链表末尾加入新节点。查找时先比较保存的哈希，再比较键引用或 equals。相等键会覆盖旧值，不相等键继续向后查找。

3. 树化需要同时满足两个条件​

当前 OpenJDK 的关键实现常量包括：

  • TREEIFY_THRESHOLD = 8
  • MIN_TREEIFY_CAPACITY = 64
  • UNTREEIFY_THRESHOLD = 6

当一次插入使桶内节点达到树化阈值时，如果整个 table 的容量还小于 64，实现优先扩容，而不是立刻树化。原因是小表中的长链可能来自容量不足，扩容后节点会分散到不同桶。

只有表已经足够大、冲突仍然集中时，才把链表转换为红黑树。

这些数字属于当前 OpenJDK 实现，不是 Map 接口契约。面试中可以说明它们，但更重要的是解释：短桶用简单结构，小表先扩容，持续严重冲突再用树限制退化。

4. 红黑树限制桶内查找高度​

红黑树通过颜色和旋转保持近似平衡，桶内有 k 个节点时，查找接近 O(log k)。HashMap 的树节点还保留链式链接，以支持迭代和扩容拆分。

键没有实现同类可比较关系时，HashMap 仍需要建立稳定的树内顺序。树的排序仅服务桶内定位，不等于 Map 获得业务排序语义，遍历顺序仍不受保证。

树化缓解极端冲突，却不能消除：

  • 计算昂贵的 hashCode 和 equals。
  • 大量碰撞键带来的内存增长。
  • 并发写入的数据竞争。
  • 攻击者持续提交海量请求的总体资源消耗。

5. 扩容会拆分链和树​

容量翻倍时，同一旧桶中的节点只会落到两个位置：

  • 原索引。
  • 原索引加旧容量。

实现可以按哈希中新增参与定位的那一位，把桶拆成低位组和高位组。树桶拆分后，如果某一组节点很少，会退化回链表，减少树节点成本。

退化阈值 6 与树化阈值 8 之间留出间隔，可以避免节点数量在边界附近变化时频繁树化、退化。

6. 冲突攻击与不可信键​

HTTP 参数名、JSON 字段或用户可控制标识进入哈希表时，攻击者可能构造大量冲突键，提高 CPU 和内存消耗。现代 HashMap 的树化限制了部分桶内复杂度，但安全设计仍需要：

  • 限制请求字段数量和总大小。
  • 在解析边界限制嵌套深度与对象数量。
  • 使用有界缓存，避免无限保留攻击者键。
  • 监控解析时间、桶异常和请求拒绝。
  • 对协议解析器使用经过安全审查的实现。

树化是数据结构防护的一层，不是流量和资源治理的替代品。

7. 常见问题​

7.1 为什么不从第一个冲突就使用红黑树​

少量节点的链表结构更小，比较逻辑更直接。红黑树需要更多字段、旋转和排序判断。只有桶持续变长时，对数查找才足以覆盖这些固定成本。

7.2 链表达到 8 个节点就一定树化吗​

不一定。table 容量小于当前实现的最小树化容量时，会先扩容；只有扩容后冲突仍集中并满足条件才树化。还要区分插入前后的计数边界，不应只背一句“等于 8”。

7.3 红黑树退化为什么不是同一个阈值​

树化和退化使用不同边界可以提供滞后区间，避免桶在 7、8 个节点附近来回变换结构。拆分后节点很少时，链表的空间和简单性更合适。

7.4 哈希冲突会让 equals 返回 true 吗​

不会。冲突只说明两个处理后哈希映射到同一桶，逻辑相等仍由 equals 决定。相等对象必须有相同哈希，但相同哈希的对象可以不相等。

8. 面试题​

8.1 HashMap 什么时候把链表转成红黑树，为什么小容量时先扩容​

出现公司：阿里巴巴、美团

考察重点

  • 树化阈值、最小表容量和退化阈值的协作。
  • 扩容分散普通碰撞与树处理持续碰撞的区别。
  • 实现常量与 Map 公共契约的边界。

相关内容：第 3 节“树化需要同时满足两个条件”至第 5 节“扩容会拆分链和树”。

参考回答

当前 OpenJDK 在桶链达到树化阈值 8，并且 table 容量至少为 64 时，才考虑转为红黑树。容量较小时先扩容，因为长链可能只是桶太少，扩容能让哈希中新的位参与定位，把节点分散开。

扩容拆分后，一组节点数量降到退化阈值附近会变回链表。树化和退化边界留有间隔，避免结构频繁切换。这些具体数字是实现细节，核心取舍是小桶保持简单、持续严重冲突才使用树。

8.2 红黑树是否彻底解决了哈希冲突攻击​

出现公司：阿里巴巴

考察重点

  • 树化只限制桶内查找成本。
  • 恶意键仍会消耗对象、比较和请求解析资源。
  • 数据结构与输入限额、过载保护需要共同工作。

相关内容：第 4 节“红黑树限制桶内查找高度”、第 6 节“冲突攻击与不可信键”。

参考回答

树化可以把严重冲突桶的查找从线性路径改善为接近对数路径，但仍要创建节点、计算哈希、比较键和处理请求。攻击者还可以通过请求数量、字段数量和对象深度消耗其他资源。

因此需要同时限制输入大小与字段数、使用有界数据结构、监控异常耗时并设置流量保护。红黑树降低一种算法退化风险，不等于完整的拒绝服务防护。

参考资料
  1. OpenJDK：HashMap 源码与树化常量
  2. Java API：HashMap
  3. Java API：Object.hashCode