集合与容器

📚 Rust 课程系列
课程概览
基础语法
函数与输入输出
所有权、借用与生命周期
结构体、枚举与模式匹配
类型系统：泛型、trait 与多态
集合与容器（本文）
错误处理与 Panic 恢复
模块、属性与宏
智能指针、迭代器与闭包
并发与异步编程
Unsafe Rust 与常用 trait 详解
工具链、Cargo 与外部 crate
最佳实践、性能与调试

集合（容器）是日常编程最常用的数据结构。Rust 标准库在 std::collections 下提供了一组覆盖常见场景的容器：动态数组 Vec、双端队列 VecDeque、哈希表 HashMap/HashSet、有序映射 BTreeMap/BTreeSet、链表 LinkedList 和二叉堆 BinaryHeap。本章逐一介绍它们的结构特点、典型用法、性能权衡与选用指南。各容器完整方法表见延伸阅读《Rust Containers》。

容器总览

类别	容器	特点
序列	`Vec<T>`、`VecDeque<T>`、`LinkedList<T>`	按插入顺序存放，可按位置或顺序访问
映射	`HashMap<K,V>`、`BTreeMap<K,V>`	键值对，按键查找
集合	`HashSet<T>`、`BTreeSet<T>`	仅键，去重/成员判断
堆	`BinaryHeap<T>`	优先队列，快速取最值

Vec、HashMap、BTreeMap 覆盖了绝大多数场景；其余容器在特定需求下才登场。

Vec<T>：动态数组

Vec<T> 是最常用的容器，在堆上存储连续的同类型元素，容量随需增长。

let mut v = Vec::new();
v.push(1);

let v2 = vec![1, 2, 3];           // 宏创建
let v3 = vec![0; 5];              // [0, 0, 0, 0, 0]

容量与增长策略：Vec 内部维护「容量」（已分配槽位数）和「长度」（实际元素数）。当长度超过容量时，Vec 重新分配更大的内存（通常翻倍）并搬移旧元素。因此 push 是 O(1) 均摊成本，但偶发的重分配会带来一次 O(n) 拷贝。

💡 提示：当已知大小时使用 Vec::with_capacity(n) 预分配以避免重复分配——这是 Vec 最常见的性能优化手段。

1
2
3

let mut v = Vec::with_capacity(1000); // 一次性分配
for i in 0..1000 { v.push(i); }
v.shrink_to_fit(); // 归还多余容量

访问与删除速查：

操作	方法	复杂度	备注
索引访问	`v[i]`	O(1)	越界 panic
安全访问	`v.get(i)`	O(1)	返回 `Option<&T>`
末尾删除	`pop()`	O(1)	返回 `Option<T>`
中间删除	`remove(i)`	O(n)	后续元素前移
中间删除	`swap_remove(i)`	O(1)	与末尾交换后 pop，不保序

⚠️ 注意：swap_remove 虽然是 O(1)，但会打乱元素顺序。需要保序时只能用 remove。

🔄 对比：Rust 的 Vec ≈ C++ 的 std::vector / Go 的 slice / Java 的 ArrayList，但 Rust 的所有权系统保证不会出现悬垂引用——持有 &v[i] 时编译器会阻止你 push 新元素（因为 push 可能触发重分配使引用失效）。

VecDeque<T>：双端队列

VecDeque 基于环形缓冲（ring buffer），两端插入/删除都是 O(1) 均摊。适合队列、滑动窗口等场景：

use std::collections::VecDeque;

let mut deque = VecDeque::new();
deque.push_back(2);
deque.push_front(1);     // [1, 2]
deque.push_back(3);      // [1, 2, 3]
assert_eq!(deque.pop_front(), Some(1));
assert_eq!(deque.pop_back(), Some(3));

💡 提示：需要 FIFO 队列时优先选 VecDeque 而非 Vec——Vec 的 remove(0) 是 O(n)，而 VecDeque 的 pop_front 是 O(1)。

HashMap<K, V>：哈希表

HashMap 用哈希表实现键值映射，平均 O(1) 的查找/插入/删除，但无序。

1
2
3

use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);

⚠️ 注意：键类型必须实现 Hash + Eq。所有整数、String/&str、元组（元素均实现 Hash+Eq）等自动满足；自定义类型需 derive 或手动实现。

