Rust By Practice 实战:HashMap 原理、增删改查与容量管理的完整演练
Rust By Practice 实战:HashMap 原理、增删改查与容量管理的完整演练
导读
本篇基于 Rust By Practice 仓库中 en/src/collections/hashmap.md 的练习体系,系统讲解 Rust 标准库 HashMap 的底层实现(SwissTable + SIMD 查找)、默认 SipHash 1-3 抗 HashDoS 设计、五道难度标注为 🌟🌟 的实战练习,以及容量收缩、所有权转移和第三方哈希替换等进阶用法。学完本篇,你将能熟练完成 HashMap 的创建、插入、查询、迭代与容量调优,并理解其 key 约束与性能取舍。
HashMap 是什么:基于 SwissTable 的键值容器
HashMap 是 Rust 标准库提供的哈希表容器:向量(Vec)按下标存储值,而 HashMap 按 key 存储值。它的底层实现是一份 Google SwissTable 的 Rust 移植版,使用二次探测(quadratic probing)与 SIMD 查找技术(见 en/src/collections/hashmap.md)。
默认情况下,HashMap 使用一种经过挑选、能够抵抗 HashDoS 攻击的哈希算法,当前默认实现是 SipHash 1-3(该选择未来可能变动,见 en/src/collections/hashmap.md)。这一设计带来的性能权衡是:
- 中型 key(如中等长度的字符串):
SipHash 1-3性能非常有竞争力; - 小型 key(如整数)或大型 key(如长字符串):其它哈希算法通常更快,但往往不具备
SipHash那样的抗 HashDoS 能力。
关于 SwissTable 的更多背景:原 C++ 实现位于 Abseil 的
raw_hash_set.h,算法整体思路可参考 CppCon 上的演讲(原文档见 en/src/collections/hashmap.md)。不过本文档本身不粘贴外部链接,仓库内也只引用本地相对路径。
基本操作:五步掌握增删改查
本节练习全部来自 en/src/collections/hashmap.md,标准答案可在 solutions/collections/Hashmap.md 中对照。
练习 1:insert / get / contains_key / remove / len / 迭代
use std::collections::HashMap;
fn main() {
let mut scores = HashMap::new();
scores.insert("Sunface", 98);
scores.insert("Daniel", 95);
scores.insert("Ashley", 69); // 注意:原文中 69.0 是浮点,会导致类型不一致,需修复
scores.insert("Katie", 58); // 原文中 "58" 是字符串,同样需要修复
// get 返回一个 Option<&V>
let score = scores.get("Sunface");
assert_eq!(score, Some(&98));
if scores.contains_key("Daniel") {
// 索引返回一个值 V(Panics on missing key)
let score = scores["Daniel"];
assert_eq!(score, 95);
scores.remove("Daniel");
}
assert_eq!(scores.len(), 3);
for (name, score) in scores {
println!("The score of {} is {}", name, score);
}
}
要点拆解(对照 solutions/collections/Hashmap.md):
| API | 返回值 | 语义 |
|---|---|---|
insert(k, v) |
Option<V> |
插入键值对,若 key 已存在则返回旧值 |
get(&k) |
Option<&V> |
返回值的引用,Option 包装 |
contains_key(&k) |
bool |
判断 key 是否存在 |
scores["Daniel"] |
V(不可变索引) |
直接索引,key 不存在时会 panic |
remove(&k) |
Option<V> |
移除并返回旧值 |
len() |
usize |
当前键值对数量 |
for (name, score) in scores |
迭代 | 消费型迭代,取出所有权 |
关于 get 的返回类型:练习 1 里需要修复的错误之一就是 assert_eq!(score, Some(98)) —— 由于 get 返回 Option<&V>,正确答案应为 Some(&98)。
练习 2:用 collect 或 HashMap::from 从数组构建
use std::collections::HashMap;
fn main() {
let teams = [
("Chinese Team", 100),
("American Team", 10),
("France Team", 50),
];
let mut teams_map1 = HashMap::new();
for team in &teams {
teams_map1.insert(team.0, team.1);
}
// 方式一:借助 Iterator 的 collect 方法
let teams_map2: HashMap<_, _> = teams.into_iter().collect();
assert_eq!(teams_map1, teams_map2);
println!("Success!");
}
第二种方式(见 solutions/collections/Hashmap.md)是利用 HashMap 实现了 From<[(K, V); N]>:
let teams_map2 = HashMap::from(teams);
HashMap 的相等比较(==)是键值级别的,与构建顺序无关,因此 teams_map1 与 teams_map2 必然相等。
练习 3:entry API 与 or_insert / or_insert_with
entry 是 HashMap 最常用的“查询-修改-插入”一体化 API:
use std::collections::HashMap;
fn main() {
// 编译器可根据后续使用推断出 HashMap<&str, u8>,也可显式标注
let mut player_stats = HashMap::new();
// 若 key 不存在才插入
player_stats.entry("health").or_insert(100);
assert_eq!(player_stats["health"], 100);
// 通过闭包/函数提供新值,仅在 key 不存在时调用
player_stats.entry("health").or_insert_with(random_stat_buff);
assert_eq!(player_stats["health"], 100); // 已存在,函数不会被调用
// or_insert 返回 &mut V,可继续修改值
let health = player_stats.entry("health").or_insert(50);
assert_eq!(health, &100);
*health -= 50;
assert_eq!(*health, 50);
println!("Success!");
}
fn random_stat_buff() -> u8 {
// 真实场景可返回随机值,这里为演示固定返回 42
42
}
关键语义(对照 solutions/collections/Hashmap.md):
entry("health")返回Entry枚举,区分Occupied(key 已存在)与Vacant(key 不存在);or_insert(value):若存在直接返回已有值的&mut V,若不存在则插入该值;or_insert_with(fn):惰性求值,仅在 key 不存在时才调用传入的函数,适合构造开销较大的默认值;- 返回值都是
&mut V,可以直接通过*health -= 50修改 map 内的值。
HashMap key 的约束:Eq + Hash
任何同时实现了 Eq 与 Hash 特征的类型都可以作为 HashMap 的 key(见 en/src/collections/hashmap.md):
bool(可用,但只有两种取值,实际意义有限);- 所有整数类型
int/uint及其变体(如u8、i32、usize); String与&str:注意技巧——当HashMap的 key 是String时,可以用&str调用.get()查询,因为标准库为此提供了Borrow<str>支持;f32与f64没有实现Hash,因为浮点精度误差会导致相等的判定不可靠,用作 key 极易出错;- 集合类型(如
Vec<T>)只有在内部元素类型T实现了Eq/Hash时,才会自动实现这两个特征。
练习 4:为自定义结构体派生 Hash + Eq
把自定义类型当作 key 时,最省力的做法是用 #[derive]:
use std::collections::HashMap;
// 关键修复:为结构体派生所需的特征
#[derive(Hash, Eq, PartialEq, Debug)]
struct Viking {
name: String,
country: String,
}
impl Viking {
fn new(name: &str, country: &str) -> Viking {
Viking {
name: name.to_string(),
country: country.to_string(),
}
}
}
fn main() {
let vikings = HashMap::from([
(Viking::new("Einar", "Norway"), 25),
(Viking::new("Olaf", "Denmark"), 24),
(Viking::new("Harald", "Iceland"), 12),
]);
for (viking, health) in &vikings {
println!("{:?} has {} hp", viking, health);
}
}
对照 solutions/collections/Hashmap.md,这里的修复点在结构体上添加 #[derive(Hash, Eq, PartialEq, Debug)]。注意:Viking 的两个字段 name 和 country 都是 String(实现了 Hash + Eq),因此派生的 Hash、Eq 会逐字段组合实现;Debug 则用于 {:?} 格式化打印。
容量管理:with_capacity / shrink_to / shrink_to_fit
与 Vec 类似,HashMap 可以增长,也可以在有剩余空间时收缩自身(见 en/src/collections/hashmap.md):
use std::collections::HashMap;
fn main() {
let mut map: HashMap<i32, i32> = HashMap::with_capacity(100);
map.insert(1, 2);
map.insert(3, 4);
// 注意:容量并不精确等于 100,因此这里不能用 == 比较
assert!(map.capacity() >= 100);
// 收缩到不低于指定下限,同时遵循内部重哈希策略,可能保留一定余量
map.shrink_to(50);
assert!(map.capacity() >= 50);
// 尽可能收缩容量
map.shrink_to_fit();
assert!(map.capacity() >= 2);
println!("Success!");
}
API 语义一览:
| 方法 | 行为 |
|---|---|
HashMap::with_capacity(n) |
以指定初始容量创建(实际容量可能大于 n) |
HashMap::new() |
使用默认初始容量(官方推荐日常使用) |
capacity() |
返回当前容量 |
shrink_to(n) |
收缩至不低于 n,由内部策略决定精确值 |
shrink_to_fit() |
按当前元素数尽可能收缩 |
容量相关讨论可对比向量章节 en/src/collections/vector.md 中关于扩容的介绍:与向量只能扩容不同,哈希表在删除大量元素后还能主动收缩,避免内存浪费。
所有权语义:Copy 拷贝 vs 所有权转移
HashMap 的所有权规则非常清晰(见 en/src/collections/hashmap.md):
- 对实现了
Copy特征的类型(如i32),值被拷贝进 HashMap,原变量仍可使用; - 对拥有所有权的类型(如
String),值被移动进 HashMap,由 HashMap 成为新的所有者,原变量失效。
练习 5:最少改动修复所有权错误
use std::collections::HashMap;
fn main() {
let v1 = 10;
let mut m1 = HashMap::new();
m1.insert(v1, v1); // i32 是 Copy 类型,v1 依然可用
println!("v1 is still usable after inserting to hashmap : {}", v1);
// 修复方案:把 String 换成 &str(&str 实现了 Copy)
let v2 = "hello";
let mut m2 = HashMap::new();
m2.insert(v2, v1);
assert_eq!(v2, "hello");
println!("Success!");
}
对照 solutions/collections/Hashmap.md:原题要求“用最少的修改修复错误,且不要删除任何代码行”,因此正确的修复是把 "hello".to_string() 改为 "hello",让 v2 成为 &str——&str 实现了 Copy,插入后 v2 仍可继续使用。
仓库实战印证:mini-redis 中的 HashMap 应用
Rust By Practice 仓库在 zh-CN/assets/mini-redis/ 附带了一个完整可运行的 mini-redis 服务端实现,其中 HashMap 正是核心数据结构(以下行号来自该仓库源码):
- zh-CN/assets/mini-redis/src/db.rs#L61-L68 定义了共享状态
State,其中entries: HashMap<String, Entry>存储全部键值数据,pub_sub: HashMap<String, broadcast::Sender<Bytes>>独立管理 pub/sub 通道——注释明确说明“Redis 为 key-value 与 pub/sub 使用相互独立的 key 空间”; - 读取路径:
GET命令最终落到 zh-CN/assets/mini-redis/src/db.rs#L153-L160 的get(),即state.entries.get(key).map(|entry| entry.data.clone()),与练习 1 中get返回Option<&V>的语义完全一致;命令解析与响应构造见 zh-CN/assets/mini-redis/src/cmd/get.rs; entryAPI 实战:在 zh-CN/assets/mini-redis/src/db.rs#L243-L247 中,订阅频道使用match state.pub_sub.entry(key) { Entry::Occupied(e) => ..., Entry::Vacant(e) => ... }来区分“频道已存在则复用,不存在则创建”,正是练习 3 所讲Entry枚举的工程化应用;- 删除路径:过期 key 清理时调用
state.entries.remove(key)(见 zh-CN/assets/mini-redis/src/db.rs#L326)。
可见:文档中讲解的 new、insert、get、remove、entry、len 等 API,正是 mini-redis 这类真实服务端程序的日常工作方式。
性能进阶:替换默认哈希为第三方库
如果你发现默认的 SipHash 1-3 性能不达标(例如大量整数或超长字符串 key),可以在 crates.io 或 GitHub 上寻找替代哈希实现,通过 HashMap 的第三个泛型参数 BuildHasher 接入(见 en/src/collections/hashmap.md):
use std::hash::BuildHasherDefault;
use std::collections::HashMap;
// 引入第三方哈希函数,例如 twox-hash 的 XxHash64
use twox_hash::XxHash64;
let mut hash: HashMap<_, _, BuildHasherDefault<XxHash64>> = Default::default();
hash.insert(42, "the answer");
assert_eq!(hash.get(&42), Some(&"the answer"));
要点:
HashMap<K, V, S = RandomState>的第三个泛型参数是哈希构建器(build hasher);BuildHasherDefault<XxHash64>让每个实例使用XxHash64的默认构造;- 替换哈希算法会失去 SipHash 的抗 HashDoS 保护,仅适合对性能敏感且不面对恶意输入的场景(如内部缓存、离线批处理);
- 使用前需在
Cargo.toml中加入对应依赖(如twox-hash),本仓库文档未内置该依赖,仅在示例中展示用法。
总结
围绕 Rust By Practice 的 HashMap 章节,本文完整覆盖了:
- 原理层:SwissTable(二次探测 + SIMD 查找)与默认
SipHash 1-3抗 HashDoS 的设计取舍; - 操作层:
insert/get/contains_key/ 索引 /remove/len/ 迭代,以及entry的or_insert/or_insert_with惰性语义; - 约束层:key 必须实现
Eq + Hash,浮点数不可作 key,自定义类型用#[derive(Hash, Eq, PartialEq)]; - 容量层:
with_capacity、shrink_to、shrink_to_fit的增长与收缩策略; - 所有权层:
Copy值拷贝、拥有型值移动进 HashMap; - 实战层:mini-redis 服务端如何用
HashMap实现键值存储与 pub/sub 分离,以及如何用第三方哈希替换默认算法。
所有练习的权威答案均可对照 solutions/collections/Hashmap.md 验证,建议结合 en/src/collections/hashmap.md 原文边练边查。