Rust HashSet 与 BTreeMap

HashSet 是一个存放不重复值的集合。同一个值放进去两次，也只会存一份。可以把它想象成门口的宾客名单：保安只关心你的名字在不在名单上，不关心它被写了几遍。

你已经认识了 Vec 和 HashMap。这一课再介绍几个你最常用到的集合：HashSet、有序的 BTreeMap 和 BTreeSet，以及用来做队列的 VecDeque。最后还有一张表，帮你挑出合适的那一个。

创建 HashSet

HashSet 位于 std::collections 里，所以需要写一行 use。insert 方法返回一个 bool：值是新的就返回 true，已经存在就返回 false。

use std::collections::HashSet;

fn main() {
    let mut tags = HashSet::new();

    println!("{}", tags.insert("rust"));
    println!("{}", tags.insert("web"));
    println!("{}", tags.insert("rust")); // 已经有了

    println!("共有 {} 个不同的标签", tags.len());
}

输出：

true
true
false
共有 2 个不同的标签

▶ 动手试一试

这个 bool 比看上去更有用。它在添加值的同一步里就回答了“这个我以前见过吗？”，所以不需要再单独检查一次。

检查和删除值

contains 告诉你某个值在不在集合里。remove 把它删掉，并且和 insert 一样返回一个 bool，告诉你是否真的删掉了什么。

use std::collections::HashSet;

fn main() {
    let mut online: HashSet<&str> = HashSet::from(["小李", "小王", "小陈"]);

    println!("小王在线吗？{}", online.contains("小王"));

    println!("删除小王：{}", online.remove("小王"));
    println!("再删一次小王：{}", online.remove("小王"));

    println!("小王在线吗？{}", online.contains("小王"));
    println!("{} 人在线", online.len());
}

输出：

小王在线吗？true
删除小王：true
再删一次小王：false
小王在线吗？false
2 人在线

▶ 动手试一试

这里为什么用集合而不用 Vec？在 Vec 上调用 contains，会把每个元素挨个看一遍。HashSet 则不管有多大，都能直接找到答案。如果有一百万个用户，这个差距就非常大了。

警告

HashSet 没有固定的顺序。用 {:?} 打印它或者遍历它时，每次运行的顺序都可能不同。如果打印时需要稳定的顺序，就把值复制到一个 Vec 里排好序，或者改用 BTreeSet（下面会讲到）。

给 Vec 去重

一个非常常见的任务：你有一个带重复值的列表，想让每个值只出现一次。有两种好办法，取决于你是否在意原来的顺序。

use std::collections::HashSet;

fn main() {
    let visits = vec![3, 1, 3, 2, 1, 5, 2];

    // 方法 1：先收集到集合里，再排序，得到稳定的顺序
    let unique: HashSet<i32> = visits.iter().copied().collect();
    let mut sorted: Vec<i32> = unique.into_iter().collect();
    sorted.sort();
    println!("排序后去重：{:?}", sorted);

    // 方法 2：按原来的顺序，保留每个值第一次出现的位置
    let mut seen = HashSet::new();
    let mut in_order = visits.clone();
    in_order.retain(|x| seen.insert(*x));
    println!("保持原顺序：{:?}", in_order);
}

输出：

排序后去重：[1, 2, 3, 5]
保持原顺序：[3, 1, 2, 5]

▶ 动手试一试

方法 2 用到了 insert 返回的 bool。retain 只保留闭包返回 true 的元素，而 insert 只有第一次见到某个值时才返回 true。

集合运算：并集、交集、差集

集合可以像维恩图里的圆圈那样组合起来。每个方法都返回一个迭代器，所以我们把结果收集到 Vec 里，打印前先排序，这样每次的输出都一样。

use std::collections::HashSet;

fn main() {
    let alice: HashSet<&str> = HashSet::from(["rust", "python", "go"]);
    let bob: HashSet<&str> = HashSet::from(["go", "java", "rust"]);

    let mut both: Vec<_> = alice.intersection(&bob).collect();
    both.sort();
    println!("两人都会：{:?}", both);

    let mut either: Vec<_> = alice.union(&bob).collect();
    either.sort();
    println!("至少一人会：{:?}", either);

    let mut only_alice: Vec<_> = alice.difference(&bob).collect();
    only_alice.sort();
    println!("只有 Alice 会：{:?}", only_alice);

    let mut only_one: Vec<_> = alice.symmetric_difference(&bob).collect();
    only_one.sort();
    println!("只有一人会：{:?}", only_one);
}

