HashSet 性能分析：O(1) 的代价与条件

HashSet 为什么快

HashSet 的 O(1) 操作不是魔法，是有条件的。

条件是：哈希函数必须把元素均匀分布到各个桶中。

如果哈希函数把大量元素都塞进同一个桶，时间复杂度就从 O(1) 退化到 O(n)。

---

各操作时间复杂度

操作	平均复杂度	最坏情况	说明
add	O(1)	O(n)	哈希 + 可能的链表遍历
remove	O(1)	O(n)	同上
contains	O(1)	O(n)	同上
遍历	O(n + m)	—	n=元素数，m=桶数

均摊 vs 最坏

10 万元素，负载因子 0.75，初始容量 16：

- 扩容次数：约 11 次（16 → 32 → 64 → ... → 131072）
- 平均每次 add 操作：1 次哈希 + 1 次数组访问 + 0~1 次 equals 比较
- 均摊复杂度：O(1)

最坏情况（所有元素 hashCode 相同）：
- 全部 10 万元素在同一个桶的链表里
- 每次 add/contains：O(n) 链表遍历

---

性能基准测试

import java.util.*;

public class HashSetBenchmark {

    public static void main(String[] args) {
        int size = 1_000_000;

        // 1. 添加性能
        HashSet<Integer> set = new HashSet<>();
        long start = System.nanoTime();
        for (int i = 0; i < size; i++) {
            set.add(i);
        }
        System.out.printf("添加 %d 元素: %.0f ms%n", size,
            (System.nanoTime() - start) / 1_000_000.0);

        // 2. 查找性能
        start = System.nanoTime();
        for (int i = 0; i < size; i++) {
            set.contains(i);
        }
        System.out.printf("查找 %d 元素: %.0f ms%n", size,
            (System.nanoTime() - start) / 1_000_000.0);

        // 3. 遍历性能
        start = System.nanoTime();
        int sum = 0;
        for (Integer i : set) {
            sum += i;
        }
        System.out.printf("遍历 %d 元素: %.0f ms%n", size,
            (System.nanoTime() - start) / 1_000_000.0);

        // 4. 删除性能
        start = System.nanoTime();
        for (int i = 0; i < size / 2; i++) {
            set.remove(i);
        }
        System.out.printf("删除 %d 元素: %.0f ms%n", size / 2,
            (System.nanoTime() - start) / 1_000_000.0);
    }
}

典型输出（MacBook Pro M2，JDK 17）：

添加 1000000 元素: 85 ms
查找 1000000 元素: 32 ms
遍历 1000000 元素: 18 ms
删除 500000 元素: 28 ms

---

影响性能的关键因素

1. 哈希函数质量

好的哈希函数让元素均匀分布：

// String 的哈希函数：高效且分布均匀
// s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
// "hello" 和 "world" 落在不同桶

// 差的哈希函数：严重冲突
class BadHash {
    int value;
    BadHash(int v) { value = v; }
    @Override public int hashCode() { return 0; } // 所有元素冲突！
}

2. 负载因子

负载因子越大，内存利用率越高，但冲突概率也越大：

负载因子	内存利用率	冲突概率	适用场景
0.5	较低	低	写多读多
0.75（默认）	平衡	中	通用
0.9	高	高	内存敏感、读多写少

// 写多场景：降低负载因子减少扩容
HashSet<String> writeHeavy = new HashSet<>(10000, 0.5f);

// 读多场景：可以适当提高负载因子
HashSet<String> readHeavy = new HashSet<>(10000, 0.9f);

3. 初始容量

如果能预估元素数量，提前设置初始容量可以避免多次扩容：

// ❌ 默认：可能扩容多次
HashSet<String> set1 = new HashSet<>();
for (int i = 0; i < 100000; i++) {
    set1.add("item-" + i);
}

// ✅ 预分配：一次到位
HashSet<String> set2 = new HashSet<>(133334); // 100000/0.75
for (int i = 0; i < 100000; i++) {
    set2.add("item-" + i);
}

// Benchmark：
// set1（默认）: ~120 ms（含多次扩容开销）
// set2（预分配）: ~45 ms

4. 扩容成本

HashSet 的扩容成本不低：

扩容过程：
1. 创建新数组（容量翻倍，如 16 → 32 → 64）
2. 重新计算所有已有元素的桶位置（rehash）
3. 拷贝到新数组

100 万元素，一次扩容需要重新插入 ~100 万元素

这就是为什么预分配容量对大数据量有意义。

---

HashSet vs 其他 Set

特性	HashSet	TreeSet	LinkedHashSet
add/contains/remove	O(1)	O(log n)	O(1)
遍历顺序	无序	排序	插入顺序
内存占用	最低	较高（树节点）	较高（额外链表）
null 支持	✅	❌	✅

// HashSet 最快，因为它不需要维护额外结构
Set<String> hash = new HashSet<>();
// TreeSet 需要 O(log n) 维护红黑树平衡
Set<String> tree = new TreeSet<>();
// LinkedHashSet 需要维护双向链表
Set<String> linked = new LinkedHashSet<>();

---

实战优化建议

场景 1：已知数据量

// 预估 10 万元素
int expectedSize = 100_000;
Set<String> set = new HashSet<>(
    (int) (expectedSize / 0.75f) + 1
);

场景 2：高性能去重（接受额外内存）

// 降低负载因子，换取更好的哈希分布
Set<String> highPerf = new HashSet<>(1_000_000, 0.5f);

场景 3：字符串去重（利用 String 缓存）

// String.hashCode 有缓存，重复查找极快
Set<String> strings = new HashSet<>();
// 第一遍计算 hashCode，后续查找直接用缓存值

---

总结

要点	说明
O(1) 条件	哈希均匀分布，无严重冲突
最坏情况	所有元素在同一桶，退化到 O(n)
性能杀手	频繁扩容、糟糕的 hashCode 实现
优化手段	预分配容量、调整负载因子
vs TreeSet	HashSet 快 10-50 倍（无排序需求时）

一句话：HashSet 的 O(1) 是「均摊」的结果，不是保证。哈希函数质量才是性能的关键。

---

相关链接

• HashSet 底层实现
• HashSet 去重原理
• TreeSet 性能分析