使用 Rust 哈希映射存储键值对

简介

欢迎来到「在哈希映射中存储键值对」实验。本实验是 Rust 程序设计语言 的一部分。你可以在 LabEx 中练习 Rust 技能。

在本实验中，我们将探索哈希映射的概念，以及如何使用它们来存储键值对。

Skills Graph

在哈希映射中存储键值对

我们常用的集合类型中的最后一种是哈希映射。HashMap<K, V> 类型使用哈希函数存储从 K 类型的键到 V 类型的值的映射关系，该函数决定了如何将这些键值对存储到内存中。许多编程语言都支持这种数据结构，但它们通常使用不同的名称，比如哈希、映射、对象、哈希表、字典或关联数组等等。

当你想要查找数据时，如果不是像使用向量那样通过索引，而是使用可以是任何类型的键，那么哈希映射就很有用。例如，在一个游戏中，你可以在哈希映射中记录每个队伍的分数，其中每个键是队伍的名称，值是每个队伍的分数。给定一个队伍名称，你就可以获取它的分数。

在本节中，我们将介绍哈希映射的基本 API，但标准库在 HashMap<K, V> 上定义的函数中还隐藏着更多有用的功能。一如既往，查阅标准库文档以获取更多信息。

创建新的哈希映射

创建空哈希映射的一种方法是使用 new，并使用 insert 添加元素。在清单 8-20 中，我们记录了两支队伍的分数，队伍名称分别是「蓝色」和「黄色」。蓝色队伍初始分数为 10 分，黄色队伍初始分数为 50 分。

use std::collections::HashMap;

let mut scores = HashMap::new();

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

清单 8-20：创建新的哈希映射并插入一些键值对

注意，我们首先需要使用标准库集合部分中的 HashMap。在我们常用的三种集合中，哈希映射是最不常用的，所以它没有包含在 prelude 中自动引入作用域的特性里。标准库对哈希映射的支持也较少；例如，没有用于构造它们的内置宏。

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

获取哈希映射中的值

我们可以通过向 get 方法提供键来从哈希映射中获取值，如清单 8-21 所示。

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：获取存储在哈希映射中的蓝色队伍的分数

在这里，score 将具有与蓝色队伍相关联的值，结果将是 10。get 方法返回一个 Option<&V>；如果哈希映射中没有该键的值，get 将返回 None。此程序通过调用 copied 来处理 Option，以获取一个 Option<i32> 而不是 Option<&i32>，然后调用 unwrap_or 在 scores 中没有该键的条目时将 score 设置为零。

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

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 特性的类型，比如 i32，值会被复制到哈希映射中。对于像 String 这样的拥有所有权的值，值会被移动，并且哈希映射将成为这些值的所有者，如清单 8-22 所示。

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 和 field_value 在此处无效，尝试
// 使用它们，看看会得到什么编译器错误！

清单 8-22：展示键和值在插入哈希映射后由其拥有

在通过调用 insert 将变量 field_name 和 field_value 移动到哈希映射中之后，我们就无法再使用它们了。

如果我们将值的引用插入到哈希映射中，值不会被移动到哈希映射中。引用所指向的值必须至少在哈希映射有效期间内保持有效。我们将在“使用生命周期验证引用”中更多地讨论这些问题。

更新哈希映射

虽然键值对的数量是可以增长的，但每个唯一的键在同一时间只能与一个值相关联（反之则不然：例如，蓝色队伍和黄色队伍都可以在 scores 哈希映射中存储值 10）。

当你想要更改哈希映射中的数据时，你必须决定如何处理键已经有值的情况。你可以用新值替换旧值，完全忽略旧值。你可以保留旧值并忽略新值，只有在键还没有值时才添加新值。或者你可以将旧值和新值合并。让我们看看如何实现这些操作！

覆盖值

如果我们向哈希映射中插入一个键值对，然后再用不同的值插入同一个键，那么与该键关联的值将会被替换。尽管清单 8-23 中的代码调用了两次 insert，但哈希映射只会包含一个键值对，因为我们两次插入的都是蓝色队伍键的值。

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 已被覆盖。

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

通常需要检查哈希映射中是否已经存在某个特定的键及其对应的值，然后采取以下操作：如果该键在哈希映射中确实存在，则现有值应保持不变；如果该键不存在，则插入它及其对应的值。

哈希映射为此提供了一个特殊的 API，称为 entry，它将你要检查的键作为参数。entry 方法的返回值是一个名为 Entry 的枚举，它表示一个可能存在也可能不存在的值。假设我们要检查黄色队伍的键是否有与之关联的值。如果没有，我们想插入值 50，蓝色队伍也是如此。使用 entry API，代码如下清单 8-24 所示。

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 将插入黄色队伍的键及其值 50，因为黄色队伍之前没有值。第二次调用 entry 不会改变哈希映射，因为蓝色队伍已经有值 10 了。

根据旧值更新值

哈希映射的另一个常见用例是查找键的值，然后根据旧值对其进行更新。例如，清单 8-25 展示了一段代码，用于统计某些文本中每个单词出现的次数。我们使用一个以单词为键的哈希映射，并增加其值来跟踪我们看到该单词的次数。如果这是我们第一次看到某个单词，我们将首先插入值 0。

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）攻击。这并非可用的最快哈希算法，但为了获得更好的安全性而在性能上有所牺牲是值得的。如果你对代码进行性能分析，发现默认哈希函数对你的目的来说太慢，那么你可以通过指定不同的哈希器来切换到另一个函数。哈希器是一种实现了 BuildHasher 特性的类型。我们将在第 10 章讨论特性以及如何实现它们。你不一定非要从头开始实现自己的哈希器；https://crates.io 有其他 Rust 用户共享的库，这些库提供了实现许多常见哈希算法的哈希器。

总结

恭喜你！你已经完成了“在哈希映射中存储键及其关联值”实验。你可以在 LabEx 中练习更多实验来提升你的技能。