输出：

两人都会：["go", "rust"]
至少一人会：["go", "java", "python", "rust"]
只有 Alice 会：["python"]
只有一人会：["java", "python"]

▶ 动手试一试

difference（差集）是单向的：alice.difference(&bob) 表示“Alice 会而 Bob 不会的”。把两边对调，得到的就是 Bob 的列表。symmetric_difference（对称差集）则同时看两边：只有其中一个人会的全部内容。

BTreeMap 和 BTreeSet：始终有序

BTreeMap 的用法和 HashMap 一样，BTreeSet 的用法和 HashSet 一样。区别在于：它们会让键始终保持有序。遍历时，每次拿到的键都是排好序的。

use std::collections::{BTreeMap, BTreeSet};

fn main() {
    let text = "the cat sat on the mat the end";

    let mut counts: BTreeMap<&str, u32> = BTreeMap::new();
    for word in text.split_whitespace() {
        *counts.entry(word).or_insert(0) += 1;
    }
    for (word, count) in &counts {
        println!("{word}: {count}");
    }

    let scores: BTreeSet<u32> = BTreeSet::from([72, 95, 58, 88]);
    println!("最低分：{:?}", scores.first());
    println!("最高分：{:?}", scores.last());
    println!("全部：{:?}", scores);
}

输出：

cat: 1
end: 1
mat: 1
on: 1
sat: 1
the: 3
最低分：Some(58)
最高分：Some(95)
全部：{58, 72, 88, 95}

▶ 动手试一试

这里的 entry API 就是你在 HashMap 那一课见过的那个。因为这是一个 BTreeMap，单词会按字母顺序输出，不需要额外排序。句子特意保留了英文：split_whitespace 按空格切分单词，而中文句子的词与词之间没有空格。

该选哪一个？

• 默认选 HashMap / HashSet，查找通常更快。
• 需要数据有序时选 BTreeMap / BTreeSet：打印排好序的报表、找出最小或最大的键，或者取出某个范围内的键。

VecDeque：队列

VecDeque（读作“vec deck”）是一个可以在两端快速添加和删除元素的列表。这让它天然适合做队列：先进先出，就像排队的人一样。

use std::collections::VecDeque;

fn main() {
    let mut line: VecDeque<&str> = VecDeque::new();
    line.push_back("小李");
    line.push_back("小王");
    line.push_back("小陈");

    while let Some(person) = line.pop_front() {
        println!("正在接待{person}，还有 {} 人在等", line.len());
    }
}

输出：

正在接待小李，还有 2 人在等
正在接待小王，还有 1 人在等
正在接待小陈，还有 0 人在等

▶ 动手试一试

这件事也可以用 Vec::remove(0) 来做，但那样会把其余每个元素都往前挪一位。VecDeque 的 pop_front 不需要挪动，所以队伍再长也一样快。

该用哪种集合？

集合	适合的场景	例子
Vec<T>	有序列表，按位置访问	文件的每一行、一组分数
HashMap<K, V>	按键快速查找值	用户名 → 用户资料
HashSet<T>	不重复的值，快速判断“在不在里面”	访问过的页面、屏蔽词
BTreeMap<K, V>	键 → 值，键保持有序	按字母顺序打印的单词计数
VecDeque<T>	在两端添加或删除	任务或消息队列

拿不准的时候，就先用 Vec。等你发现自己在反复搜索它（换成集合或 map），或者经常从开头删除元素（换成 VecDeque）时，再换也不迟。

常见误区

把自己的结构体放进 HashSet，却没有加上需要的 derive。 HashSet 需要对它的值计算哈希，并比较它们是否相等。你的结构体不会自动具备这些能力：

use std::collections::HashSet;

struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let mut visited = HashSet::new();
    visited.insert(Point { x: 0, y: 0 });
}

error[E0277]: the trait bound `Point: Eq` is not satisfied
  --> src/main.rs:10:13
   |
10 |     visited.insert(Point { x: 0, y: 0 });
   |             ^^^^^^ the trait `Eq` is not implemented for `Point`

error[E0277]: the trait bound `Point: Hash` is not satisfied
  --> src/main.rs:10:13
   |