哈希算法（进阶）

默认使用 SipHash-1-3，抗哈希碰撞攻击（防止恶意输入触发最坏 O(n) 退化），但相对慢。若性能敏感且键可信，可换更快的 hasher：

1 2	`use std::hash::BuildHasherDefault; type FastMap<K, V> = HashMap<K, V, BuildHasherDefault<fnv::FnvHasher>>;`

🔄 对比：Go 的 map 和 Java 的 HashMap 也使用类似策略，但 Rust 默认选择安全优先的 SipHash，而 C++ std::unordered_map 默认哈希函数不抗碰撞攻击。

Entry API

entry API 是 HashMap 最惯用的技巧——一次查找完成「存在则读，不存在则写」，避免重复查找：

let mut counts: HashMap<&str, u32> = HashMap::new();
for word in ["a", "b", "a", "c", "b", "a"] {
    *counts.entry(word).or_insert(0) += 1; // 不存在则插入 0
}
// {"a": 3, "b": 2, "c": 1}

💡 提示：or_insert(v) 总会求值 v（即使键已存在）；若默认值计算昂贵，用 or_insert_with(|| expensive()) 只在需要时才计算。值为 Default 时可用 or_default() 更简洁。

BTreeMap<K, V>：有序映射

BTreeMap 基于 B 树，按键有序排列，查找/插入/删除为 O(log n)，支持按范围遍历。当需要按键排序或范围查询时用它替代 HashMap：

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert("banana", 2);
map.insert("apple", 5);
map.insert("cherry", 3);

for (k, v) in &map { /* 按 key 字典序：apple, banana, cherry */ }

// 范围查询
for (k, v) in map.range("apple".."cherry") { /* [apple, banana) */ }

⚠️ 注意：键类型必须实现 Ord。BTreeMap 的插入/删除比 HashMap 慢（O(log n) vs O(1) 均摊），但遍历有序且无哈希开销。不需要顺序时优先用 HashMap。

🔄 对比：BTreeMap ≈ C++ 的 std::map / Java 的 TreeMap，但 Rust 的 B 树节点通常比 C++ 红黑树节点缓存更友好（B 树节点存多个元素）。

HashSet 与 BTreeSet

HashSet<T> 和 BTreeSet<T> 分别是 HashMap<T, ()> 和 BTreeMap<T, ()> 的集合版本，只存键，用于去重与成员判断：

use std::collections::HashSet;

let mut set = HashSet::new();
set.insert(1);
set.insert(2);
set.insert(1); // 重复，返回 false
assert_eq!(set.len(), 2);

// 集合运算
let a: HashSet<_> = [1, 2, 3].into_iter().collect();
let b: HashSet<_> = [2, 3, 4].into_iter().collect();
let inter: HashSet<_> = a.intersection(&b).cloned().collect();   // {2, 3}
let union:  HashSet<_> = a.union(&b).cloned().collect();         // {1,2,3,4}
let diff:   HashSet<_> = a.difference(&b).cloned().collect();    // {1}

💡 提示：集合运算返回的是引用的迭代器，需要 .cloned().collect() 才能得到新的 HashSet。BTreeSet 同样支持 intersection/union/difference/symmetric_difference，且结果保持有序。

LinkedList<T>：双向链表（慎用）

LinkedList<T> 两端 O(1) 操作，但缓存不友好、随机访问 O(n)。在 Rust 中绝大多数「想用链表」的场景用 Vec/VecDeque 更快更简单。

⚠️ 注意：LinkedList 主要在需要频繁从中间拆分/拼接（split_off/append）时才考虑。官方也建议谨慎使用——Rust 的所有权模型使链表操作比 C/C++ 更繁琐（需要 unsafe 或 Rc<RefCell<>> 才能实现双向引用）。

🔄 对比：C++ 的 std::list 在中间插入 O(1) 常被使用，但 Rust 的 LinkedList 因所有权限制几乎无法直接操作中间节点，实用性远低于 C++ 版本。

BinaryHeap<T>：二叉堆

BinaryHeap<T> 是最大二叉堆，常作优先队列：peek O(1)，push/pop O(log n)。

use std::collections::BinaryHeap;

