16. Collections — 集合类型

Rust 标准库提供了丰富的集合类型——它们是数据结构的基石，但 Rust 版本与其它语言有根本的不同。Rust 的 move 语义避免了意外的深拷贝，借用检查器在编译时防止悬垂指针，Option 替代了 null——这些特性使得 Rust 集合既高效又安全。本章深入探讨每种集合的特性、性能特征和最佳使用场景。

集合类型总览

标准库中 8 种核心集合：

集合类型	数据结构	C++ 对应	Java 对应	Python 对应
Vec<T>	可增长数组	vector<T>	ArrayList<T>	list
VecDeque<T>	双端队列（环形缓冲）	deque<T>	ArrayDeque<T>	collections.deque
LinkedList<T>	双向链表	list<T>	LinkedList<T>	—
BinaryHeap<T>	最大堆（优先队列）	priority_queue<T>	PriorityQueue<T>	heapq
HashMap<K,V>	哈希表	unordered_map<K,V>	HashMap<K,V>	dict
BTreeMap<K,V>	有序映射（B 树）	map<K,V>	TreeMap<K,V>	—
HashSet<T>	哈希集合	unordered_set<T>	HashSet<T>	set
BTreeSet<T>	有序集合	set<T>	TreeSet<T>	—

Vec<T>：可增长数组

Vec<T> 是 Rust 中使用最频繁的集合——它是一个在堆上分配的连续数组，支持高效的随机访问和尾部插入。

创建

// vec! 宏
let v: Vec<i32> = vec![1, 2, 3, 4, 5];

// 指定容量
let v: Vec<i32> = Vec::with_capacity(1000);

// 从迭代器收集
let v: Vec<i32> = (0..10).collect();

// 填充默认值
let v = vec![0; 100];  // 100 个 0

// 通过 resize
let mut v = Vec::new();
v.resize(5, 42);  // [42, 42, 42, 42, 42]

访问元素

let v = vec![10, 20, 30, 40, 50];

// 索引——越界会 panic
assert_eq!(v[0], 10);
assert_eq!(v[2], 30);

// 安全访问——返回 Option
assert_eq!(v.get(0), Some(&10));
assert_eq!(v.get(100), None);

// 首尾
assert_eq!(v.first(), Some(&10));
assert_eq!(v.last(), Some(&50));

// 切片
let slice: &[i32] = &v[1..4];
assert_eq!(slice, &[20, 30, 40]);

增删元素

let mut v = vec![1, 2, 3];

// 尾部操作——O(1)（均摊）
v.push(4);           // [1, 2, 3, 4]
v.pop();             // 返回 Some(4)，vec = [1, 2, 3]

// 任意位置——O(n)（需要移动后续元素）
v.insert(1, 99);     // [1, 99, 2, 3]
v.remove(1);         // 返回 99，vec = [1, 2, 3]

// 交换删除——O(1)（与尾部元素交换后弹出）
v.swap_remove(0);    // 返回 1，vec = [3, 2]

容量管理

Vec 在堆上分配连续内存。当 push 超出当前容量时，Rust 自动重新分配——通常是当前容量的 2 倍：

let mut v: Vec<i32> = Vec::new();

assert_eq!(v.capacity(), 0);
v.push(1);
assert_eq!(v.capacity(), 4);  // 第一次分配 4 个元素空间

// 预分配——避免多次重新分配
let mut v = Vec::with_capacity(1000);
assert_eq!(v.capacity(), 1000);

for i in 0..1000 {
    v.push(i);  // 不会重新分配
}

// 收缩容量
v.shrink_to_fit();
// 或保留至少指定容量
v.reserve(500);  // 保证至少还能放 500 个元素
v.reserve_exact(500);  // 精确分配

批量操作

let mut v1 = vec![1, 2, 3];
let mut v2 = vec![4, 5, 6];

// append——将 v2 的所有元素移到 v1 尾部（v2 变为空）
v1.append(&mut v2);
assert_eq!(v1, vec![1, 2, 3, 4, 5, 6]);
assert!(v2.is_empty());

// extend——从迭代器添加
v1.extend([7, 8, 9].iter().copied());

// split_off——在指定位置分割
let mut v = vec![1, 2, 3, 4, 5];
let right = v.split_off(3);
assert_eq!(v, vec![1, 2, 3]);
assert_eq!(right, vec![4, 5]);

筛选与去重

let mut v = vec![1, 2, 3, 4, 5, 6, 7, 8];

// retain——保留满足条件的元素
v.retain(|&n| n % 2 == 0);
assert_eq!(v, vec![2, 4, 6, 8]);

