• 哈希表 HashMap
    • HashMap的要求
    • 增删改查
    • entry

    哈希表 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在这个方面更加直观和具体。