HashMap

我们对 Index/IndexMut 的实现并不理想：我们需要遍历整个 Vec 来通过 ID 获取工单；算法复杂度为 O(n)，其中 n 是存储中工单的数量。

我们可以通过使用不同的数据结构 HashMap<K, V> 来改善这一情况来存储工单。

#![allow(unused)]
fn main() {
use std::collections::HashMap;

// 类型推导允许我们省略显式的类型签名（在这个例子中将是 `HashMap<String, String>`）。
let mut book_reviews = HashMap::new();

book_reviews.insert(
    "哈克贝利·费恩历险记".to_string(),
    "我最喜欢的书.".to_string(),
);
}

HashMap 通过键值对工作。它对两者都具有泛型性：K 是键类型的泛型参数，而 V 是值类型的泛型参数。

插入、检索和移除的预期成本是恒定的，即 O(1)。这听起来非常适合我们的应用场景，不是吗？

键的要求

虽然 HashMap 的结构定义上没有特征界限，但你可以在其方法上找到一些。以 insert 为例：

#![allow(unused)]
fn main() {
// 略微简化
impl<K, V> HashMap<K, V>
where
    K: Eq + Hash,
{
    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
        // [...]
    }
}
}

键的类型必须实现 Eq 和 Hash 特征。

Hash

哈希函数（或散列器）将一个潜在无限的值集合（例如，所有可能的字符串）映射到一个有限范围内（例如，一个 u64 值）。有许多不同的哈希函数，各有不同的属性（速度、碰撞风险、可逆性等）。

顾名思义，HashMap 在幕后使用哈希函数。它对你的键进行哈希运算，然后使用该哈希值来存储/检索相关的值。这种策略要求键类型必须是可哈希的，因此在 K 上有 Hash 特征界限。

你可以在 std::hash 模块中找到 Hash 特征：

#![allow(unused)]
fn main() {
pub trait Hash {
    // 必须实现的方法
    fn hash<H>(&self, state: &mut H)
       where H: Hasher;
}
}

你很少会手动实现 Hash，大多数时候你会通过派生来实现它：

#![allow(unused)]
fn main() {
#[derive(Hash)]
struct Person {
    id: u32,
    name: String,
}
}

Eq

HashMap 必须能够比较键的相等性。在处理哈希碰撞时这一点尤为重要——即两个不同的键哈希到相同的值。

你可能疑惑：这不是 PartialEq 特征的作用吗？几乎！但 PartialEq 对于 HashMap 来说不够，因为它不保证自反性，即 a == a 总是 true。例如，浮点数 (f32 和 f64) 实现了 PartialEq，但它们不满足自反性：f32::NAN == f32::NAN 是 false。自反性对于 HashMap 正确工作至关重要：没有它，你将无法使用插入时的相同键从映射中检索值。

Eq 特征扩展了 PartialEq 并包含了自反性：

#![allow(unused)]
fn main() {
pub trait Eq: PartialEq {
    // 无新增方法
}
}

它是一个标记特征：它不添加任何新方法，只是你向编译器表明在 PartialEq 中实现的等价逻辑是自反性的一种方式。

当你派生 PartialEq 时，也可以自动派生 Eq：

#![allow(unused)]
fn main() {
#[derive(PartialEq, Eq)]
struct Person {
    id: u32,
    name: String,
}
}

Eq 和 Hash 的联系

Eq 和 Hash 之间存在着隐含的约定：如果两个键相等，它们的哈希值也必须相等。这对于 HashMap 正确工作至关重要。如果你破坏了这个约定，使用 HashMap 时将会得到不合逻辑的结果。