rust/std/collections/readme.md

在 Rust 里，std::collections 其实不只有 HashMap 和 HashSet。标准库给的集合虽然不多，但每一个都很经典，而且用途非常明确。整体大概可以分成三类：

1️⃣ 哈希结构 2️⃣ 有序结构（树） 3️⃣ 队列 / 双端结构

我给你完整列一遍，并且说明用途和核心方法。

---

一、Hash 类（你已经在用）

use std::collections::{HashMap, HashSet};

1 HashMap<K,V>

哈希表键值对。

特点：

• O(1) 平均查找
• 无序
• 最常用

常见用途：

• 字典
• 统计
• cache

你已经基本掌握。

---

2 HashSet<T>

哈希集合。

特点：

• 元素唯一
• 无序
• 基于 HashMap 实现

常见用途：

• 去重
• 集合运算

---

二、有序结构（基于红黑树）

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

Rust 标准库没有 TreeMap，而是 BTree。

原因：

BTree 对 CPU cache 更友好。

---

3 BTreeMap<K,V>

有序 map。

特点：

• key 自动排序
• O(log n) 查询

例子：

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert(3, "c");
map.insert(1, "a");
map.insert(2, "b");

for (k,v) in &map {
    println!("{} {}", k, v);
}

输出：

1 a
2 b
3 c

---

常见方法

基本和 HashMap 一样：

insert
get
remove
contains_key
entry

但多了 范围查询：

map.range(2..5)

这个功能非常强。

例如：

for (k,v) in map.range(10..20) {
}

---

使用场景

• 排序数据
• 区间查询
• ordered dictionary

---

4 BTreeSet<T>

有序集合。

特点：

• 自动排序
• 唯一元素

例子：

use std::collections::BTreeSet;

let mut set = BTreeSet::new();

set.insert(3);
set.insert(1);
set.insert(2);

for v in &set {
    println!("{}", v);
}

输出：

1
2
3

---

三、队列结构

5 VecDeque<T>

双端队列。

use std::collections::VecDeque;

结构：

head -> circular buffer <- tail

特点：

• 两端 O(1) 插入删除
• 比 Vec 更适合做队列

---

常见方法

插入：

push_back()
push_front()

删除：

pop_back()
pop_front()

查看：

front()
back()

例子：

let mut q = VecDeque::new();

q.push_back(1);
q.push_back(2);
q.push_front(0);

println!("{:?}", q);

---

使用场景

• BFS
• 任务队列
• sliding window

---

四、链表

6 LinkedList<T>

use std::collections::LinkedList;

双向链表。

操作：

push_back
push_front
pop_back
pop_front

例子：

let mut list = LinkedList::new();

list.push_back(1);
list.push_back(2);
list.push_front(0);

---

⚠️ Rust 官方建议：

尽量不要用 LinkedList。

原因：

• cache locality 差
• VecDeque 更快

除非：

• 频繁 splice
• 复杂链表操作

---

五、BinaryHeap（非常重要）

7 BinaryHeap<T>

use std::collections::BinaryHeap;

二叉堆。

默认：

最大堆

例子：

let mut heap = BinaryHeap::new();

heap.push(3);
heap.push(1);
heap.push(5);

println!("{:?}", heap.pop());

输出：

Some(5)

---

常见方法

push
pop
peek
len
is_empty

---

变成最小堆

使用：

std::cmp::Reverse

例子：

use std::cmp::Reverse;

let mut heap = BinaryHeap::new();

heap.push(Reverse(3));
heap.push(Reverse(1));

println!("{:?}", heap.pop());

---

使用场景

• Dijkstra
• 优先队列
• 调度系统

---

六、collections 全部结构总结

Rust 标准库集合其实只有 7 个核心结构：

HashMap
HashSet
BTreeMap
BTreeSet
VecDeque
LinkedList
BinaryHeap

---

七、Rust collections 使用频率排行（真实项目）

大致是：

HashMap      ⭐⭐⭐⭐⭐
VecDeque     ⭐⭐⭐⭐
HashSet      ⭐⭐⭐⭐
BinaryHeap   ⭐⭐⭐
BTreeMap     ⭐⭐
BTreeSet     ⭐⭐
LinkedList   ⭐

---

八、很多人不知道的一点

Rust 最常用容器其实是 Vec：

Vec<T>

但它在：

std::vec

不是 collections。

原因：

Vec 太重要了，直接放 core。

---

九、如果你想系统练习 Rust collections

我非常推荐你写这几个小项目：

1️⃣ 词频统计

HashMap

2️⃣ LRU Cache

HashMap + LinkedList

3️⃣ Dijkstra

BinaryHeap

4️⃣ 任务调度器

BinaryHeap + HashMap

5️⃣ 滑动窗口最大值

VecDeque

---

如果你愿意，我可以再给你一个：

🔥「Rust collections 深度指南（90% Rust 程序员不知道的细节）」

比如：

• 为什么 Rust 没有 TreeMap
• 为什么 LinkedList 几乎没人用
• HashMap 为什么这么快
• BTreeMap 内部结构其实不是二叉树

这些底层实现其实非常有意思。