let mut heap = BinaryHeap::new();
heap.push(3);
heap.push(1);
heap.push(2);
assert_eq!(heap.peek(), Some(&3)); // 最大值在堆顶
assert_eq!(heap.pop(), Some(3));   // 按降序弹出

要最小堆或自定义顺序，用 Reverse 包装或实现自定义 Ord：

use std::cmp::Reverse;
let mut min_heap: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
min_heap.push(Reverse(3));
min_heap.push(Reverse(1));
assert_eq!(min_heap.pop(), Some(Reverse(1))); // 最小值

💡 提示：BinaryHeap 要求元素实现 Ord。自定义优先级时，推荐用 Reverse 包装（零开销）而非实现反向 Ord——后者容易在别处引起混淆。

性能对比

容器	索引/查找	插入/删除	备注
`Vec<T>`	O(1) 索引	末尾 O(1) 均摊；中间 O(n)	连续内存，缓存友好
`VecDeque<T>`	O(1) 索引	两端 O(1) 均摊；中间 O(n)	环形缓冲
`HashMap<K,V>`	O(1) 均摊	O(1) 均摊	无序，需 `Hash` + `Eq`
`BTreeMap<K,V>`	O(log n)	O(log n)	有序，需 `Ord`
`HashSet`/`BTreeSet`	同对应 Map	同对应 Map	无值
`LinkedList<T>`	O(n)	两端 O(1)；中间 O(1)（已知游标）	缓存不友好，慎用
`BinaryHeap<T>`	peek O(1)	push/pop O(log n)	最大堆

选用指南

需求	推荐
一组同类型元素，按下标访问	`Vec`
两端频繁增删（队列/滑动窗口）	`VecDeque`
键值映射、查找为主、不关心顺序	`HashMap`
键值映射、需要按键排序或范围查询	`BTreeMap`
去重 / 成员判断 / 集合运算	`HashSet`（无序）或 `BTreeSet`（有序）
取最值 / 优先队列	`BinaryHeap`
频繁从中间拆分/拼接	`LinkedList`（默认优先考虑 `Vec`）

并发集合

标准库的集合不是线程安全的——它们没有实现内部同步，跨线程共享可变集合需要外部锁。

use std::sync::{Arc, Mutex};
use std::collections::HashMap;

let counts = Arc::new(Mutex::new(HashMap::<u32, u32>::new()));
let c = Arc::clone(&counts);
std::thread::spawn(move || {
    let mut m = c.lock().unwrap();
    *m.entry(1).or_insert(0) += 1;
});

⚠️ 注意：Arc<Mutex<HashMap<...>>> 简单但锁粒度粗，竞争激烈时性能差。读多写少可用 Arc<RwLock<...>>，但注意 RwLock 可能导致写饥饿。

🔬 进阶：更高吞吐可使用第三方并发数据结构如 dashmap，它采用分片锁（sharded locking）显著降低锁竞争：

1
2
3

use dashmap::DashMap;
let map = DashMap::new();
map.insert("a", 1); // 多线程可直接并发写入，无需外部 Mutex

🔄 对比：Java 有 ConcurrentHashMap、Go 有 sync.Map，Rust 标准库没有内置并发 map——这是 Rust 的设计哲学：零成本抽象意味着不为单线程场景支付同步开销，并发需求交给第三方 crate。

与迭代器配合

集合与迭代器适配器天然契合，collect() 可把迭代器结果收集回任意实现了 FromIterator 的集合：

let v = vec![1, 2, 3, 4, 5];
let doubled: Vec<i32> = v.iter().map(|x| x * 2).collect();
let evens: Vec<&i32> = v.iter().filter(|x| *x % 2 == 0).collect();

// 直接收集成不同容器
let set: std::collections::HashSet<i32> = v.iter().cloned().collect();
let map: std::collections::HashMap<i32, i32> = v.iter().cloned().map(|x| (x, x * x)).collect();

💡 提示：collect() 需要类型标注让编译器推断目标容器。当推断歧义时，用「turbofish」语法：v.iter().cloned().collect::<HashSet<_>>()。

迭代器的完整方法与惰性求值细节见《智能指针、迭代器与闭包》。

延伸阅读：Rust Containers（每个容器的创建方法、常用方法表、性能特点与适用场景的完整参考）。