Rust 从 0 到 1- 集合 -Hash Map

在 Rust 里，Hash Map 的类型是 HashMap<K, V> ，用于储存键值对（即 key-value 映射），并通过一个哈希函数（hashing function）来决定键和值在内存中如何存储。这种数据结构在很多编程语言都有，不过可能名字会有所不同，譬如，hash, map, object, hash table, dictionary 或者 associative array 等等。

Hash Map 的键可以是布尔型、整型、字符串，或任何实现了 Eq 和 Hash trait 的类型，适用于我们想通过一个有意义的键（key）来访问数据，而不像在 vector 中只能通过索引进行访问的场景。譬如，在一个游戏中，我们可以把每个团队的分数记录到 Hash Map 中，使用队伍的名字作为键来存储每个队伍的分数，从而给出一个队名，就能获得他们的得分。

下面我们会介绍 Hash Map 的基本 API，它包含的更多扩展功能请参考官方标准库对 HashMap<K, V> 的说明。

创建 Hash Map

和前面介绍的 Vec 类似，可以使用 new 关键字创建一个空的 HashMap，并使用 insert 方法添加元素。譬如，我们记录蓝队和黄队两支队伍的分数。蓝队开始有 10 分，黄队开始有 50 分：

use std::collections::HashMap;
let mut scores = HashMap::new();scores.insert(String::from("Blue"), 10);scores.insert(String::from("Yellow"), 50);

注意，我们必须首先使用 use 引入标准库中的 std::collections::HashMap，因为它并没有在 prelude 默认引入。标准库中对 HashMap 的支持相比 vector 要较弱，譬如，没有用于构建的宏，不过，大家可以去 crates.io 上发掘一下。

和 vector 类似，HashMap 也是将数据储存在堆上，并且同一个 HashMap 键和值的类型必须也是相同的。譬如，例子中的键是 String 类型而值是 i32 类型，那么所有元素的键和值都必须是这两个类型。

另外一种创建 HashMap 的方法是通过 vector 的迭代器（iterators）和 collect 方法将一个元素类型为元组的 vector 转换为 HashMap（其中每个元组元素包含一个键值对），后面的章节我们将详细介绍迭代器及其相关的方法。我们使用这种方式重新实现前面的例子：

use std::collections::HashMap;
let teams = vec![String::from("Blue"), String::from("Yellow")];let initial_scores = vec![10, 50];
let mut scores: HashMap<_, _> =    teams.into_iter().zip(initial_scores.into_iter()).collect();

上例中，开始两个队伍的名字和分数分别存在两个 vector 中，然后我们使用 zip 方法将名字和分数放入一个元组中并存入 vector，接着使用 collect 方法将这个包含元组类型元素的 vector 转换为 HashMap。另外，需要注意的是这里实现声明了 HashMap<_, _> 类型，这是因为 collect 方法返回的结果类型是不确定的，除非显式指定否则 Rust 无法事先知道类型，但是对于键和值的类型，可以使用下划线占位，因为 Rust 能够根据 vector 中数据的类型推断出它们的类型。

HashMap 和所有权

对于像 i32 这样的实现了 Copy trait 的类型，HashMap 会拷贝它的值；而对于像 String 这样具有所有权概念的类型，它将被移动到 HashMap，从而 HashMap 获得其所有权：

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 不再有效，// 如果再次使用它们将会发生编译错误！

如果将引用插入 HashMap，需要保证这些引用指向的值必须在 HashMap 有效时也是有效的，我们将在后面讨论 “生命周期与引用有效性” 时进行更为详细的讨论。

访问 HashMap 的值

可以使用键作为参数通过 get 方法来获取 HashMap 中的值：

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);

上例中，score 是蓝队的分数，get 方法返回的结果是 Some(10)，即 Option<V> 类型；如果一个键在 HashMap 中不存在，get 方法会返回 None（这个在前面介绍 Option 的时候讨论过）。

另外，我们还可以使用与 vector 类似的方式对 HashMap 进行遍历（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);}

修改 HashMap

前面介绍了，我们可以通过 insert 方法增加新的键值对，但是在 HashMap 中每个键只能对应一个值。那么如果当我们增加的键在 HashMap 中已存在时会怎样？如果我们想用新值代替旧的值怎么处理？如果我们想丢弃新值保留旧值怎么处理？如果我们想在旧值的基础上进行新值的处理怎么办？下面我们就来看看分别该如何处理。

覆盖旧值

如果我们使用相同的键插入（ insert ）一个不同的值，那么与这个键相对应的旧值将被替换：

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}，即 Blue 对应的值最终为 25 ，原始的值 10 则被新值所替代。

当键对应的值不存在时插入

这是我们经常会碰到的一种场景，即检查某个键是否有值，如果没有就插入一个值。HashMap 提供了 entry 方法用来处理这种场景。entry 方法的返回值是枚举类型 Entry：

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);

上例将会打印出 {"Yellow": 50, "Blue": 10}。第一个 entry 会插入黄队（Yellow）的值（50），因为黄队（Yellow）在 HashMap 中没有值。第二个 entry 不会改变 HashMap，因为蓝队（Blue）在 HashMap 已经有对应值（10）。

Entry 的 or_insert 方法在键对应的值存在时就返回旧值的可变引用，如果不存在则将参数作为新值插入 HashMap 并返回新值对应的可变引用。优美的逻辑实现，并且 Rust 还会帮助我们检查错误。

在旧值的基础上更新

另一个常见的应用场景是找到一个键对应的值并根据旧的值更新它，譬如，计数器：

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);

上例中我们使用 HashMap 以单词作为键来记录我们遇到过几次相同的单词，最终会打印出 {"world": 2, "hello": 1, "wonderful": 1}，or_insert 方法返回值对应的可变引用（&mut V），然后我们将其赋值给 count 变量，并在原计数值的基础上加 1。为了对值进行修改我们使用了 * 进行解引用，这个可变引用在 for 循环的结尾结束，因此所有这些修改都是符合所有权规则并且是安全的。

哈希函数

HashMap 默认使用一种 “强密码”（https://en.wikipedia.org/wiki/SipHash）的哈希函数，可以抵抗拒绝服务（Denial of Service, DoS）攻击。这并不是性能最好的的算法，但是为了更好的安全性值得付出一些性能上的代价。如果默认的哈希函数的性能在你的场景中无法被接受，可以通过指定一个自定义的哈希函数实现（需要实现 BuildHasher trait ）。另外，在 crates.io 有其他人分享的轮子，实现了许多常用哈希算法，我们可以直接拿来使用。

总结

集合是我们在编码中经常会用到的类型，官方的介绍还是比较基础的，如果需要解决我们实际场景中碰到的问题（官方文档中也举了一些例子），还需要我们查阅对应类型的官方 API 文档，并辅以练习。