Rust 程序设计语言

在哈希映射中存储具有关联值的键

我们常见的集合中的最后一个是哈希映射。类型 HashMap<K, V> 使用散列函数存储类型为 K 的键到类型为 V 的值的映射，该散列函数确定它如何将这些键和值放入内存中。许多编程语言都支持这种数据结构，但它们通常使用不同的名称，例如散列、映射、对象、哈希表、字典或关联数组，仅举几例。

当您想要查找数据而不是像使用向量那样使用索引，而是使用可以是任何类型的键时，哈希映射非常有用。例如，在游戏中，您可以在哈希映射中跟踪每个团队的分数，其中每个键都是团队的名称，而值是每个团队的分数。给定一个团队名称，您可以检索其分数。

我们将在本节中介绍哈希映射的基本 API，但是标准库在 HashMap<K, V> 上定义的函数中隐藏了更多的好东西。与往常一样，请查阅标准库文档以获取更多信息。

创建新的哈希映射

创建空哈希映射的一种方法是使用 new 并使用 insert 添加元素。在清单 8-20 中，我们正在跟踪两个名为 *Blue* 和 *Yellow* 的团队的分数。蓝色队以 10 分开始，黄色队以 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：访问哈希映射中存储的蓝色队的分数

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

我们可以使用 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 特性的类型（如 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 章中的部分详细讨论这些问题。

更新哈希映射

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

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

覆盖值

如果我们向哈希映射中插入一个键和一个值，然后使用不同的值插入相同的键，则与该键关联的值将被替换。即使清单 8-23 中的代码调用了两次 insert，哈希映射也只会包含一个键值对，因为我们两次都为蓝色队的键插入了值。

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 的枚举，它表示可能存在也可能不存在的值。假设我们要检查黄色队的键是否具有与之关联的值。如果它没有，我们希望插入值 50，蓝色队也一样。使用 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 将插入黄色队的键以及值 50，因为黄色队尚未具有值。第二次调用 entry 不会更改哈希映射，因为蓝色队已经具有值 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) 攻击的抵抗能力¹。这不是最快的散列算法，但是为了获得更好的安全性而牺牲性能是值得的。如果您分析代码并发现默认的散列函数对于您的目的来说太慢，则可以通过指定不同的哈希器切换到另一个函数。哈希器是一种实现 BuildHasher 特性的类型。我们将在第 10 章中讨论特性以及如何实现它们。您不一定必须从头开始实现自己的哈希器；crates.io具有其他 Rust 用户共享的库，这些库提供了实现许多常见散列算法的哈希器。

总结

当您需要存储、访问和修改数据时，向量、字符串和哈希映射将提供程序中所需的大量功能。以下是您现在应该能够解决的一些练习

1. 给定一个整数列表，使用向量并返回列表的中位数（排序后，中间位置的值）和众数（出现次数最多的值；哈希映射将在此处有所帮助）。
2. 将字符串转换为猪拉丁语。每个单词的第一个辅音移到单词末尾，并添加ay，所以first变成irst-fay。以元音开头的单词则在末尾添加hay（apple变成apple-hay）。请注意关于UTF-8编码的细节！
3. 使用哈希映射和向量，创建一个文本界面，允许用户将员工姓名添加到公司的部门中；例如，“将 Sally 添加到工程部”或“将 Amir 添加到销售部”。然后让用户检索某个部门的所有人员列表或按部门排序的公司所有人列表（按字母顺序排序）。

标准库 API 文档描述了向量、字符串和哈希映射具有的方法，这些方法对于这些练习将很有帮助！

我们正在进入更复杂的程序，其中操作可能会失败，所以现在是讨论错误处理的绝佳时机。接下来我们将讨论错误处理！