Rust 程序设计语言

在散列表中存储带有关联值的键

我们常用的集合类型中最后一种是 散列表。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);
}

注意，我们需要首先从标准库的集合部分 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);
}

在这里，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!
}

在通过调用 insert 将变量 field_name 和 field_value 移动到散列表中之后，我们就不能再使用它们了。

如果我们插入值的引用到散列表中，值将不会被移动到散列表中。引用指向的值必须至少与散列表本身一样有效。我们将在第 10 章的“使用生命周期验证引用”中讨论更多这些问题。在第 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:?}");
}

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

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

一种常见的做法是检查散列表中是否已经存在某个键及其对应的值，然后执行以下操作：如果键确实存在于散列表中，则保留现有值不变；如果键不存在，则插入该键及其值。

散列表为此提供了一个特殊的 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:?}");
}

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

运行列表 8-24 中的代码将打印 {"Yellow": 50, "Blue": 10}。第一次调用 entry 将插入 Yellow 团队的键及其值 50，因为 Yellow 团队尚无值。第二次调用 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:?}");
}

这段代码将打印 {"world": 2, "hello": 1, "wonderful": 1}。你可能会看到相同的键值对以不同的顺序打印：回想一下“访问散列表中的值”中提到的，遍历散列表是按任意顺序进行的。

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

散列函数

默认情况下，HashMap 使用名为 SipHash 的散列函数，它可以提供对涉及散列表的拒绝服务 (DoS) 攻击的抵抗能力¹。这不是最快的散列算法，但为了获得更好的安全性而牺牲一些性能是值得的。如果你对代码进行性能分析，发现默认散列函数对你的目的来说太慢，你可以通过指定不同的散列器来切换到另一个函数。散列器 是一种实现了 BuildHasher trait 的类型。我们将在第 10 章中讨论 trait 以及如何实现它们。你不必从头开始实现自己的散列器；crates.io上有其他 Rust 用户共享的库，它们提供了实现许多常见散列算法的散列器。

总结

向量、字符串和散列表将提供程序中存储、访问和修改数据所需的大量功能。以下是你现在应该能够解决的一些练习：

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

标准库 API 文档描述了向量、字符串和散列表拥有的方法，这些方法对这些练习会有帮助！

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