将具有关联值的键存储在哈希 Map 中


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


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


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


创建新的哈希 Map


创建空哈希 map 的一种方法是使用 new 并使用 插入。在示例 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：创建一个新的哈希 map 并插入一些键和值


请注意，我们需要首先使用标准库的 collections 部分的 HashMap。在我们的三个常见集合中，这个集合使用得最少，因此它不会包含在 prelude 中自动引入范围的功能中。标准库对哈希 map 的支持也较少;例如，没有内置的宏来构造它们。


就像向量一样，哈希 map 将其数据存储在堆上。此 HashMap 具有 String 类型的键和 i32 类型的值。与向量一样，哈希映射是同构的：所有键必须具有相同的类型，并且所有值都必须具有相同的类型。


访问哈希 Map 中的值


我们可以通过将哈希 map 的 key 提供给 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：访问存储在哈希 map 中的蓝队分数


此处，score 将具有与蓝队关联的值，结果将为 10。get 方法返回一个 Option<&V>;如果哈希 map 中没有该键的值，则 get 将返回 None。此程序通过调用 copied 来处理 Option 以获取 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}");
    }
}


此代码将按任意顺序打印每对：


黄色：50
蓝色：10


哈希映射和所有权


对于实现 Copy trait 的类型，如 i32，值将被复制到哈希 map 中。对于像 String 这样的拥有值，值将被移动，哈希 map 将是这些值的所有者，如示例 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：显示键和值在插入后归哈希 map 所有


在通过调用 insert 将变量 field_name 和 field_value 移动到哈希 map 后，我们无法使用它们。


如果我们将对值的引用插入到哈希 map 中，则这些值不会移动到哈希 map 中。只要哈希 map 有效，引用指向的值就必须至少有效。我们将在“验证引用 Lifetimes“部分。


更新 Hash Map


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


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


覆盖值


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

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：替换使用特定 key 存储的值


此代码将打印 {“Blue”： 25}。原始值 10 已被覆盖。


仅在 key 不存在时添加 key 和 value


通常检查哈希 map 中是否已存在具有值的特定键，然后执行以下作：如果哈希 map 中确实存在该键，则现有值应保持原样;如果该键不存在，请插入该键及其值。


哈希映射有一个特殊的 API 用于此，称为 entry，它将您要检查的键作为参数。entry 方法的返回值是一个名为 Entry 的枚举，它表示一个可能存在也可能不存在的值。假设我们想要检查 Yellow 团队的键是否具有与之关联的值。如果没有，我们想插入值 50，Blue team 也是如此。使用入口 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 方法仅在 key 还没有值时插入


Entry 上的 or_insert 方法定义为返回对相应 Entry 键的值的可变引用（如果该键存在），如果不存在，则它将参数插入作为该键的新值，并返回对新值的可变引用。这种技术比我们自己编写 logic 要干净得多，此外，它与 borrow checker 配合得更好。


运行示例 8-24 中的代码将打印 {“Yellow”： 50， “Blue”： 10}。对 entry 的第一次调用将插入 Yellow team 的键，其值为 50 的分数，因为 Yellow 团队还没有值。第二次调用 条目不会更改哈希映射，因为蓝队已经有值 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：使用存储单词和计数的哈希 map 计算单词的出现次数


此代码将打印 {"world": 2, "hello": 1, "wonderful": 1} 。您可能会看到 以不同顺序打印相同的键值对：从 “Accessing Values in a Hash Map” 部分，迭代 Hash Map 的顺序是任意的。


split_whitespace 方法返回 text 中值的子切片的迭代器，用空格分隔。or_insert 方法返回对指定键值的可变引用 （&mut V）。在这里，我们将该可变引用存储在 count 变量中，因此为了分配给该值，我们必须首先使用星号 （*） 取消引用 count。可变引用在 for 循环结束时超出范围，因此所有这些更改都是安全的，并且是借用规则允许的。


哈希函数


默认情况下，HashMap 使用名为 SipHash 的哈希函数，该函数可以抵御涉及哈希表1 的拒绝服务 （DoS） 攻击。这不是可用的最快的哈希算法，但随着性能下降而为获得更好的安全性而进行的权衡是值得的。如果您分析代码并发现默认哈希函数对于您的目的来说太慢，则可以通过指定不同的哈希程序切换到另一个函数。哈希器是一种实现 BuildHasher trait 的 BuildHasher 特征。我们将讨论特征以及如何在 第 10 章.您不一定要从头开始实现自己的哈希器;crates.io 具有其他 Rust 用户共享的库，这些库提供实现许多 常见的哈希算法。


总结


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


  1. 给定一个整数列表，使用一个向量并返回列表的中位数（排序时，中间位置的值）和众数（最常出现的值;哈希映射在这里会有所帮助）。

  2. 将字符串转换为 pig 拉丁语。每个单词的第一个辅音被移动到单词的末尾，并加上 ay，所以第一个辅音变成了 irst-fay。以元音开头的单词会在末尾加上 hay （apple 变为 apple-hay 的请记住有关 UTF-8 编码的详细信息！

  3. 使用哈希映射和向量，创建一个文本界面，以允许用户将员工姓名添加到公司的部门;例如，“Add Sally to Engineering” 或 “Add Amir to Sales”然后，让用户检索一个部门中的所有人员或公司中按部门的所有人员的列表，并按字母顺序排序。


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


我们正在研究作可能会失败的更复杂的程序，因此现在是讨论错误处理的最佳时机。我们接下来会这样做！