在哈希映射中存储带有相关值的键

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

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

我们将在这部分介绍哈希映射的基本 API，但标准库中定义的 HashMap<K, V> 还隐藏着许多其他功能。如往常一样，更多详细信息请查阅标准库文档。

创建新的哈希映射

创建一个空的哈希映射的一种方法是使用new并使用insert添加元素。在清单8-20中，我们正在跟踪两个团队的得分，这两个团队的名字分别是蓝色和黄色。蓝色团队从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);
}

Listing 8-20: Creating a new hash map and inserting some keys and values

请注意，我们需要首先 use 来自标准库集合部分的 HashMap。在我们常用的三种集合中，这个集合使用频率最低，因此没有包含在预定义模块中自动引入的功能范围内。哈希映射在标准库中的支持也较少；例如，没有内置的宏来构造它们。

就像向量一样，哈希映射将其数据存储在堆上。这个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);
}

Listing 8-21: Accessing the score for the Blue team stored in the hash map

这里，score 将拥有与 Blue 队相关联的值，结果将是 10。get 方法返回一个 Option<&V>；如果哈希映射中没有该键的值，get 将返回 None。此程序通过调用 copied 将 Option<&i32> 转换为 Option<i32>，然后使用 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}");
    }
}

这段代码将以任意顺序打印每对：println!("{:?}", pair);

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!
}

Listing 8-22: Showing that keys and values are owned by the hash map once they’re inserted

我们无法在将 field_name 和 field_value 移动到哈希映射中后使用它们，调用 insert 之后。

如果我们插入值的引用到哈希映射中，这些值不会被移动到哈希映射中。引用指向的值必须至少与哈希映射的生命周期一样长。我们将在第10章的“使用生命周期验证引用”部分详细讨论这些问题。

更新哈希映射

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

当你想要更改哈希映射中的数据时，你必须决定如何处理键已经分配了值的情况。你可以用新值替换旧值，完全忽略旧值。你可以保留旧值并忽略新值，只有在键没有已经有一个值时才添加新值。或者你可以将旧值和新值结合起来。让我们看看如何做到每一种！

Overwriting a Value

如果我们向哈希映射中插入一个键和一个值，然后用不同的值再次插入同一个键，与该键关联的值将被替换。即使列表 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:?}");
}

Listing 8-23: Replacing a value stored with a particular key

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

Adding a Key and Value Only If a Key Isn’t Present

通常会检查哈希映射中是否已存在某个键及其值，然后采取以下操作：如果键存在于哈希映射中，则保持现有值不变；如果键不存在，则插入该键及其值。

哈希映射为此提供了一个特殊的 API，称为 entry，它接受你想要检查的键作为参数。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:?}");
}

Listing 8-24: Using the entry method to only insert if the key does not already have a value

or_insert 方法在 Entry 上定义为，如果该键存在，则返回对应 Entry 键的值的可变引用；如果不存在，则将参数作为此键的新值插入，并返回新值的可变引用。这种技术比我们自己编写逻辑要干净得多，并且与借用检查器更友好。

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

Updating a Value Based on the Old Value

另一个常见的哈希映射用例是查找键的值，然后根据旧值进行更新。例如，列表 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:?}");
}

Listing 8-25: Counting occurrences of words using a hash map that stores words and counts

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

split_whitespace 方法返回一个迭代器，该迭代器遍历 text 中由空白分隔的子切片。or_insert 方法返回一个指向指定键值的可变引用 (&mut V)。在这里，我们将这个可变引用存储在 count 变量中，因此为了给该值赋值，我们必须首先使用星号 (*) 对 count 进行解引用。可变引用在 for 循环结束时超出作用域，因此所有这些更改都是安全的，并且符合借用规则。

哈希函数

默认情况下，HashMap 使用一种称为 SipHash 的哈希函数，可以提供针对涉及哈希表的拒绝服务 (DoS) 攻击的防护¹。这不是最快的哈希算法，但性能下降带来的更好安全性是值得的。如果你对代码进行了剖析并发现默认的哈希函数对于你的用途来说太慢，你可以通过指定不同的哈希器来切换到其他函数。一个 哈希器 是实现了 BuildHasher 特性的类型。我们将在第 10 章中讨论特性以及如何实现它们。你不必一定从头开始实现自己的哈希器；crates.io 有其他 Rust 用户共享的库，提供了实现许多常见哈希算法的哈希器。

https://zh.wikipedia.org/wiki/SipHash

摘要

向量、字符串和哈希映射将在你需要存储、访问和修改数据的程序中提供大量必要的功能。这里有一些你现在应该能够解决的练习：

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

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

我们正在进入更复杂的程序，在这些程序中操作可能会失败，因此现在是讨论错误处理的绝佳时机。我们接下来就来做这件事！

The Rust Programming Language