63、HashMap（哈希表）
HashMap（哈希表）
我们对Index/IndexMut的实现并不理想：我们需要按照id遍历整个Vec来检索想要的ticket；时间复杂度为O(n)，其中n就是TicketStore里面ticket的数量。
我们可以通过使用不同的数据结构来存储ticket：HashMap<K,V>（哈希表）
use std::collections::HashMap;
// Type inference lets us omit an explicit type signature (which
// would be `HashMap<String, String>` in this example).
// 类型推断允许我们省略显式的类型签名（在此例中，该类型应为 HashMap<String, String>）。
let mut book_reviews = HashMap::new();
book_reviews.insert(
"Adventures of Huckleberry Finn".to_string(),
"My favorite book.".to_string(),
);
HashMap适用于键值对，它对两者都是泛型：K是键类型的有效参数，V是值类型的有效参数。
插入、查找和删除的预期成本是常数，即 O(1)。这对我们的用例来说听起来完美，对吧？
关键要求
HashMap的结构体定义中没有trait bound，但是在其方法里可以找到一些。让我们来看看insert操作，例如：
// Slightly simplified
impl<K, V> HashMap<K, V>
where
K: Eq + Hash,
{
pub fn insert(&mut self, k: K, v: V) -> Option<V> {
// [...]
}
}
Key类型必须实现Eq和Hashtrait。
让我们深入了解这两个trait。
Hash
散列函数（散列器）可以将潜在的无限值得集合（如所有可能的字符串）映射到有界范围（例如u64这么大）。
目前有许多不同的散列函数，每种函数都有不同的特性（速度，碰撞风险，可逆性等等）。
哈希表，顾名思义，其背后原理就是哈希函数。它对键进行散列，然后使用散列来存储/检索相关的值。这种策略要求Key类型必须是可以散列的，因此K上绑定了Hashtrait。
我们可以在std::hash模块找到Hashtrait：
pub trait Hash {
// Required method
fn hash<H>(&self, state: &mut H)
where H: Hasher;
}
我们很少手动实现Hash，大多数情况下，可以直接用派生宏：
#[derive(Hash)]
struct Person {
id: u32,
name: String,
}
Eq
HashMap必须能够比较键的相等性。这在处理哈希冲突的时候尤为重要——当两个不同的键散列为相同的值时。
这大概就是PartialEqtrait的用途吧，差不多。PartialEq对于HashMap来说是不够的，因为它不能保证reflexivity（自反性），即确保a==a始终为true。
例如，浮点数（f32和f64）实现了PartialEq，但是，但是我们不能保证他们的自反性：f32::NAN==f32::NAN是false。
自反性对于HashMap正常工作非常重要：没有它，我们将不能用与插入时相同的键再次散列计算以从map中检索值。
Eqtrait通过自反性属性拓展了PartialEq：
pub trait Eq: PartialEq {
// No additional methods
}
这是一个标记trait：它不添加任何新方法，只是让编译器知道PartialEq实现的相等的逻辑是自反的。
派生PartialEq时，可以自动派生Eq：
#[derive(PartialEq, Eq)]
struct Person {
id: u32,
name: String,
}
Eq 和 Hash 是关联的
Eq 和 Hash 之间存在一个隐式约定：如果两个键相等，它们的哈希值也必须相同。这对于HashMap的工作至关重要。如果我们违反了这个约定，那么我们在使用HashMap时会得到无意义的结果。
练习
这次的练习就是让我们完善之前的代码，为它添加HashMap的功能，直接看题目吧：
// TODO: Replace `todo!()`s with the correct implementation.
// Implement additional traits on `TicketId` if needed.
use std::collections::HashMap;
use std::ops::{Index, IndexMut};
use ticket_fields::{TicketDescription, TicketTitle};
#[derive(Clone)]
pub struct TicketStore {
tickets: HashMap<TicketId, Ticket>,
counter: u64,
}
#[derive(Clone, Copy, Debug, PartialEq/* TODO */)]
pub struct TicketId(u64);
#[derive(Clone, Debug, PartialEq)]
pub struct Ticket {
pub id: TicketId,
pub title: TicketTitle,
pub description: TicketDescription,
pub status: Status,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct TicketDraft {
pub title: TicketTitle,
pub description: TicketDescription,
}
#[derive(Clone, Debug, Copy, PartialEq, Eq)]
pub enum Status {
ToDo,
InProgress,
Done,
}
impl TicketStore {
pub fn new() -> Self {
Self {
tickets: todo!()
counter: 0,
}
}
pub fn add_ticket(&mut self, ticket: TicketDraft) -> TicketId {
let id = TicketId(self.counter);
self.counter += 1;
let ticket = Ticket {
id,
title: ticket.title,
description: ticket.description,
status: Status::ToDo,
};
todo!()
id
}
pub fn get(&self, id: TicketId) -> Option<&Ticket> {
todo!()
}
pub fn get_mut(&mut self, id: TicketId) -> Option<&mut Ticket> {
todo!()
}
}
impl Index<TicketId> for TicketStore {
type Output = Ticket;
fn index(&self, index: TicketId) -> &Self::Output {
self.get(index).unwrap()
}
}
impl Index<&TicketId> for TicketStore {
type Output = Ticket;
fn index(&self, index: &TicketId) -> &Self::Output {
&self[*index]
}
}
impl IndexMut<TicketId> for TicketStore {
fn index_mut(&mut self, index: TicketId) -> &mut Self::Output {
self.get_mut(index).unwrap()
}
}
impl IndexMut<&TicketId> for TicketStore {
fn index_mut(&mut self, index: &TicketId) -> &mut Self::Output {
&mut self[*index]
}
}
有多个地方的代码需要修改，首先是：
#[derive(Clone, Copy, Debug, PartialEq/* TODO */)]
pub struct TicketId(u64);
我们需要完善一些派生宏，根据前面学到的内容，我们在这里填写Eq和Hash就对了。
第二，是这里的new方法：
pub fn new() -> Self {
Self {
tickets: todo!()
counter: 0,
}
}
之前的代码是在这里初始化Vec，很显然我们要用的是HashMap来替换掉它，所以我们就可以在这里编写：
pub fn new() -> Self {
Self {
tickets: HashMap::new(),
counter: 0,
}
}
然后就是add_ticket这个方法，直接猜也能猜出来，我们要实现的是HashMap添加数据的功能：
pub fn add_ticket(&mut self, ticket: TicketDraft) -> TicketId {
let id = TicketId(self.counter);
self.counter += 1;
let ticket = Ticket {
id,
title: ticket.title,
description: ticket.description,
status: Status::ToDo,
};
self.tickets.insert(id, ticket);
id
}
就是插入这样一行代码就可以了self.tickets.insert(id, ticket);，和常规的C++，Java等语言的操作方式都很像。
最后就是这两个方法：
pub fn get(&self, id: TicketId) -> Option<&Ticket> {
todo!()
}
pub fn get_mut(&mut self, id: TicketId) -> Option<&mut Ticket> {
todo!()
}
也是一样的，我们要做的是根据ID进行查询，还是查找HashMap提供的get方法，于是这样编写代码：
pub fn get(&self, id: TicketId) -> Option<&Ticket> {
self.tickets.get(&id)
}
pub fn get_mut(&mut self, id: TicketId) -> Option<&mut Ticket> {
self.tickets.get_mut(&id)
}
最终代码也是成功运行了，并顺利通过了测试。
以上就是这一节的内容了。
