Rust By Practice 实战:HashMap 原理、增删改查与容量管理的完整演练

原创2026-09-21 21:05:301,947 阅读
文章标签:文档教程教育

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;
  • entry API 实战:在 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 章节,本文完整覆盖了:

  1. 原理层:SwissTable(二次探测 + SIMD 查找)与默认 SipHash 1-3 抗 HashDoS 的设计取舍;
  2. 操作层:insert / get / contains_key / 索引 / remove / len / 迭代,以及 entry 的 or_insert / or_insert_with 惰性语义;
  3. 约束层:key 必须实现 Eq + Hash,浮点数不可作 key,自定义类型用 #[derive(Hash, Eq, PartialEq)];
  4. 容量层:with_capacity、shrink_to、shrink_to_fit 的增长与收缩策略;
  5. 所有权层:Copy 值拷贝、拥有型值移动进 HashMap;
  6. 实战层:mini-redis 服务端如何用 HashMap 实现键值存储与 pub/sub 分离,以及如何用第三方哈希替换默认算法。

所有练习的权威答案均可对照 solutions/collections/Hashmap.md 验证,建议结合 en/src/collections/hashmap.md 原文边练边查。

登录后查看全文
rust-by-practice