Rust 常用集合（下）

1、使用 Hash Map 储存键值对

1.1 新建一个哈希 map

1.2 访问哈希 map 中的值

1.3 哈希 map 和所有权

1.4 更新哈希 map

1.4.1 覆盖一个值

1.4.2 只在键没有对应值时插入键值对

1.4.3 根据旧值更新一个值

1.4.4 移除hash map的某一项

1.4.5 清空hash map

1.5 哈希函数

1.6 总结

1、使用 Hash Map 储存键值对

最后介绍的常用集合类型是 哈希 map（hash map）。HashMap<K, V> 类型储存了一个键类型 K 对应一个值类型 V 的映射。它通过一个 哈希函数（hashing function）来实现映射，决定如何将键和值放入内存中。很多编程语言支持这种数据结构，不过通常有不同的名字：哈希、map、对象、哈希表或者关联数组。

哈希 map 可以用于需要任何类型作为键来寻找数据的情况，而不是像 vector 那样通过索引。例如，在一个游戏中，你可以将每个团队的分数记录到哈希 map 中，其中键是队伍的名字而值是每个队伍的分数。给出一个队名，就能得到他们的得分。

1.1 新建一个哈希 map

可以通过 get 方法并提供对应的键来从哈希 map 中获取值，如下所示：

fn main() {
    let mut scores = HashMap::new();
    let key = "math";
    scores.insert(key, 93);
    println!("{:?}", scores);
}

注意必须首先 use 标准库中集合部分的 HashMap。在这三个常用集合中，HashMap 是最不常用的，所以并没有被自动引用。标准库中对 HashMap 的支持也相对较少，例如，并没有内建的构建宏。

像 vector 一样，哈希 map 将它们的数据储存在堆上，这个 HashMap 的键类型是 String 而值类型是 i32。类似于 vector，哈希 map 是同质的：所有的键必须是相同类型，值也必须都是相同类型。

1.2 访问哈希 map 中的值

可以通过 get 方法并提供对应的键来从哈希 map 中获取值，如下所示：

fn main() {
    let mut scores = HashMap::new();
    let key = "math";
    scores.insert(key, 93);
    println!("{:?}", scores);
    println!("{:?}", scores.get(&key).copied().unwrap_or(0)); // 93
}

get 方法返回 Option<&V>，如果某个键在哈希 map 中没有对应的值，get 会返回 None。程序中通过调用 copied 方法来获取一个 Option<i32> 而不是 Option<&i32>，接着调用 unwrap_or 在 scores 中没有该键所对应的项时将其设置为零。

可以使用与 vector 类似的方式来遍历哈希 map 中的每一个键值对，也就是 for 循环：

fn main() {
    let mut scores = HashMap::new();
    let key = "math";
    scores.insert(key, 93);
    for (key, value) in &scores {
        println!("{:?}: {:?}", key, value)
    }
}

这会以任意顺序打印出每一个键值对：

"math": 93

1.3 哈希 map 和所有权

对于像 i32 这样的实现了 Copy trait 的类型，其值可以拷贝进哈希 map。对于像 String 这样拥有所有权的值，其值将被移动而哈希 map 会成为这些值的所有者，如下所示：

fn main() {
    let mut scores = HashMap::new();
    let key = String::from("math");
    scores.insert(key, 93);
    println!("{key}");  // 编译报错，key的所有权被改变
}

当 insert 调用将 key 移动到哈希 map 中后，key的所有权将会改变，打印的地方会报错。

如果将值的引用插入哈希 map，这些值本身将不会被移动进哈希 map。但是这些引用指向的值必须至少在哈希 map 有效时也是有效的。

1.4 更新哈希 map

尽管键值对的数量是可以增长的，每个唯一的键只能同时关联一个值，反之不一定成立。

当我们想要改变哈希 map 中的数据时，必须决定如何处理一个键已经有值了的情况。可以选择完全无视旧值并用新值代替旧值。可以选择保留旧值而忽略新值，并只在键没有对应值时增加新值。

1.4.1 覆盖一个值

如果我们插入了一个键值对，接着用相同的键插入一个不同的值，与这个键相关联的旧值将被替换。

fn main() {
    let mut scores = HashMap::new();
    let key1 = String::from("math");
    let key2 = String::from("math");
    scores.insert(key1, 93);
    scores.insert(key2, 100);
    println!("{:?}", scores); // {"math": 100}
}

1.4.2 只在键没有对应值时插入键值对

我们经常会检查某个特定的键是否已经存在于哈希 map 中并进行如下操作：如果哈希 map 中键已经存在则不做任何操作。如果不存在则连同值一块插入。

为此哈希 map 有一个特有的 API，叫做 entry，它获取我们想要检查的键作为参数。entry 函数的返回值是一个枚举，Entry，它代表了可能存在也可能不存在的值。如下所示：

fn main() {
    let mut scores = HashMap::new();
    let key1 = String::from("math");
    let key2 = String::from("math");
    scores.entry(key1).or_insert(93);
    scores.entry(key2).or_insert(100);
    println!("{:?}", scores);  // {"math": 93}
}

Entry 的 or_insert 方法在键对应的值存在时就返回这个值的可变引用，如果不存在则将参数作为新值插入并返回新值的可变引用。这比编写自己的逻辑要简明的多，另外也与借用检查器结合得更好。

1.4.3 根据旧值更新一个值

另一个常见的哈希 map 的应用场景是找到一个键对应的值并根据旧的值更新它。例如，以下示例中统计数组中每个单词出现的次数。

fn main() {
    let mut scores = HashMap::new();
    let arr = ["math", "other", "english", "other", "english"];
    for w in arr {
        let count = scores.entry(w).or_insert(0);
        *count += 1;
    }
    println!("{:?}", scores);  // {"english": 2, "math": 1, "other": 2}
}

这里我们将这个可变引用储存在 count 变量中，所以为了赋值必须首先使用星号（*）解引用 count。这个可变引用在 for 循环的结尾离开作用域，这样所有这些改变都是安全的并符合借用规则。

1.4.4 移除hash map的某一项

可以根据传入的key值，删除hash map中的key以及对应的值。如下所示：

fn main() {
    let mut scores = HashMap::new();
    let arr = ["math", "other", "english", "other", "english", "english"];
    for w in arr {
        let count = scores.entry(w).or_insert(0);
        *count += 1;
    }
    scores.remove("math");
    println!("{:?}", scores); // {"other": 2, "english": 3}
}

1.4.5 清空hash map

如果需要清空一个hash ma的值，可以使用clear() 方法，如下所示：

fn main() {
    let mut scores = HashMap::new();
    let arr = ["math", "other", "english", "other", "english", "english"];
    for w in arr {
        let count = scores.entry(w).or_insert(0);
        *count += 1;
    }
    println!("{:?}", scores.clear()); // ()
}

1.5 哈希函数

HashMap 默认使用一种叫做 SipHash 的哈希函数，它可以抵御涉及哈希表（hash table）1 的拒绝服务（Denial of Service, DoS）攻击。然而这并不是可用的最快的算法，不过为了更高的安全性值得付出一些性能的代价。如果性能监测显示此哈希函数非常慢，以致于你无法接受，你可以指定一个不同的 hasher 来切换为其它函数。hasher 是一个实现了 BuildHasher trait 的类型。

crates.io 有其他人分享的实现了许多常用哈希算法的 hasher 的库。

https://en.wikipedia.org/wiki/SipHash