哈希表 HashMap

和动态数组Vec一样，哈希表(HashMap)也是Rust内置的集合类型之一，同属std::collections模块下。

它提供了一个平均复杂度为O(1)的查询方法，是实现快速搜索必备的类型之一。

这里呢，主要给大家介绍一下HashMap的几种典型用法。

HashMap的要求

顾名思义, HashMap 要求一个可哈希（实现 Hash trait）的Key类型，和一个编译时知道大小的Value类型。
同时，Rust还要求你的Key类型必须是可比较的，在Rust中，你可以为你的类型轻易的加上编译器属性：

  1. #[derive(PartialEq, Eq, Hash)]

这样，即可将你的类型转换成一个可以作为Hash的Key的类型。
但是，如果你想要自己实现Hash这个trait的话，你需要谨记两点：

    1. 如果 Key1==Key2 ,那么一定有 Hash(Key1) == Hash(Key2)
    1. 你的Hash函数本身不能改变你的Key值，否则将会引发一个逻辑错误（很难排查，遇到就完的那种）

什么？你看到 std::hash::Hash 这个 trait 中的函数没有&mut self的啊！但是，你不要忘了Rust中还有Cell和RefCell这种存在，他们提供了不可变对象的内部可变性，具体怎么变呢，请参照第20章。

另外，要保证你写的Hash函数不会被很轻易的碰撞，即 Key1! = Key2，但 Hash(Key1)==Hash(Key2)，碰撞的严重了，HashMap甚至有可能退化成链表！

这里笔者提议，别费劲，就按最简单的来就好。

增删改查

对于这种实用的类型，我们推荐用一个例子来解释：

  1. use std::collections::HashMap;
  3. // 声明
  4. let mut come_from = HashMap::new();
  5. // 插入
  6. come_from.insert("WaySLOG", "HeBei");
  7. come_from.insert("Marisa", "U.S.");
  8. come_from.insert("Mike", "HuoGuo");
  10. // 查找key
  11. if !come_from.contains_key("elton") {
  12.     println!("Oh, 我们查到了{}个人，但是可怜的Elton猫还是无家可归", come_from.len());
  13. }
  15. // 根据key删除元素
  16. come_from.remove("Mike");
  17. println!("Mike猫的家乡不是火锅！不是火锅！不是火锅！虽然好吃！");
  19. // 利用get的返回判断元素是否存在
  20. let who = ["MoGu", "Marisa"];
  21. for person in &who {
  22.     match come_from.get(person) {
  23.         Some(location) => println!("{} 来自: {}", person, location),
  24.         None => println!("{} 也无家可归啊.", person),
  25.     }
  26. }
  28. // 遍历输出
  29. println!("那么，所有人呢？");
  30. for (name, location) in &come_from {
  31.     println!("{}来自: {}", name, location);
  32. }

这段代码输出：

  1. Oh, 我们查到了3个人，但是可怜的Elton猫还是无家可归
  2. Mike猫的家乡不是火锅！不是火锅！不是火锅！虽然好吃！
  3. MoGu 也无家可归啊.
  4. Marisa 来自: U.S.
  5. 那么，所有人呢？
  6. Marisa来自: U.S.
  7. WaySLOG来自: HeBei

entry

我们在编程的过程中，经常遇到这样的场景，统计一个字符串中所有的字符总共出现过几次。借助各种语言内置的Map类型我们总能完成这件事，但是完成的几乎都并不令人满意。很多人讨厌的一点是：为什么我要判断这个字符在字典中有没有出现，就要写一个大大的if条件！烦不烦？烦！于是，现代化的编程语言开始集成了类似Python里setdefault类似的特性（方法），下面是一段Python代码：

  1. val = {}
  2. for c in "abcdefasdasdawe":
  3.     val[c] = 1 + val.setdefault(c, 0)
  4. print val

唔，总感觉怪怪的。那么Rust是怎么解决这个问题的呢？
以下内容摘自标注库api注释：

  1. use std::collections::HashMap;
  3. let mut letters = HashMap::new();
  5. for ch in "a short treatise on fungi".chars() {
  6.     let counter = letters.entry(ch).or_insert(0);
  7.     *counter += 1;
  8. }
  10. assert_eq!(letters[&'s'], 2);
  11. assert_eq!(letters[&'t'], 3);
  12. assert_eq!(letters[&'u'], 1);
  13. assert_eq!(letters.get(&'y'), None);

Rust为我们提供了一个名叫 entry 的api，它很有意思，和Python相比，我们不需要在一次迭代的时候二次访问原map，只需要借用 entry 出来的Entry类型（这个类型持有原有HashMap的引用）即可对原数据进行修改。就语法来说，毫无疑问Rust在这个方面更加直观和具体。