// drain——移出元素（返回迭代器）
let drained: Vec<i32> = v.drain(..2).collect();
assert_eq!(drained, vec![2, 4]);
assert_eq!(v, vec![6, 8]);

// dedup——去除相邻重复
let mut v = vec![1, 2, 2, 3, 3, 3, 4];
v.dedup();
assert_eq!(v, vec![1, 2, 3, 4]);

// dedup_by——自定义去重条件
let mut v = vec!["foo", "bar", "Bar", "baz"];
v.dedup_by(|a, b| a.eq_ignore_ascii_case(b));
assert_eq!(v, vec!["foo", "bar", "baz"]);

排序与搜索

let mut v = vec![3, 1, 4, 1, 5, 9, 2, 6];

v.sort();                       // 升序——[1, 1, 2, 3, 4, 5, 6, 9]
v.sort_by(|a, b| b.cmp(a));     // 自定义比较
v.sort_by_key(|&x| -x);         // 按键排序

// binary_search——前提是已排序
assert_eq!(v.binary_search(&5), Ok(某索引));

// contains
assert!(v.contains(&4));

借用检查器防止失效

这是 Rust 集合最独特的优势——在编译时防止迭代器失效：

// 这段代码在 Python、Java、C++ 中可能运行错误，
// 但在 Rust 中直接编译失败
let mut v = vec![1, 2, 3, 4, 5];

// for item in &v {
//     v.push(*item * 10);  // 编译错误！
//     // 在迭代过程中修改 v 会使其迭代器失效
// }

// 正确的做法：使用 retain 或 collect 到新 Vec
let v2: Vec<i32> = v.iter().flat_map(|&x| vec![x, x * 10]).collect();

VecDeque<T>：双端队列

VecDeque 是用环形缓冲区实现的双端队列——支持 O(1) 的头部和尾部插入/删除：

use std::collections::VecDeque;

let mut deque = VecDeque::new();

// 两端操作——全部 O(1)
deque.push_back(3);    // [3]
deque.push_front(2);   // [2, 3]
deque.push_back(4);    // [2, 3, 4]
deque.push_front(1);   // [1, 2, 3, 4]

assert_eq!(deque.pop_front(), Some(1));
assert_eq!(deque.pop_back(), Some(4));

// 索引访问——O(1)
assert_eq!(deque[0], 2);
assert_eq!(deque[1], 3);

// 转为连续切片
let slice: &mut [i32] = deque.make_contiguous();
slice.sort();

// Vec <-> VecDeque
let v = Vec::from(deque);
let deque = VecDeque::from(v);

使用场景：需要高效的头部操作（如任务队列、滑动窗口、撤销重做缓冲区）。

BinaryHeap<T>：优先队列

BinaryHeap 是一个最大堆——.pop() 返回最大值：

use std::collections::BinaryHeap;

let mut heap = BinaryHeap::new();
heap.push(3);
heap.push(1);
heap.push(5);
heap.push(2);

assert_eq!(heap.peek(), Some(&5));   // 查看最大值
assert_eq!(heap.pop(), Some(5));     // 取出最大值
assert_eq!(heap.pop(), Some(3));
assert_eq!(heap.pop(), Some(2));
assert_eq!(heap.pop(), Some(1));

BinaryHeap 要求 T: Ord。对于 f64，需要使用比较包装器。

peek_mut() 允许条件性地修改堆顶：

let mut heap = BinaryHeap::from(vec![5, 3, 8]);

if let Some(mut top) = heap.peek_mut() {
    if *top > 5 {
        *top = 5;  // 修改后堆自动调整
    }
}
// 堆现在为 [5, 3, 5]

注意：.iter() 产生的元素顺序不确定——要用优先顺序消费，必须用 while let Some(item) = heap.pop() 循环。

BinaryHeap 默认是最大堆。要实现最小堆，可以用 std::cmp::Reverse：

use std::collections::BinaryHeap;
use std::cmp::Reverse;

let mut heap = BinaryHeap::new();
heap.push(Reverse(3));
heap.push(Reverse(1));
heap.push(Reverse(5));

assert_eq!(heap.pop(), Some(Reverse(1)));  // 最小元素先出

HashMap<K, V>：哈希映射

HashMap 是 Rust 中使用最广泛的键值映射：

use std::collections::HashMap;

let mut scores = HashMap::new();

// 插入
scores.insert(String::from("Alice"), 95);
scores.insert(String::from("Bob"), 82);

