写点什么

Rust 从 0 到 1- 集合 -Hash Map

用户头像
关注
发布于: 2021 年 05 月 18 日
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 文档,并辅以练习。

发布于: 2021 年 05 月 18 日阅读数: 11
用户头像

关注

公众号"山 顽石"欢迎大家关注;) 2021.03.23 加入

IT老兵,关注Rust、Java、前端、架构、大数据、AI、算法等;平时喜欢美食、旅游、宠物、健身、篮球、乒乓球等。希望能和大家交流分享。

评论

发布
暂无评论
Rust从0到1-集合-Hash Map