为什么 Java 8 HashMap 在大量 hash 碰撞时树化后仍接近 O(n)？

2026-11-04数据阿明

结论

HashMap 的桶转换为红黑树后，操作仍可能达到 O(n)。红黑树保持平衡只能保证树高为 O(log n)，查找时还需要能根据键确定搜索方向。

当所有键的 hashCode() 相同，又没有可用的比较顺序时，查找可能访问左右两棵子树，最坏情况下会检查整个桶。设桶内有 m 个元素，单次查找可达 O(m)；如果所有 n 个元素都集中在一个桶里，就是 O(n)。这个结论来自 OpenJDK 8u 的查找实现。来源：OpenJDK HashMap 源码

原问题没有提供键类型、具体操作和计时方式，还不能确定实际测试遇到了哪种情况。

为什么平衡树仍需要搜索多个分支？

树节点查找先比较内部保存的 hash，再检查引用是否相同或 equals() 是否相等。hash 相同而键不相等时，只有 HashMap 能识别并使用 Comparable，且比较结果非零，才能据此选择单侧子树；否则可能搜索两侧。

需要检查两种情况：

键没有可用的 Comparable 顺序。典型可识别形式是同一运行时类型的 class Key implements Comparable<Key>，不能只凭实现了某种 Comparable 就认定它一定生效。
不相等的键之间，compareTo() 大量返回 0。这时比较结果仍不能帮助确定方向。

插入时，tieBreakOrder() 会使用类名和 System.identityHashCode() 安排位置。但查找仍须支持“不同实例、equals() 相等”的键，因此不能直接依赖对象身份排除另一侧子树。putTreeVal() 缺乏可用顺序时，也可能先搜索子树，确认是否已有相等键，再插入。来源：TreeNode.find()、tieBreakOrder() 与 putTreeVal()

先确认桶确实已经树化

OpenJDK 8u 的 TREEIFY_THRESHOLD 为 8，MIN_TREEIFY_CAPACITY 为 64。底层数组容量不足 64 时，树化请求会优先触发扩容。对于普通 put() 路径，向已有至少 8 个节点的链表桶追加新键时才会请求树化，因此不能简单理解成“第 8 个元素插入后必然树化”。来源：putVal() 与 treeifyBin()

排查时，可以用调试器检查目标桶是否为 HashMap$TreeNode，以确认结构状态。具体性能原因还需要结合键的实现和测量方式判断。

如何用代码做对照？

下面保留常量 hashCode()，同时为键提供与 equals() 一致的比较顺序：

import java.util.HashMap;
import java.util.Map;

public class CollisionDemo {
    static final class Key implements Comparable<Key> {
        private final int id;

        Key(int id) {
            this.id = id;
        }

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

        @Override
        public boolean equals(Object obj) {
            return obj instanceof Key && id == ((Key) obj).id;
        }

        @Override
        public int compareTo(Key other) {
            return Integer.compare(id, other.id);
        }
    }

    public static void main(String[] args) {
        Map<Key, Integer> map = new HashMap<>(64);
        for (int i = 0; i < 32; i++) {
            map.put(new Key(i), i);
        }

        System.out.println(map.get(new Key(20)));
        System.out.println(map.get(new Key(-1)));
    }
}

做对照时，先移除 implements Comparable<Key> 和整个 compareTo() 方法，再与保留它们的版本比较。查询时使用新建的键，包括与已有键相等的情况，并分别测量命中和未命中场景。这段代码用于展示键的设计，不构成性能测试结果。

怎样判断测到的是否为单次 O(n)？

先明确计时范围：

单次 get() 的耗时才适合直接用于分析查找复杂度。
对全部 n 个键各查询一次，即使每次为 O(log n)，总成本也会是 O(n log n)。
连续插入 n 个同 hash、不可排序的不同键，若每次都需搜索已有节点，总成本可能达到 O(n²)。
遍历整个 HashMap 所需的时间与容量及元素数量有关，树化不会让完整遍历变成 O(log n)。来源：HashMap API 文档

对照测试应分开记录建表和查询时间，控制操作次数、对象分配、扩容及预热条件，并检查 equals()、compareTo() 自身是否昂贵。复杂度分析通常假设这些比较的成本为常数；一条耗时曲线不足以证明渐进复杂度。

实际使用中，应优先改善 hashCode() 的分布，并保证相等键拥有相同的 hashCode()。常量 hashCode() 适合制造极端测试场景，增加容量无法分散完全相同的 hash。确有自然顺序时，可以实现一致的 Comparable，同时保持参与相等判断和排序的字段在键存入期间稳定。