10 |     visited.insert(Point { x: 0, y: 0 });
   |             ^^^^^^ the trait `Hash` is not implemented for `Point`

编译器说的是：Point 没有实现 Eq trait，也没有实现 Hash trait。修复方法只需要在结构体上面加一行：#[derive(PartialEq, Eq, Hash)]。如果是 BTreeSet，还需要 PartialOrd 和 Ord，这样它才知道怎么排序。这些 trait 分别是什么意思，可以看常用 trait 那一课。

use std::collections::HashSet;

#[derive(PartialEq, Eq, Hash)]
struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let mut visited = HashSet::new();
    visited.insert(Point { x: 0, y: 0 });
    visited.insert(Point { x: 1, y: 0 });
    visited.insert(Point { x: 0, y: 0 }); // 重复了，被忽略
    println!("走过了 {} 个格子", visited.len());
}

输出：

走过了 2 个格子

▶ 动手试一试

更进一步

需要一个队列（先进先出），或者想“每次都拿到最大的那个”？VecDeque 与 BinaryHeap 介绍了专门为此设计的两种集合。

练习

1. 第一个重复的词

给定单词列表 ["红色", "蓝色", "绿色", "蓝色", "红色"]，打印第一个出现第二次的词。提示：值已经在集合里时，insert 会返回 false，而 break 可以停止循环。

查看答案

use std::collections::HashSet;

fn main() {
    let words = ["红色", "蓝色", "绿色", "蓝色", "红色"];
    let mut seen = HashSet::new();

    for word in words {
        if !seen.insert(word) {
            println!("第一个重复的词：{word}");
            break;
        }
    }
}

输出：

第一个重复的词：蓝色

▶ 动手试一试

!seen.insert(word) 读作“插入失败了”，也就是“这个我以前见过”。"蓝色" 是第一个重复的词。"红色" 也重复了，但出现得更晚。

2. 按字母顺序数字母

统计 "mississippi" 里每个字母出现了多少次，并按字母顺序打印出来。提示：用一个 BTreeMap，配合 BTreeMap 那一节里同样的 entry(...).or_insert(0) 技巧，再遍历 word.chars()。

查看答案

use std::collections::BTreeMap;

fn main() {
    let word = "mississippi";
    let mut counts = BTreeMap::new();

    for letter in word.chars() {
        *counts.entry(letter).or_insert(0) += 1;
    }

    for (letter, count) in &counts {
        println!("{letter}: {count}");
    }
}

输出：

i: 4
m: 1
p: 2
s: 4

▶ 动手试一试

如果用 HashMap，这四行可能以任意顺序输出。BTreeMap 让键保持有序，所以 i、m、p、s 每次都按字母顺序打印。

总结

• HashSet 存储不重复的值。insert 和 remove 返回一个 bool，告诉你集合有没有变化。
• 在集合上调用 contains 很快，集合再大也一样；在 Vec 上则要逐个检查每个元素。
• union、intersection、difference 和 symmetric_difference 用来做集合运算。打印前先把结果排好序。
• BTreeMap 和 BTreeSet 让键保持有序，在意顺序时就用它们。
• VecDeque 是做队列的首选：用 push_back 排进队尾，用 pop_front 离开队头。

小测验

小测验

1. 如果 x 已经在集合里，set.insert(x) 会返回什么？

true 一个错误 false 旧的值

2. 你想按字母顺序打印单词计数，又不想自己排序。哪种 map 最合适？

HashMap BTreeMap Vec VecDeque

3. 为什么用 {:?} 打印同一个 HashSet，每次运行的输出可能不一样？

因为 HashSet 没有固定的顺序 因为 {:?} 是随机的 因为集合里的值会随时间丢失 因为这只在调试模式下发生

4. 哪种集合最适合做先进先出的队列？

HashSet BTreeSet HashMap VecDeque

得分: 0 / 4

延伸阅读

• std::collections 概览 — 标准库文档（英文）：一篇更详细的集合选择指南，列出了每种操作的速度。
• 散列集 HashSet — 通过例子学 Rust：union、intersection 和 difference 的可运行示例。
• HashSet — 标准库文档（英文）：集合的全部方法，包括 is_subset 和 retain。
• BTreeMap — 标准库文档（英文）：有序 map 的用法，包括用 range 取出一段键。
• VecDeque — 标准库文档（英文）：队列的全部方法，比如 push_front、pop_back 和 front。