633 lines
5.5 KiB
Markdown
633 lines
5.5 KiB
Markdown
好主意。`HashMap` 和 `HashSet` 是 Rust **最核心的标准库容器之一**，而且很多 Rust 代码都会围绕它们写。如果你打算系统试一遍，我建议按 **结构 → 常用方法 → 进阶 API → 迭代器 → 实用技巧** 这样理解，会非常清晰。
|
||
|
||
它们都在：
|
||
|
||
```rust
|
||
use std::collections::{HashMap, HashSet};
|
||
```
|
||
|
||
本质上：
|
||
|
||
* `HashMap<K, V>`：键值对
|
||
* `HashSet<T>`：只有键（本质上是 `HashMap<T, ()>`）
|
||
|
||
---
|
||
|
||
# 一、HashMap 结构
|
||
|
||
```rust
|
||
HashMap<K, V>
|
||
```
|
||
|
||
要求：
|
||
|
||
```rust
|
||
K: Eq + Hash
|
||
```
|
||
|
||
因为要进行哈希比较。
|
||
|
||
例子：
|
||
|
||
```rust
|
||
use std::collections::HashMap;
|
||
|
||
let mut map: HashMap<String, i32> = HashMap::new();
|
||
```
|
||
|
||
---
|
||
|
||
# 二、HashMap 创建方法
|
||
|
||
### 1 `new`
|
||
|
||
```rust
|
||
let map: HashMap<i32, i32> = HashMap::new();
|
||
```
|
||
|
||
---
|
||
|
||
### 2 `with_capacity`
|
||
|
||
提前分配空间。
|
||
|
||
```rust
|
||
let map: HashMap<i32, i32> = HashMap::with_capacity(100);
|
||
```
|
||
|
||
减少 rehash。
|
||
|
||
---
|
||
|
||
### 3 `from`
|
||
|
||
```rust
|
||
let map = HashMap::from([
|
||
("a", 1),
|
||
("b", 2),
|
||
]);
|
||
```
|
||
|
||
---
|
||
|
||
# 三、HashMap 基本操作
|
||
|
||
## 1 插入 `insert`
|
||
|
||
```rust
|
||
map.insert("apple", 3);
|
||
```
|
||
|
||
返回：
|
||
|
||
```rust
|
||
Option<V>
|
||
```
|
||
|
||
如果 key 已存在：
|
||
|
||
```rust
|
||
let old = map.insert("apple", 5);
|
||
```
|
||
|
||
`old = Some(3)`
|
||
|
||
---
|
||
|
||
## 2 获取 `get`
|
||
|
||
```rust
|
||
map.get("apple")
|
||
```
|
||
|
||
返回：
|
||
|
||
```rust
|
||
Option<&V>
|
||
```
|
||
|
||
例子：
|
||
|
||
```rust
|
||
if let Some(v) = map.get("apple") {
|
||
println!("{}", v);
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
## 3 获取可变值 `get_mut`
|
||
|
||
```rust
|
||
map.get_mut("apple")
|
||
```
|
||
|
||
返回：
|
||
|
||
```
|
||
Option<&mut V>
|
||
```
|
||
|
||
例子：
|
||
|
||
```rust
|
||
if let Some(v) = map.get_mut("apple") {
|
||
*v += 1;
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
## 4 删除 `remove`
|
||
|
||
```rust
|
||
map.remove("apple")
|
||
```
|
||
|
||
返回：
|
||
|
||
```
|
||
Option<V>
|
||
```
|
||
|
||
---
|
||
|
||
## 5 是否包含 key
|
||
|
||
```rust
|
||
map.contains_key("apple")
|
||
```
|
||
|
||
返回：
|
||
|
||
```
|
||
bool
|
||
```
|
||
|
||
---
|
||
|
||
# 四、Entry API（Rust最强HashMap接口）
|
||
|
||
Rust 的 HashMap **最强 API 是 `entry()`**。
|
||
|
||
它避免：
|
||
|
||
* 先查
|
||
* 再插入
|
||
|
||
这种两次查找。
|
||
|
||
---
|
||
|
||
## 1 entry
|
||
|
||
```rust
|
||
map.entry("apple")
|
||
```
|
||
|
||
返回：
|
||
|
||
```
|
||
Entry<K,V>
|
||
```
|
||
|
||
有两种：
|
||
|
||
```
|
||
Occupied
|
||
Vacant
|
||
```
|
||
|
||
---
|
||
|
||
## 2 or_insert
|
||
|
||
```rust
|
||
map.entry("apple").or_insert(0);
|
||
```
|
||
|
||
含义：
|
||
|
||
```
|
||
如果没有 -> 插入0
|
||
如果有 -> 返回已有值
|
||
```
|
||
|
||
返回：
|
||
|
||
```
|
||
&mut V
|
||
```
|
||
|
||
例子：
|
||
|
||
```rust
|
||
*map.entry("apple").or_insert(0) += 1;
|
||
```
|
||
|
||
经典 **词频统计**：
|
||
|
||
```rust
|
||
for word in words {
|
||
*map.entry(word).or_insert(0) += 1;
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
## 3 or_insert_with
|
||
|
||
延迟计算。
|
||
|
||
```rust
|
||
map.entry("key").or_insert_with(|| expensive());
|
||
```
|
||
|
||
只有需要时才计算。
|
||
|
||
---
|
||
|
||
## 4 and_modify
|
||
|
||
```rust
|
||
map.entry("apple")
|
||
.and_modify(|v| *v += 1)
|
||
.or_insert(1);
|
||
```
|
||
|
||
意思：
|
||
|
||
```
|
||
如果存在 -> 修改
|
||
如果不存在 -> 插入
|
||
```
|
||
|
||
非常常用。
|
||
|
||
---
|
||
|
||
# 五、HashMap 遍历
|
||
|
||
## 1 遍历 key value
|
||
|
||
```rust
|
||
for (k, v) in &map {
|
||
println!("{} {}", k, v);
|
||
}
|
||
```
|
||
|
||
类型：
|
||
|
||
```
|
||
(&K, &V)
|
||
```
|
||
|
||
---
|
||
|
||
## 2 只遍历 key
|
||
|
||
```rust
|
||
for k in map.keys() {
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
## 3 只遍历 value
|
||
|
||
```rust
|
||
for v in map.values() {
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
## 4 可变 value
|
||
|
||
```rust
|
||
for v in map.values_mut() {
|
||
*v += 1;
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
# 六、HashMap 容量操作
|
||
|
||
## len
|
||
|
||
```rust
|
||
map.len()
|
||
```
|
||
|
||
---
|
||
|
||
## is_empty
|
||
|
||
```rust
|
||
map.is_empty()
|
||
```
|
||
|
||
---
|
||
|
||
## clear
|
||
|
||
```rust
|
||
map.clear()
|
||
```
|
||
|
||
删除全部。
|
||
|
||
---
|
||
|
||
## capacity
|
||
|
||
```rust
|
||
map.capacity()
|
||
```
|
||
|
||
---
|
||
|
||
## reserve
|
||
|
||
```rust
|
||
map.reserve(100);
|
||
```
|
||
|
||
增加容量。
|
||
|
||
---
|
||
|
||
## shrink_to_fit
|
||
|
||
```rust
|
||
map.shrink_to_fit();
|
||
```
|
||
|
||
释放多余空间。
|
||
|
||
---
|
||
|
||
# 七、HashMap 进阶 API
|
||
|
||
## remove_entry
|
||
|
||
删除并返回 key value
|
||
|
||
```rust
|
||
map.remove_entry("apple")
|
||
```
|
||
|
||
返回：
|
||
|
||
```
|
||
Option<(K,V)>
|
||
```
|
||
|
||
---
|
||
|
||
## retain
|
||
|
||
过滤元素
|
||
|
||
```rust
|
||
map.retain(|k, v| *v > 10);
|
||
```
|
||
|
||
---
|
||
|
||
## drain
|
||
|
||
清空并返回迭代器
|
||
|
||
```rust
|
||
for (k, v) in map.drain() {
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
# 八、HashSet
|
||
|
||
HashSet 本质：
|
||
|
||
```
|
||
HashMap<T, ()>
|
||
```
|
||
|
||
所以 API 很类似。
|
||
|
||
---
|
||
|
||
# 九、HashSet 创建
|
||
|
||
```rust
|
||
use std::collections::HashSet;
|
||
|
||
let mut set = HashSet::new();
|
||
```
|
||
|
||
---
|
||
|
||
### from
|
||
|
||
```rust
|
||
let set = HashSet::from([1,2,3]);
|
||
```
|
||
|
||
---
|
||
|
||
### with_capacity
|
||
|
||
```rust
|
||
HashSet::with_capacity(100);
|
||
```
|
||
|
||
---
|
||
|
||
# 十、HashSet 基本操作
|
||
|
||
## insert
|
||
|
||
```rust
|
||
set.insert(10);
|
||
```
|
||
|
||
返回：
|
||
|
||
```
|
||
bool
|
||
```
|
||
|
||
是否新插入。
|
||
|
||
---
|
||
|
||
## contains
|
||
|
||
```rust
|
||
set.contains(&10);
|
||
```
|
||
|
||
---
|
||
|
||
## remove
|
||
|
||
```rust
|
||
set.remove(&10);
|
||
```
|
||
|
||
---
|
||
|
||
## len
|
||
|
||
```rust
|
||
set.len()
|
||
```
|
||
|
||
---
|
||
|
||
## clear
|
||
|
||
```rust
|
||
set.clear()
|
||
```
|
||
|
||
---
|
||
|
||
# 十一、HashSet 集合运算（非常强）
|
||
|
||
## union
|
||
|
||
并集
|
||
|
||
```rust
|
||
set1.union(&set2)
|
||
```
|
||
|
||
---
|
||
|
||
## intersection
|
||
|
||
交集
|
||
|
||
```rust
|
||
set1.intersection(&set2)
|
||
```
|
||
|
||
---
|
||
|
||
## difference
|
||
|
||
差集
|
||
|
||
```rust
|
||
set1.difference(&set2)
|
||
```
|
||
|
||
---
|
||
|
||
## symmetric_difference
|
||
|
||
对称差
|
||
|
||
```rust
|
||
set1.symmetric_difference(&set2)
|
||
```
|
||
|
||
---
|
||
|
||
例子：
|
||
|
||
```rust
|
||
for x in set1.intersection(&set2) {
|
||
println!("{}", x);
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
# 十二、HashSet 遍历
|
||
|
||
```rust
|
||
for v in &set {
|
||
println!("{}", v);
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
# 十三、HashSet 关系判断
|
||
|
||
## is_subset
|
||
|
||
```rust
|
||
set1.is_subset(&set2)
|
||
```
|
||
|
||
---
|
||
|
||
## is_superset
|
||
|
||
```rust
|
||
set1.is_superset(&set2)
|
||
```
|
||
|
||
---
|
||
|
||
## is_disjoint
|
||
|
||
```rust
|
||
set1.is_disjoint(&set2)
|
||
```
|
||
|
||
两个集合是否没有交集。
|
||
|
||
---
|
||
|
||
# 十四、一个典型例子
|
||
|
||
### 去重
|
||
|
||
```rust
|
||
let nums = vec![1,2,2,3,4];
|
||
|
||
let set: HashSet<_> = nums.into_iter().collect();
|
||
```
|
||
|
||
---
|
||
|
||
### 统计词频
|
||
|
||
```rust
|
||
let mut map = HashMap::new();
|
||
|
||
for word in text.split_whitespace() {
|
||
*map.entry(word).or_insert(0) += 1;
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
# 十五、Rust HashMap 一个隐藏知识
|
||
|
||
Rust标准库 HashMap **不是自己实现的**。
|
||
|
||
它使用：
|
||
|
||
**SwissTable**
|
||
|
||
来自：
|
||
|
||
Google
|
||
|
||
算法实现来自：
|
||
|
||
**Abseil**
|
||
|
||
特点：
|
||
|
||
* SIMD 查找
|
||
* robin hood hashing
|
||
* 非常快
|