bigywater.tech
Rust · 61

HashSet 与去重

HashSet 看起来只是「没有值的 HashMap」,但 insert 的返回值、集合运算、保序去重、dedup 的陷阱和 Eq 与 Hash 的一致性都有细节。这篇每一点都用真实运行验证。

bool
insert 与 remove 的返回值:是否真的改变了集合
3 种
Eq 与 Hash 不一致时,12 次运行得到的不同结果数
11.3 ms
100 万个元素去重,HashSet collect 的耗时

insert 与集合运算

实测 · 本机执行输出
  编译:成功
  运行(退出码 0):
    insert 3 -> true  insert 5 -> true  再 insert 3 -> false  len 2
    remove 5 -> true  remove 9 -> false  contains 3 -> true
    交 [3, 4]  并 [1, 2, 3, 4, 5]  差 a-b [1, 2]  对称差 [1, 2, 5]
    is_subset true  is_disjoint false
    HashSet 相等与顺序无关: true
    &a | &b = {1, 2, 3, 4, 5}  &a & &b = {3, 4}

HashMap 的细节见HashMap 的哈希与扩容。

去重的写法

实测 · 本机执行输出
  编译:成功
  运行(退出码 0):
    保持首次出现顺序: [3, 1, 2, 5]
    sort + dedup:     [1, 2, 3, 5]
    BTreeSet:         [1, 2, 3, 5]
    只 dedup(不排序): [3, 1, 3, 2, 1, 5, 2]  ← dedup 只去掉相邻的重复

去重的速度

实测 · 本机执行输出
  编译:成功
  运行(退出码 0):
    HashSet collect   11.30 ms (去重后 99995 个)
    sort_unstable + dedup   11.66 ms (去重后 99995 个)
    BTreeSet collect   15.18 ms (去重后 99995 个)

耗时是本机 release 实测,键是 xorshift 生成的 0..100000 随机数;换成字符串或更多重复率,排名可能不同。

自定义类型的 Eq 与 Hash

实测 · 本机执行输出
  编译:成功
  运行(退出码 0):
    true
    同 id 不同 name 再插入 -> false(被当作重复,保留的是 User { id: 1, name: "alice" })
    replace 才会替换 -> 旧值 Some("alice"),现在是 "ALICE"
  编译:成功
  运行(退出码 0):
    19
  eq 恒为 true、哈希按内部值:20 个元素插入后 len,同一个程序运行 12 次: [20, 20, 20, 20, 19, 19, 17, 20, 20, 19, 19, 19] (理想的集合应当总是 1)

分步演示

HashSet 去重
本步的对象

    本文用到的工具与边界

    • 本机 macOS 27 arm64 / rustc 1.98.1(brew)/ cargo 1.98.1;单个文件用 rustc 直接编译,需要依赖时用 cargo(经代理从 crates.io 下载);计时用 std::time::Instant,数字每次运行会有小幅抖动。计时 release + black_box
    • 没有验证:字符串元素的去重速度、HashSet::retain/drain 的行为、集合运算在大集合上的复杂度(只验证了结果)、Eq/Hash 不一致时在其它容量下的结果分布
    京ICP备2026067502号-1京公网安备11010502063487号