键盘快捷键

按 ← 或 → 在章节间切换

按 S 或 / 搜索本书

按 ? 显示此帮助

按 Esc 隐藏此帮助

使用哈希映射存储键值对

我们要介绍的最后一种常见集合是哈希映射。HashMap<K, V> 类型使用哈希函数将 K 类型的键映射到 V 类型的值；哈希函数决定了这些键和值在内存中的存放位置。许多编程语言都支持这种数据结构，但常用不同名称，例如 hash、map、object、hash table、dictionary 或 associative array 等等。

当你想要查找数据时，哈希映射很有用。与向量通过索引查找不同，哈希映射使用键来查找，而键可以是任意类型。例如，在游戏中，你可以使用哈希映射记录每支队伍的得分，其中每个键是队伍名称，对应的值是队伍得分。给定队伍名称，就可以查到它的得分。

本节会介绍哈希映射的基本 API，不过标准库为 HashMap<K, V> 定义的函数中还隐藏着许多实用功能。和往常一样，更多信息请查阅标准库文档。

创建新的哈希映射

创建空哈希映射的一种方法是使用 new，然后通过 insert 添加元素。在示例 8-20 中，我们记录了两支队伍的得分，它们的名称分别是 Blue 和 Yellow。Blue 队初始得分为 10，Yellow 队初始得分为 50。

fn main() {
    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);
}
示例 8-20：创建新的哈希映射并插入一些键和值

请注意，我们首先需要从标准库的集合部分 use 引入 HashMap。在三种常见集合中，哈希映射的使用频率最低，因此它没有被包含在 prelude 自动引入作用域的功能中。标准库对哈希映射的支持也相对较少，例如没有用于构造哈希映射的内置宏。

和向量一样，哈希映射也将数据存储在堆上。这个 HashMap 的键类型是 String，值类型是 i32。与向量类似，哈希映射也是同质的：所有键必须具有相同类型，所有值也必须具有相同类型。

访问哈希映射中的值

我们可以将键传给 get 方法，从哈希映射中获取对应的值，如示例 8-21 所示。

fn main() {
    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);

    let team_name = String::from("Blue");
    let score = scores.get(&team_name).copied().unwrap_or(0);
}
示例 8-21：访问哈希映射中 Blue 队的得分

这里，score 会得到与 Blue 队关联的值，结果为 10。get 方法返回 Option<&V>；如果哈希映射中没有该键对应的值，get 就会返回 None。这段程序先调用 copied 得到 Option<i32>（而不是 Option<&i32>）来处理 Option，然后调用 unwrap_or：如果 scores 中没有该键对应的条目，就将 score 设为零。

与遍历向量类似，我们可以使用 for 循环遍历哈希映射中的每个键值对：

fn main() {
    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);

    for (key, value) in &scores {
        println!("{key}: {value}");
    }
}

这段代码会以任意顺序打印每个键值对：

Yellow: 50
Blue: 10

哈希映射中的所有权管理

对于实现了 Copy trait 的类型（例如 i32），值会被复制到哈希映射中。对于 String 这样的拥有所有权的值，值会被移动，哈希映射将成为这些值的所有者，如示例 8-22 所示。

fn main() {
    use std::collections::HashMap;

    let field_name = String::from("Favorite color");
    let field_value = String::from("Blue");

    let mut map = HashMap::new();
    map.insert(field_name, field_value);
    // field_name and field_value are invalid at this point, try using them and
    // see what compiler error you get!
}
示例 8-22：展示插入后键和值由哈希映射拥有

调用 insert 将 field_name 和 field_value 移入哈希映射后，我们就不能再使用这两个变量了。

如果向哈希映射中插入的是值的引用，值本身不会被移动到哈希映射中。引用指向的值必须至少与哈希映射本身一样长寿。关于这些问题，我们会在第 10 章“使用生命周期验证引用”一节中进一步讨论。

更新哈希映射

虽然键值对的数量可以增长，但每个唯一键在同一时刻只能关联一个值（反过来则不成立：例如，Blue 队和 Yellow 队都可以在 scores 哈希映射中对应值 10）。

想要更改哈希映射中的数据时，你必须决定如何处理键已经有对应值的情况。你可以用新值替换旧值，完全忽略旧值；也可以保留旧值并忽略新值，只有在键尚无对应值时才添加新值；或者将旧值与新值合并。下面分别看看这些做法！

覆盖值

如果我们先向哈希映射中插入一个键和值，然后再用同一个键插入不同的值，那么与该键关联的值就会被替换。尽管示例 8-23 调用了两次 insert，哈希映射中仍然只会有一个键值对，因为两次插入的都是 Blue 队对应的键。

fn main() {
    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Blue"), 25);

    println!("{scores:?}");
}
示例 8-23：替换与特定键关联的值