// 访问
assert_eq!(scores.get("Alice"), Some(&95));
assert_eq!(scores.get("Charlie"), None);

// 索引语法——缺失时 panic
// let s = scores["Charlie"];  // panic!

// 检查存在
assert!(scores.contains_key("Alice"));

// 移除
let removed = scores.remove("Bob");
assert_eq!(removed, Some(82));

Entry API

entry 方法是 Rust 的独特设计——一次哈希查找完成“检查或插入”：

let mut word_counts: HashMap<String, usize> = HashMap::new();

for word in "the brown fox and the quick dog".split_whitespace() {
    // 一次哈希查找：
    // - 存在：返回 &mut V
    // - 不存在：插入默认值，返回 &mut V
    *word_counts.entry(word.to_string()).or_insert(0) += 1;
}

println!("{:?}", word_counts);
// {"the": 2, "brown": 1, "fox": 1, ...}

entry 的组合方法：

let mut map = HashMap::new();

// or_insert——插入默认值
map.entry("a").or_insert(1);

// or_insert_with——惰性计算默认值
map.entry("b").or_insert_with(|| expensive_computation());

// and_modify——先修改已存在的值
map.entry("a")
    .and_modify(|v| *v *= 2)
    .or_insert(1);

// or_default——使用 Default trait
map.entry("c").or_default();  // 对于 i32 插入 0

异构查找与 Borrow

HashMap::get 不要求参数类型完全匹配 K——只要 K: Borrow<Q> 且 Q: Hash + Eq：

let mut map: HashMap<String, i32> = HashMap::new();
map.insert("hello".to_string(), 42);

// 不需要先构造 String！直接用 &str 查找
assert_eq!(map.get("hello"), Some(&42));

// 这之所以有效，是因为
// String: Borrow<str>
// &str: Hash + Eq

HashMap vs BTreeMap

特性	HashMap	BTreeMap
底层结构	哈希表	B 树
查找	O(1) 平均	O(log n)
插入	O(1) 平均	O(log n)
内存	可能浪费	紧凑
有序	无	键排序
范围查询	不支持	.range(..) 支持
DoS 防护	SipHash	N/A
自定义哈希	BuildHasher	无法自定义

选择规则：

• 需要按键排序遍历或范围查询时 → BTreeMap
• 需要极致查找性能 → HashMap
• 键很大时 → BTreeMap（不需要哈希计算）

哈希算法

Rust 默认使用 SipHash-1-3——一种加密强度的哈希算法，提供了 HashDoS 防护。每次创建 HashMap 时使用一个随机密钥，使得攻击者无法预测哈希冲突。

对于性能敏感的小键（如整数），可以切换为更快的哈希器：

use std::collections::HashMap;
use std::hash::BuildHasherDefault;
use fnv::FnvHasher;

// FNV 哈希——对整数键极快
type FnvMap<K, V> = HashMap<K, V, BuildHasherDefault<FnvHasher>>;

let mut map: FnvMap<u64, String> = FnvMap::default();
map.insert(1, "one".into());

BTreeMap<K, V>：有序映射

BTreeMap 按键的排序顺序维护键值对。它是 B 树（而非二叉树）实现——在现代硬件上 B 树比二叉树有更好的缓存局部性：

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert(3, "three");
map.insert(1, "one");
map.insert(4, "four");
map.insert(2, "two");

// 迭代时按键的升序
for (key, value) in &map {
    println!("{key}: {value}");
}
// 输出: 1: one, 2: two, 3: three, 4: four

// 范围查询
let range: Vec<_> = map.range(2..4).collect();
assert_eq!(range, vec![(&2, &"two"), (&3, &"three")]);

// split_off——将大于等于指定键的元素分离为新 map
let right = map.split_off(&3);
// 现在 map 包含 {1, 2}, right 包含 {3, 4}

HashSet<T> 和 BTreeSet<T>

两种集合都是基于对应 Map 的封装（HashSet<T> ~ HashMap<T, ()>）——功能和使用方式统一：

use std::collections::HashSet;

let mut set = HashSet::new();
set.insert("apple");
set.insert("banana");
set.insert("orange");

assert!(set.contains("apple"));
assert!(!set.contains("grape"));
assert_eq!(set.len(), 3);

// 插入已存在的值——返回 false
assert!(!set.insert("apple"));

集合运算

use std::collections::HashSet;

let a: HashSet<_> = [1, 2, 3, 4, 5].iter().cloned().collect();
let b: HashSet<_> = [4, 5, 6, 7, 8].iter().cloned().collect();