这段代码会打印 {"Blue": 25}。原来的值 10 已被覆盖。

仅在键不存在时添加键和值

一种常见做法是检查哈希映射中是否已存在某个键及其对应值，然后采取以下措施：如果键已经存在，就保留现有值；如果键不存在，就插入该键及其对应的值。

哈希映射为此提供了一个名为 entry 的特殊 API，它接收你想要检查的键作为参数。entry 方法的返回值是一个名为 Entry 的枚举，它表示某个值可能存在，也可能不存在。假设我们想要检查 Yellow 队的键是否有关联值；如果没有，就插入值 50，Blue 队也一样。使用 entry API 后，代码如示例 8-24 所示。

fn main() {
    use std::collections::HashMap;

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

    scores.entry(String::from("Yellow")).or_insert(50);
    scores.entry(String::from("Blue")).or_insert(50);

    println!("{scores:?}");
}
示例 8-24：使用 entry 方法，仅在键尚无对应值时插入

Entry 上的 or_insert 方法会返回与对应 Entry 键关联值的可变引用（如果该键存在）；如果不存在，它会将参数作为该键的新值插入，并返回指向新值的可变引用。这种写法比自行编写逻辑简洁得多，而且也更容易通过借用检查器。

运行示例 8-24 中的代码会打印 {"Yellow": 50, "Blue": 10}。第一次调用 entry 时，Yellow 队还没有对应值，因此会插入键和值 50。第二次调用 entry 不会更改哈希映射，因为 Blue 队已经有值 10。

根据旧值更新值

哈希映射的另一种常见用途是查找某个键的值，然后根据旧值更新它。例如，示例 8-25 展示了如何统计一段文本中每个单词出现的次数。我们使用单词作为键，并递增对应的值来记录该单词出现的次数。如果是第一次遇到某个单词，就先插入值 0。

fn main() {
    use std::collections::HashMap;

    let text = "hello world wonderful world";

    let mut map = HashMap::new();

    for word in text.split_whitespace() {
        let count = map.entry(word).or_insert(0);
        *count += 1;
    }

    println!("{map:?}");
}
示例 8-25：使用存储单词及计数的哈希映射统计单词出现次数

这段代码会打印 {"world": 2, "hello": 1, "wonderful": 1}。你也可能看到相同的键值对以不同顺序打印出来：回顾“访问哈希映射中的值”一节，哈希映射的遍历顺序是任意的。

split_whitespace 方法会返回一个迭代器，它将 text 中的值按空白字符分隔为若干子切片。or_insert 方法会返回指定键对应值的可变引用（&mut V）。这里我们将该可变引用存储在 count 变量中，因此要给这个值赋值，必须先使用星号（*）解引用 count。在 for 循环结束时，可变引用会离开作用域，因此这些修改都是安全的，并且符合借用规则。

哈希函数

默认情况下，HashMap 使用名为 SipHash 的哈希函数，它能够抵御针对哈希表的拒绝服务（DoS）攻击1。这不是速度最快的哈希算法，但性能有所下降所换来的更高安全性是值得的。如果你对代码进行性能分析后发现默认哈希函数对你的用途来说太慢，可以通过指定不同的哈希器来切换函数。哈希器是一种实现了 BuildHasher trait 的类型。我们会在第 10 章讨论 trait 及其实现方式。你不一定要从头实现自己的哈希器；crates.io 上有其他 Rust 用户分享的库，提供了实现多种常见哈希算法的哈希器。

总结

当程序需要存储、访问和修改数据时，向量、字符串和哈希映射能提供大量必要功能。现在你应该已经掌握了完成以下练习所需的知识：

  1. 给定一个整数列表，使用向量返回其中位数（排序后位于中间位置的值）和众数（出现次数最多的值；这里哈希映射会很有用）。
  2. 将字符串转换为 Pig Latin。每个单词的第一个辅音移到词尾，并添加 ay，因此 first 会变成 irst-fay。以元音开头的单词则在词尾添加 hay（apple 会变成 apple-hay）。请记住 UTF-8 编码的相关细节！
  3. 使用哈希映射和向量创建一个文本界面，让用户可以将员工姓名添加到公司的某个部门，例如“将 Sally 添加到 Engineering”或“将 Amir 添加到 Sales”。然后允许用户获取某个部门的所有人员列表，或按部门获取公司的所有人员列表，并按字母顺序排序。

标准库 API 文档介绍了向量、字符串和哈希映射提供的各种方法，这些方法会对完成上述练习有所帮助！

我们正在进入更复杂的程序领域，其中的操作可能会失败，因此现在正是讨论错误处理的好时机。下一章我们就来介绍它！

  1. https://en.wikipedia.org/wiki/SipHash ↩