// 交集
let intersection: HashSet<_> = &a & &b;
assert_eq!(intersection, [4, 5].iter().cloned().collect());

// 并集
let union: HashSet<_> = &a | &b;
assert_eq!(union.len(), 8);

// 差集
let difference: HashSet<_> = &a - &b;
assert_eq!(difference, [1, 2, 3].iter().cloned().collect());

// 对称差
let sym_diff: HashSet<_> = &a ^ &b;
assert_eq!(sym_diff, [1, 2, 3, 6, 7, 8].iter().cloned().collect());

// 子集/超集检查
assert!(!a.is_subset(&b));
assert!(a.is_disjoint(&HashSet::from([10, 11])));
assert!(a.is_superset(&HashSet::from([1, 2])));

运算符方法也提供了对应的函数调用形式：.intersection(), .union(), .difference(), .symmetric_difference()——这些返回迭代器而不是新集合，适合大集合场景。

LinkedList<T> 与何时不用它

LinkedList 是双向链表——但在 Rust 中几乎总是不推荐使用：

操作	Vec	LinkedList
索引访问	O(1)	O(n)
尾部插入	O(1)*	O(1)
头部插入	O(n)	O(1)
任意插入	O(n)	O(n)（需要先遍历）
内存开销	小（单块分配）	大（每节点单独分配 + 指针）
缓存局部性	优秀	差（节点分散）

即使在头部插入频繁的场景，VecDeque 通常也是更好的选择（环形缓冲，O(1) 双端操作 + 更好的缓存局部性）。只有在需要在遍历中分割/合并列表的特定场景下才考虑 LinkedList。

性能特征对比表

操作	Vec	VecDeque	HashMap	BTreeMap
索引访问	O(1)	O(1)	—	—
键查找	—	—	O(1) 平均	O(log n)
尾部插入	O(1)*	O(1)*	O(1)*	O(log n)
头部插入	O(n)	O(1)*	O(1)*	O(log n)
任意插入/删除	O(n)	O(n)	O(1)*	O(log n)
有序遍历	O(n)	O(n)	O(n) 无序	O(n) 有序
范围查询	支持	支持	不支持	.range()
内存效率	高	高	中	中

*均摊复杂度

选择正确的集合

决策流程：

1. 需要键值对 → HashMap 或 BTreeMap（看是否需要排序）
2. 需要唯一值集合 → HashSet 或 BTreeSet
3. 需要序列 + 索引访问 → Vec
4. 需要队列/栈 → VecDeque（或直接用 Vec 做栈）
5. 需要优先队列 → BinaryHeap
6. 需要 O(1) 检查存在性 → HashSet
7. 需要有序序列 + 范围查询 → BTreeMap 或 BTreeSet

一般原则：从 Vec 和 HashMap 开始。它们是 Rust 中最优化、最常用的集合。除非有明确的原因为其它集合。

自定义哈希

实现自定义 Hash trait 以使自定义类型可以作为 HashMap 的键且正确工作：

use std::hash::{Hash, Hasher};

#[derive(Debug, PartialEq, Eq)]
struct Person {
    id: u64,
    name: String,
}

// 关键规则：如果 a == b，则 hash(a) == hash(b)
// 反之不一定成立（冲突允许存在）
impl Hash for Person {
    fn hash<H: Hasher>(&self, state: &mut H) {
        // 只哈希 id——与 PartialEq 保持一致
        self.id.hash(state);
    }
}

// 现在 Person 可以作为 HashMap 的键
// HashMap 的查找基于 id 匹配

小结

• Vec<T> 是最通用的集合——连续存储、O(1) 随机访问、自动增长。容量管理策略（2 倍扩展）平衡了空间和时间。
• HashMap 的 entry API 是 Rust 最优雅的设计之一——一次哈希查找完成“存在则修改，不存在则插入”。Borrow trait 支持用 &str 查找 HashMap<String, V>，无需构造临时 String。
• BTreeMap 是 B 树实现——利用缓存局部性在现代硬件上表现出色。支持按键范围和有序遍历。
• HashSet 和 BTreeSet 是 Map 的轻量封装——完整的集合运算支持（并/交/差/对称差），运算符重载语法自然清晰。
• VecDeque 用环形缓冲实现 O(1) 双端操作——比 LinkedList 更好的缓存局部性和更低的内存开销。LinkedList 在 Rust 中几乎总是有更好的替代品。
• 借用检查器在编译时防止迭代器失效——这是 Rust 相对 Python、Java、C++ 最根本的安全性优势。