集合 — Rust的STL

CPP —> Standard Template Library

Rust 标准库包含多个集合，这些集合是泛型类型，用于在内存中存储各种数据。

Rust 的集合与其他语言的集合之间的一些系统性差异：

• 首先，移动和借用无处不在。Rust 使用移动来避免对值做深拷贝。这就是 Vec::push(item) 方法会按值而非按引用来获取参数的原因。这样值就会 移动到向量中。将 Rust String 压入 Vec 中会很快，因为 Rust 不必复制字符串的字符数 据，并且字符串的所有权始终是明晰的。
• 其次，Rust 没有失效型错误，也就是当程序仍持有指向集合内部数据的指针时，集合被重新调整大小或发生其他变化而导致的那种悬空指针错误。失效型错误是 C++ 中未定义行为的另一个来源，即使在内存安全的语言中，它们也会偶尔导致ConcurrentModificationException。Rust 的借用检查器在编译期就可以排除这些错误。

Rust 没有 null，因此在其他语言使用 null 的地方 Rust 会使用 Option。

本文介绍Rust 的 8 个标准集合，它们都是泛型类型

• Vec（普通向量） 　可增长的、分配在堆上的 T 类型值数组。
• VecDeque（双端队列向量）　　与 Vec 类似，但更适合用作先入先出队列。它支持在列表的前面和后面高效地添加值和移除值，但代价是会让所有其他的操作都稍微变慢一些。
• BinaryHeap（二叉堆） 　优先级队列。BinaryHeap 中的值是精心组织过的，因此始终可以高效地 查找和移除其最大值。
• HashMap（哈希 Map） 　由键-值对构成的表。通过键查找值很快。其条目会以任意顺序存储。
• BTreeMap（B 树 Map） 　与 HashMap 类似，但它会根据键来对条目进行排序。 BTreeMap 会以 String 的比较顺序来存储其条目。除非需要让条目保持排序状态，否则用 HashMap 更快一些。
• HashSet（哈希 Set） 　由 T 类型的值组成的 Set。它既能很快地添加值和移除值，也能很快地查 询给定值是否在此 Set 中。
• BTreeSet（B 树 Set） 　与 HashSet 类似，但它会让元素按值排序。同样，除非需要让数据保 持排序状态，否则用 HashSet 更快一些。
• 因为 LinkedList 很少使用（对于大多数用例，在性能和接口方面有更好的替代方案），所以这里就不展开讲解了。

Vec<T>向量

创建向量的最简单方法是使用 vec! 宏：

rust">// 创建一个空向量
let mut numbers: Vec<i32> = vec![];// 使用给定内容创建一个向量
let words = vec!["step", "on", "no", "pets"];
let mut buffer = vec![0u8; 1024]; // 1024个内容为0的字节

向量具有 3 个字段：长度、容量和指向用于存储元素的堆分配内存的指针。图展示了前面的向量在内存中的布局方式。空向量 numbers 最初的容量为 0。直到添加第一个元素之前，不会为其分配堆内存。

Vec 也实现了 std::iter::FromIterator，所以可以使 用迭代器的 .collect() 方法从任意迭代器创建向量

rust">// 把另一个集合转换成向量
let my_vec = my_set.into_iter().collect::<Vec<String>>();

访问元素

通过索引来获取数组、切片或向量的元素非常简单，越界就会Panic

下面这些方法可以轻松访问向量或切片的特定元素（请注意，所有的切片方法也 都适用于数组和向量）：

• slice.first()（第一个） 　返回对 slice 的第一个元素的引用（如果有的话）。 　返回类型为 Option<&T>，所以如果 slice 为空则返回值为 None，如果 不为空则返回 Some(&slice[0])。
• slice.last()（最后一个） 　与 first 类似，但会返回对最后一个元素的引用。
• slice.get(index)（获取） 　如果其存在，就返回 slice[index] 引用的 Some 值。如果 slice 的元 素少于 index+1 个，则返回 None。
• slice.first_mut()（第一个可变）、slice.last_mut()（最后一个 可变）和 slice.get_mut(index)（获取指定索引可变） 　这些方法是前述 slice.first() 等方法的变体，但借入的是可变引用。因为按值返回 T 就意味着移动它，所以一些需要就地访问元素的方法通常会按 引用返回这些元素。.to_vec() 方法是一个例外，它会复制这些元素。
• slice.to_vec()（转向量） 　克隆整个切片，返回一个新向量：

迭代

向量、数组和切片是可迭代的，要么按值迭代 ，要么按引用迭代

• 遍历Vec<T> 或数组 [T; N] 会生成 T 类型的条目。这些元素会逐个从向量或数组中移动出来并被消耗掉。
• 遍历 &[T; N]、&[T] 或 &Vec <T>类型的值（对数组、切片或向量的引 用）会生成 &T 类型的条目，即对单个元素的引用，这些元素不会移动出 3 3来。
• 遍历 &mut [T; N]、&mut [T] 或 &mut Vec<T> 类型的值会生成 &mut T 类型的条目。

数组、切片和向量也有 .iter() 方法和 .iter_mut() 方，以用于创建一个会生成对其元素的引用的迭代器。

扩大向量与收缩向量

数组、切片或向量的长度是它们已经包含的元素数量。

• slice.len()（长度） 　返回 slice 的长度，类型为 usize。
• slice.is_empty()（为空？） 　如果 slice 未包含任何元素（slice.len() == 0）则为真。

数组和切片中没有这些方 法，因为数组和切片一旦创建就无法调整大小。

向量的所有元素都存储在连续的、分配在堆上的内存块中。向量的**容量**就是该内存块可以容纳的最大元素数量。Vec 通常会替你管理容量，当需要更多空间时它 会自动分配更大的缓冲区并将元素移入其中。下面是一些显式管理容量的方法：

• Vec::with_capacity(n)（自带容量） 　创建一个容量为 n 的新的空向量。

• vec.capacity()（取容量） 　返回 vec 的容量，类型为 usize。vec.capacity() >= vec.len() 始终是成立的。

• vec.reserve(n)（预留）　　确保向量至少有足够的备用容量来容纳另外 n 个元素，也就是说， vec.capacity() 至少等于 vec.len() + n。如果已经有足够的空间，就什 么也不做。如果没有，则会分配一个更大的缓冲区并将向量的内容移入其中。

• vec.reserve_exact(n)（精确预留） 　与 vec.reserve(n) 类似，但要求 vec 不要为未来的增长分配任何多于 n 的额外容量。调用此方法后，vec.capacity() 应该精确等于 vec.len() + n。

• vec.shrink_to_fit()（缩小到刚好够） 　如果 vec.capacity() 大于 vec.len()，则尝试释放额外的内存。 Vec 还有许多用来添加或移除元素的方法，它们可以改变向量的长度。所有 这些方法都可以通过可变引用获取其 self 参数。 下面这两个方法会在向量的末尾添加或移除单个值。

• vec.push(value)（推入） 　将给定 value 添加到 vec 的末尾。

• vec.pop()（弹出） 　移除并返回最后一个元素。返回类型是 Option。如果弹出的元素是 x，则返回 Some(x)；如果向量已经为空，则返回 None。 请注意，.push() 会按值而不是按引用接受其参数。同样，.pop() 会返回弹出的值，而不是引用。本节中剩下的大部分方法也是如此。它们可以将值移动进 和移动出向量。 下面这两个方法会在向量的任意位置添加或移除一个值。

• vec.insert(index, value)（插入） 　在 vec[index] 处插入给定的 value，将 vec[index…] 中的所有当前 值向右平移一个位置以腾出空间。 　如果 index > vec.len()，则会引发 panic。

• vec.remove(index)（移除） 　移除并返回 vec[index]，将 vec[index+1…] 中的所有当前值向左平 移一个位置以填补空白。 　如果 index >= vec.len()，则会引发 panic，因为在这种情况下要移除 的 vec[index] 元素并不存在。 　向量越长，这个操作就越慢。如果需要经常执行 vec.remove(0)，请考虑 使用 VecDeque来代替 Vec。 需要移动的元素越多，.insert() 和 .remove() 的速度就会越慢。 下面这 4 个方法可以把向量的长度更改为特定值。

• vec.resize(new_len, value)（调整大小） 　将 vec 的长度设置为 new_len。如果该操作会增加 vec 的长度，则以 value 的副本填补新空间。元素类型必须实现 Clone 特型。

• vec.resize_with(new_len, closure)（以……调整大小） 　与 vec.resize 类似，但会调用闭包来构造每个新元素。它能用于不可 Clone 的元素构成的向量。

• vec.truncate(new_len)（截断） 　将 vec 的长度减少到 new_len，丢弃 vec[new_len…] 范围内的任何元 素。 　如果 vec.len() 已经小于或等于 new_len，则什么也不会发生。

• vec.clear()（清空） 　从 vec 中移除所有元素。此方法的效果和 vec.truncate(0) 一样。 下面这 4 个方法可以一次添加或移除多个值。

• vec.extend(iterable)（扩展）　　按顺序在 vec 末尾添加来自给定 iterable 值的所有条目。此方法就像 .push() 的多值版本。iterable 参数可以是实现了 IntoIterator 的任何值。此方法非常有用，所以我们为其定义了一个标准特型 Extend，所有标准集 合都实现了该特型

• vec.split_off(index)（拆分出） 　与 vec.truncate(index) 类似，但此方法会返回一个 Vec，其中包 含从 vec 末尾移除的那些值。此方法就像是 .pop() 的多值版本。

• vec.append(&mut vec2)（追加） 　这会将 vec2 的所有元素移动到 vec 中，其中 vec2 是 Vec 类型的另 一个向量。之后，vec2 会被清空。 　此方法与 vec.extend(vec2) 类似，不同之处在于调用 extend 之后 vec2 仍然存在，其容量也不受影响。

• vec.drain(range)（抽取） 　这将从 vec 中移除 range 范围内的切片 vec[range]，并返回对所移除 元素的迭代器，其中 range 是范围值，类似 .. 或 0..4。 还有一些略显古怪的方法可以从向量中选择性地移除一些元素。

• vec.retain(test)（留下） 　移除所有未通过给定测试的元素。test 参数是实现了 FnMut(&T) -> bool 的函数或闭包。针对 vec 的每个元素，此方法都会调用 test(&element)，如果函数或闭包返回了 false，就会从向量中移除并丢弃 此元素。除了性能上略有差异，此方法和下面的写法很像：vec = vec.into_iter().filter(test).collect();

• vec.dedup()（去重） 　丢弃重复的元素，类似于 Unix shell 实用程序 uniq。此方法会扫描 vec 以 查找彼此相等的相邻元素，然后会从这些相等值中保留一个并丢弃多余的值：

  rust">let mut byte_vec = b"Misssssssissippi".to_vec();
  byte_vec.dedup();
  assert_eq!(&byte_vec, b"Misisipi");
  

  此方法只会移除相邻的重复项。要想消除所有重复项，你有 3 个选择：在调用 .dedup() 之前对向量进 行排序、将数据移动到一个 Set 中，或者（为了保持元素的原始顺序）使用如 下 .retain() 技巧

  rust">let mut byte_vec = b"Misssssssissippi".to_vec();
  let mut seen = HashSet::new();
  byte_vec.retain(|r| seen.insert(*r));
  assert_eq!(&byte_vec, b"Misp");
  // 上述代码的工作原理是当 Set 已经包含我们要插入的条目时 .insert()就会返回 false。
  

• vec.dedup_by(same)（根据 same 调用结果去重） 　与 vec.dedup() 类似，但此方法会使用函数或闭包 same(&mut elem1, &mut elem2) 而不是 == 运算符来检查两个元素是否应被视为相等。

• vec.dedup_by_key(key)（根据 key 属性去重） 　与 vec.dedup() 类似，但此方法会在 key(&mut elem1) == key(&mut elem2) 时将两个元素视为相等。 　如果 errors 是一个 Vec<Box<dyn Error>>，你可以这样写：

  rust">// 移除带有相同信息的多余错误（error）
  errors.dedup_by_key(|err| err.to_string());
  

上面所有方法，只有 .resize() 会克隆值，其他方法都是将值从一 个地方移动到另一个地方。

联结

以下两个方法可用于数组的数组，即其元素本身也是数组、切片或向量的数组、 切片或向量。

• slices.concat()（串联） 　返回通过串联所有切片组装成的新向量。assert_eq!([[1, 2], [3, 4], [5, 6]].concat(), vec![1, 2, 3, 4, 5, 6]);
• slices.join(&separator)（联结） 　与 concat 类似，只是在这些切片之间插入了值 separator 的副本。assert_eq!([[1, 2], [3, 4], [5, 6]].join(&0), vec![1, 2, 0, 3, 4, 0, 5, 6]);

拆分

同时获得多个对数组、切片或向量中元素的不可变引用是比较容易的，但获取多个可变引用就不那么容易了

Rust 有几种方法可以同时借入对数组、切片或向量的两个或多个部分的可变引用。与前面的代码不同，这些方法是安全的，因为根据设计，它们总会把数据拆 分成几个不重叠的区域。这里的大部分方法在处理非 mut 切片时也很方便，因此每个方法都有 mut 版本和非 mut 版本

slice.split(|&x|x==0) 输出 中的小矩形是由于存在两个相邻的分隔符而生成的空切片，并且 rsplitn 会按 从后向前的顺序生成其输出，这与另外几个方法不同

这些方法都没有直接修改数组、切片或向量，它们只是返回了对内部数据中各部 分的新引用。

• slice.iter()（迭代器）和 slice.iter_mut()（可变迭代器） 　生成对 slice 中每个元素的引用。

• slice.split_at(index)（拆分于）和 slice.split_at_mut(index)（可变拆分于）　　将一个切片分成两半，返回一个值对。slice.split_at(index) 等价于 (&slice[…index], &slice[index…])。如果 index 超出了限界，这两 个方法就会发生 panic。

• slice.split_first()（拆分首个）和 slice.split_first_mut() （可变拆分首个） 　同样会返回一个值对：对首个元素（slice[0]）的引用和对所有其余元素 （slice[1…]）的切片的引用。 　.split_first() 的返回类型是 Option<(&T, &[T])>，如果 slice 为空，则结果为 None。

• slice.split_last()（拆分末尾）和 slice.split_last_mut() （可变拆分末尾） 　与 slice.split_first() 和 slice.split_first_mut() 类似，但 这两个方法拆分出的是最后一个元素而不是首个元素。 　.split_last() 的返回类型是 Option<(&T, &[T])>。

• slice.split(is_sep)（拆分）和 slice.split_mut(is_sep)（可 变拆分） 　将 slice 拆分为一个或多个子切片，使用函数或闭包 is_sep 确定拆分位 置。这两个方法会返回一个遍历这些子切片的迭代器。 　当你消耗此迭代器时，这些方法会为切片中的每个元素调用 is_sep(&element)。如果 is_sep(&element) 为 true，则认为该元素是 分隔符。分隔符不会包含在输出的任何子切片中。 　输出总是至少包含一个子切片，每遇到一个分隔符就额外加一个。如果有多 个分隔符彼此相邻，或者有分隔符出现在 slice 的两端，则每对分隔符和两端 的分隔符分别会对应输出一个空的子切片。

• slice.split_inclusive(is_sep)（拆分，含分隔符）和 slice.split_inclusive_mut(is_sep)（可变拆分，含分隔符） 　与 split 和 split_mut 类似，但这两个方法会在前一个子切片的结尾包 含分隔符而不会排除它。

• slice.rsplit(is_sep)（右起拆分）和 slice.rsplit_mut(is_sep)（右起可变拆分） 　与 split 和 split_mut 类似，但这两个方法会从切片的末尾开始往前拆 分。 slice.splitn(n, is_sep)（拆分为 n 片）和 slice.splitn_mut(n, is_sep)（可变拆为 n 片） 　与 slice.rsplit(is_sep) 和 slice.rsplit_mut(is_sep) 类似， 但这两个方法最多会生成 n 个子切片。在找到前 n-1 个切片后，不会再调用 is_sep。最后一个子切片中会包含剩下的所有元素。

• slice.rsplitn(n, is_sep)（右起拆分为 n 片）和 slice.rsplitn_mut(n, is_sep)（右起可变拆分为 n 片） 　与 .splitn() 和 .splitn_mut() 类似，但是在使用这两个方法时，切 片会以相反的顺序扫描。也就是说，这两个方法会在切片中的最后而不是最前 n-1 个分隔符上进行拆分，并且子切片是从末尾开始向前生成的。

• slice.chunks(n)（分为长度为 n 的块）和 slice.chunks_mut(n) （分为长度为 n 的可变块） 　返回长度为 n 的非重叠子切片上的迭代器。如果 n 不能被 slice.len() 整除，则最后一个块包含的元素将不足 n 个。

• slice.rchunks(n)（右起分为长度为 n 的块）和 slice.rchunks_mut(n)（右起分为长度为 n 的可变块） 　与 slice.chunks 和 slice.chunks_mut 类似，但会从切片的末尾开始 向前拆分。

• slice.chunks_exact(n)（精确分为长度为 n 的块）和 slice.chunks_exact_mut(n)（精确分为长度为 n 的可变块） 　返回长度为 n 的非重叠子切片上的迭代器。如果 n 不能被 slice.len() 整除，则最后一个块（少于 n 个元素）可以在其结果的 remainder() 方法中 获取。

• slice.rchunks_exact(n)（右起精确分为长度为 n 的块）和 slice.rchunks_exact_mut(n)（右起精确分为长度为 n 的可变块） 　与 slice.chunks_exact 和 slice.chunks_exact_mut 类似，但会 从切片的末尾开始拆分。 还有一个迭代子切片的方法。

• slice.windows(n)（滑动窗口） 　返回一个其行为类似于 slice 中数据的“滑动窗口”的迭代器。这个迭代器 会生成一些横跨此 slice 中 n 个连续元素的子切片。它生成的第一个值是 &slice[0…n]，第二个值是 &slice[1…n+1]，以此类推。 　如果 n 大于 slice 的长度，则不会生成任何切片。如果 n 为 0，则此方法 会发生 panic。 　如果 days.len() == 31，那么就可以通过调用 days.windows(7) 来 生成 days 中所有相隔 7 天的时间段。 　大小为 2 的滑动窗口可用于探究数据序列如何从一个数据点变化到下一个 数据点：

  rust">let changes = daily_high_temperatures
   .windows(2) // 获得两个相邻的最高气温
   .map(|w| w[1] - w[0]) // 气温变化了多少？
   .collect::<Vec<_>>();
  

  因为各个子切片会重叠，所以此方法并没有返回可变引用的变体

交换

• slice.swap(i, j)（交换元素） 　交换 slice[i] 和 slice[j] 这两个元素。
• slice_a.swap_with_slice(slice_b)（互换内容）　　交换 slice_a 和 slice_b 的全部内容。slice_a 和 slice_b 的长度必须相同。 向量有一个关联方法，该方法可以高效地移除任何元素。
• vec.swap_remove(i)（交换后移除） 　移除并返回 vec[i]。与 vec.remove(i) 类似，但此方法不会将向量中 剩余的元素平移过来以填补空缺，而是简单地将 vec 的最后一个元素移动到空缺中。如果不关心向量中剩余条目的顺序，那么此方法会很有用，因为性能更高。

填充

• slice.fill(value)（填充） 　用 value 的克隆体填充切片。
• slice.fill_with(function)（以 function 回调填充） 　使用调用给定函数生成的值来填充切片。这对于实现了 Default 但未实现 Clone 的类型很有用，比如当 T 为不可复制类型时的 Option<T> 或 Vec<T>。

排序与搜索

切片提供的 3 个排序方法：

• slice.sort()（排序） 　将元素按升序排列。此方法仅当元素类型实现了 Ord 时才存在。

• slice.sort_by(cmp)（按 cmp 回调排序） 　对 slice 中的元素按函数或闭包 cmp 指定的顺序进行排序。cmp 必须实现 Fn(&T, &T) -> std::cmp::Ordering。　　手动实现 cmp 是一件痛苦的事，不过可以把它委托给别的 .cmp() 方法来 实现：students.sort_by(|a, b| a.last_name.cmp(&b.last_name))，如果想按一个字段排序，但当该字段相同时按另一个字段判定先后，则可以先把它们做成元组然后再进行比较。

  rust">students.sort_by(|a, b| {
   let a_key = (&a.last_name, &a.first_name);
   let b_key = (&b.last_name, &b.first_name);
   a_key.cmp(&b_key)
  });
  

• slice.sort_by_key(key)（按 key 回调排序） 　使用由函数或闭包型参数 key 给出的排序键对 slice 的元素按递增顺序排序。key 的类型必须实现 Fn(&T) -> K，这里要满足 K: Ord。 　这在 T 包含一个或多个有序字段时会很有用，因此它可以按多种方式排序：students.sort_by_key(|s| s.grade_point_average());按平均学分绩点排序，低分在前。请注意，在排序过程中不会缓存这些排序键值，因此 key 函数可能会被调 用 n 次以上。 　出于技术原因，key(element) 无法返回从元素借来的任何引用。下面这种写法行不通：

  rust">students.sort_by_key(|s| &s.last_name); // 错误：无法推断生命周期
  

以上 3 个方法都会执行稳定排序

反序排序：要想以相反的顺序排序，可以将 sort_by 与交换了两个参数的 cmp 闭包一起 使用。传入参数 |b, a| 而不是 |a, b| 可以有效地生成相反的顺序。或者， 也可以在排序之后调用 slice.reverse() 方法。

搜索

• slice.binary_search(&value)（二分搜索）
• slice.binary_search_by(&value, cmp)（按 cmp 回调二分搜索）
• slice.binary_search_by_key(&value, key)（按 key 闭包二分 搜索）

这些方法的返回类型是 Result<usize, usize>。如果在指定排序顺序 中 slice[index] 等于 value，那么这些方法就会返回 Ok(index)。如果找不到这样一个索引，那么这些方法就会返回 Err(insertion_point)，这样当你在 insertion_point 中插入 value 后，向量仍然会保持排好序的状态。

当然，只有在切片确实已经按指定顺序排序时二分搜索才有效。否则，结果将是没有意义的。

由于 f32 和 f64 具有 NaN 值，因此它们无法实现 Ord 并且不能直接用作排序 和二分搜索方法的键。要获得适用于浮点数据的类似方法，请使用 ord_subset crate。

可以用另一个方法在未排过序的向量中搜索。 slice.contains(&value)（包含） 　如果 slice 中有任何元素等于 value，则返回 true。这会简单地检查切片的每个元素，直到找到匹配项。value 同样是按引用传递的。 如果要在切片中查找值的位置（类似 JavaScript 中的 array.indexOf(value)），请使用迭代器：

slice.iter().position(|x| *x == value)返回 Option<usize>

比较切片

如果类型 T 支持 == 运算符和!=运算符（PartialEq 特型）， 那么数组 [T; N]、切片[T] 和向量 Vec<T> 也会支持这两个运算符。如果两 个切片的长度相同并且对应的元素也相等，那它们就是相等的。数组和向量也是 如此。

如果 T 支持运算符 <、<=、> 和 >=（PartialOrd 特型），那 么 T 的数组、切片和向量也会支持这些运算符。切片之间是按字典序比较的 （从左到右逐个比较）。 下面是执行常见的切片比较的两个便捷方法。

• slice.starts_with(other)（以 other 开头） 　如果 slice 的起始值序列等于 other 切片中的相应元素，则返回 true。
• slice.ends_with(other)（以 other 结尾） 　与上一个方法类似，但会检查 slice 的结尾值

随机元素

随机数并未内置在 Rust 标准库中，但在 rand crate 提供了以下两个方法，用于从数组、切片或向量中获取随机输出。

• slice.choose(&mut rng)（随机选取） 　返回对切片中随机元素的引用。与 slice.first() 和 slice.last() 类似，此方法会返回 Option<&T>，只有当切片为空时才返回 None。
• slice.shuffle(&mut rng)（随机洗牌） 　就地随机重排切片中的元素。切片必须通过可变引用传递。

这两个都是rand::Rng特型的方法，所以你需要一个 Rng（random number generator，随机数生成器），以便调用它们。通过调用rand::thread_rng() 很容易得到一个生成器。要对向量 my_vec 进行洗
牌：

rust">use rand::seq::SliceRandom;
use rand::thread_rng;
my_vec.shuffle(&mut thread_rng());

Rust 中不存在失效型错误

python迭代器失效：

my_list = [1, 3, 5, 7, 9]
for index, val in enumerate(my_list):
 if val > 4:
 del my_list[index] # bug：在迭代过程中修改列表
print(my_list)

这个程序打印出了 [1, 3, 7]。但是 7 显然大于 4。为什么失 控了？这就是失效型错误：程序在迭代数据时修改了数据，让迭代器失效了。在 Java 中，结果将是一个异常。在 C++ 中，这是未定义行为。在 Python 中，虽 然此行为有明确定义，但不直观：迭代器会跳过一个元素。这样一来，val 永远 不会等于 7，因此也就没有机会删除它了

在 Rust 中重现这个 bug：

rust">fn main() {
 let mut my_vec = vec![1, 3, 5, 7, 9];
 for (index, &val) in my_vec.iter().enumerate() {
     if val > 4 {
     	my_vec.remove(index); // 错误：不能把`my_vec`借用为可变的
     }
 } 
 println!("{:?}", my_vec);
}

Rust 在编译时就会拒绝这个程序。当我们调用 my_vec.iter() 时，它 借用了一个共享（非 mut）的向量引用。引用与迭代器的生命周期一样长，直到 for 循环结束。当存在不可变引用时，不能通过调用 my_vec.remove(index) 来修改向量

最简单的修改方法：my_vec.retain(|&val| val <= 4); 也可以像在 Python 或任何其他语言中那样使用 filter 创建一个新向量。

VecDeque<T>双端队列向量

Vec 只支持在末尾高效地添加元素和移除元素。当程序需要一个地方来存储“排队等候”的值时，Vec 可能会很慢。 Rust 的 std::collections::VecDeque 是一个双端队列（deque， double-ended queue）,支持在首端和尾端进行高效 的添加操作和移除操作。

• deque.push_front(value)（队首推入） 　在队列的首端添加一个值。
• deque.push_back(value)（队尾推入） 　在队列的尾端添加一个值。（此方法比 .push_front() 更常用，因为队 列通常的习惯是在尾端添加值，在首端移除值，就像人们在排队等候一样。）
• deque.pop_front()（队首弹出） 　移除并返回队列的首端值，如果队列为空则返回一个为 None 的 Option，就像 vec.pop() 那样。
• deque.pop_back()（队尾弹出） 　移除并返回队列的尾端值，同样返回 Option。
• deque.front()（队首）和 deque.back()（队尾） 　与 vec.first() 和 vec.last() 类似，这两个方法会返回对队列首端或 尾端元素的引用。返回值是一个 Option<&T>，如果队列为空则为 None。
• deque.front_mut()（队首，可变版）和 deque.back_mut()（队尾， 可变版） 　与 vec.first_mut() 和 vec.last_mut() 类似，这两个方法会返回 Option<&mut T>。

和 Vec 一样，VecDeque 用一块分配在堆上的内存来存储元素。与 Vec 不同， VecDeque 的数据并不总是从该区域的开头开始，它可以“回绕”到末尾。

这个双 端队列的元素按顺序排列是 [‘A’, ‘B’, ‘C’, ‘D’, ‘E’]。VecDeque 有 两个私有字段 start 和 stop，用于记住数据在缓冲区 中的首端位置和尾端位置。

从任一端向队列中添加一个值都意味着占用一个未使用的插槽。如果需要，可以回绕或分配更大的内存块。 VecDeque 会管理回绕，因此你不必费心于此。

通常，当你需要用到双端队列时，基本上只是需要 .push_back() 和 .pop_front() 这两个方法。用于创建队列的类型关联函数 VecDeque::new() 和 VecDeque::with_capacity(n) 和它们在 Vec 中的 对应函数一样。

VecDeque 还实现了 Vec 中的许多方法，比如 .len() 和 .is_empty()、.insert(index, value)、.remove(index)、.extend(iterable) 等。 和向量一样，双端队列可以按值、共享引用或可变引用进行迭代。

它们有 3 个迭 代器方法，即 .into_iter()、.iter() 和 .iter_mut()。

它们可以按通常 的方式通过索引来访问：deque[index]。 因为双端队列不会将自己的元素存储在连续的内存中，所以它们无法继承切片的 所有方法。但是，如果你愿意承受移动内容的开销，则可以通过 VecDeque 提供的如下方法来解决此问题。

deque.make_contiguous()（变连续） 　获取 &mut self 并将 VecDeque 重新排列到连续的内存中，返回 &mut [T]。

Vec 和 VecDeque 紧密相关，为了轻松地在两者之间进行转换，标准库提供了 两个特型实现。

• Vec::from(deque)（来自双端队列） 　Vec 实现了From<VecDeque<T>>，因此 Vec::from(deque) 能将 双端队列变成向量。这个操作的时间复杂度是 O(n)，因为可能要重新排列元 素。

• VecDeque::from(vec)（来自向量） 　VecDeque 实现了 From<Vec<T>>，因此 VecDeque::from(vec) 能把向量变成双端队列。这个操作的时间复杂度是 O(1)，因为 Rust 会直接把向量缓冲区转移给 VecDeque，而不会重新分配。 　这个方法使得创建具有指定元素的双端队列变得很容易，哪怕并没有标准的 vec_deque![] 宏。

  rust">use std::collections::VecDeque; 
  let v = VecDeque::from(vec![1, 2, 3, 4]);
  

BinaryHeap（二叉堆）

BinaryHeap（二叉堆）是一种元素组织会保持松散的集合，这样最大值便能总是冒泡到队列的首部。以下是 3 个最常用的 BinaryHeap 方法。

• heap.push(value)（压入） 　向堆中添加一个值。

• heap.pop()（弹出） 　从堆中移除并返回最大值。如果堆为空，则会返回一个为 None 的 Option<T>。

• heap.peek()（窥视） 　返回对堆中最大值的引用。返回类型是 Option<&T>。

• heap.peek_mut()（窥视，可变版）返回一个 PeekMut，它会返回对堆中最大值的可变引用，并提供类型 关联函数 pop() 以从堆中弹出该值。使用此方法，我们可以根据最大值来决定 是否将其从堆中弹出。

  rust">use std::collections::binary_heap::PeekMut;
  if let Some(top) = heap.peek_mut() {
   if *top > 10 {
   PeekMut::pop(top);
   }
  }
  

BinaryHeap 还支持 Vec 上的部分方法，包括 BinaryHeap::new()、.len()、.is_empty()、.capacity()、.clear () 和 .append(&mut heap2)。

rust">use std::collections::BinaryHeap;
let mut heap = BinaryHeap::from(vec![2, 3, 8, 6, 9, 5, 4]);

值 9 会位于堆顶：

rust">assert_eq!(heap.peek(), Some(&9));
assert_eq!(heap.pop(), Some(9));

移除了 9 之后也会稍微重新排列其他元素，以便让 8 位于最前面，以此类推

当然，BinaryHeap 并不局限于数值。它可以包含实现了内置特型 Ord 的任意 类型的值。 这使得 BinaryHeap 可用作工作队列。你可以定义一个基于优先级实现 Ord 的 任务结构体，以便高优先级任务比低优先级任务大一些。然后，创建一个 BinaryHeap 来保存所有待处理的任务。它的 .pop() 方法将始终返回最重要的条目，也就是你的程序下一步就应该处理的任务。

注意：BinaryHeap 是可迭代的，它有一个.iter()方法，但此迭代器会以任意顺序而不是从大到小生成堆的元素。要按优先顺序消耗 BinaryHeap 中的 值，使用 while 循环：

rust">while let Some(task) = heap.pop() {
 handle(task);
}

HashMap哈希Map & BTreeMapB树Map

Map 是键-值对［称为条目（entry）］的集合。

任何两个条目都不会有相同的 键，并且这些条目会始终按某种数据结构【B树】进行组织，从而使你可以通过键在 Map 中高效地查找对应的值。简而言之，Map 就是一个查找表。

Rust 提供了两种 Map 类型：HashMap<K,V> 和 BTreeMap<K,V>。这两种类型共享许多相同的方法，区别在于它们如何组织条目以便进行快速查找。

• HashMap 会将键和值存储在哈希表中，因此它需要一个实现了 Hash 和 Eq 的 键类型 K，即用来求哈希与判断相等性的标准库特型。所有 键、值和缓存的哈希码都存储在一个分配在堆上的表中。添加条目最终会迫使 HashMap 分配一个更大的表并将所有数据移入其中。

  

• BTreeMap 会在树结构中按键的顺序存储条目，因此它需要一个实现了 Ord 的 键类型 K。BTreeMap 中存储条目的单元称为节点。BTreeMap 中的大多数节点仅包含键值对。非叶节点中也有一些空间用于存储指向子节点的指针。(20, ‘q’) 和 (30, ‘r’) 之间的指针会指向包含 20 和 30 之间所有键的子节点。添加条目通常需要将节点的一些现有条目向右平移，以保持它们的顺序，并且偶尔需要创建新节点。 真正的 BTreeMap 节点会有 11 个条目的空间，而不是 4 个。

  

Rust 标准库采用了 B 树而不是平衡二叉树，因为 B 树在现代硬件上速度更快。 两相对比，二叉树固然在每次搜索时的比较次数较少，但 B 树具有更好的局部性（也就是说，内存访问被分组在一起，而不是分散在整个堆中）。这使得 CPU 缓存未命中的情况更为罕见。这会带来显著的速度提升。

创建 Map 的几种方法：

• HashMap::new()（新建）和 BTreeMap::new()（新建） 　创建新的空 Map。
• iter.collect()（收集） 　可用于从键-值对创建和填充新的 HashMap 或 BTreeMap。iter 必须是 Iterator 类型的。
• HashMap::with_capacity(n)（自带容量） 　创建一个新的空 HashMap，其中至少有 n 个条目的空间。与向量一样， HashMap 会将数据存储在分配在堆上的单块内存中，因此它们有容量及其相关 方法 hash_map.capacity()、hash_map.reserve(additional) 和 hash_map.shrink_to_fit()。BTreeMap 则没有这些。

处理键和值的核心方法：

• map.len()（长度） 　返回条目数。
• map.is_empty()（为空？） 　如果 map 没有条目，则返回 true。
• map.contains_key(&key)（包含 key？） 　如果 map 具有给定 key 的条目，则返回 true。
• map.get(&key)（按 key 获取） 　在 map 中搜索具有给定 key 的条目。如果找到匹配的条目，就返回 Some®，其中 r 是对相应值的引用。如果没找到，则返回 None。
• map.get_mut(&key)（按 key 获取，可变版） 　与 map.get(&key) 类似，但此方法会返回对值的可变引用。 　一般来说，Map 允许对其存储的值进行可变访问，但不允许对键进行可变访问。你可以随意修改这些值，但键属于 Map 本身，需要确保它们不会改变，因 为条目是根据对应的键来组织的。对键进行就地修改是错误的。
• map.insert(key, value)（插入） 　将条目 (key, value) 插入 map 并返回旧值（如果有的话）。返回类型 是 Option<T>。如果 Map 中已有 key 条目，则新插入的 value 会覆盖旧值。
• map.extend(iterable)（用 iterable 扩展） 　遍历 iterable 中的 (K, V) 项并将这些键和值逐个插入 map 中。
• map.append(&mut map2)（从 map2 追加） 　将所有条目从 map2 移动到 map 中。之后，map2 会变空。
• map.remove(&key)（按 key 移除值）　　从 map 中查找并移除具有给定 key 的任何条目，如果存在，就返回刚刚移 除的值。返回类型是 Option。
• map.remove_entry(&key)（按 key 移除条目） 　从 map 中查找并移除具有给定 key 的任何条目，返回刚刚移除的键和值 （如果有的话）。返回类型是 Option<(K, V)>。
• map.retain(test)（留下） 　移除所有未通过给定测试的元素。test 参数是实现了 FnMut(&K, &mut V) -> bool 的函数或闭包。对于 map 中的每个元素，都会调用 test(&key, &mut value)，如果此函数或闭包返回 false，则从 map 中移除并丢弃该元 素。 　除了性能上有些许区别，此方法类似于：map = map.into_iter().filter(test).collect();
• map.clear()（清空） 　移除所有条目。
• 使用方括号来查询 Map，比如 map[&key]。也就是说，Map 实现了内置特型 Index。但是，如果给定 key 还没有条目（就像越界数组访问），则会出 现 panic，因此只有在要查找的条目肯定已填充过时才应使用此语法。

.contains_key()、.get()、.get_mut() 和 .remove() 的 key 参数不必具有确切的类型 &K。这些方法对可以从 K 借用来的类型来说是通用的。

可以 在 HashMap<String,Fish> 上调用 fish_map.contains_key("conger")，即便 “conger” 不是确切的 String 类型也没问题，因为 String 实现了 Borrow<&str>[看做为]。

因为 BTreeMap 会始终保持其条目是根据键排序的，所以它支持一些额 外的操作：

btree_map.split_off(&key)（拆分出）　　把 btree_map 一分为二。将键小于 key 的条目留在 btree_map 中。返回包含其他条目的新 BTreeMap。

条目

Entry 类型是为 HashMap 专门定义的一个枚举（BTreeMap 也类似）：

rust">// (in std::collections::hash_map)
pub enum Entry<'a, K, V> {
 Occupied(OccupiedEntry<'a, K, V>),
 Vacant(VacantEntry<'a, K, V>)
}

OccupiedEntry 类型和 VacantEntry 类型都有一些无须重复查找即可插 入、移除和访问条目的方法。这些额外的方法 有时可用于消除一两次冗余查找，不过 .or_insert() 和 .or_insert_with() 已经涵盖了几种常见情况。

HashMap 和 BTreeMap 都有其对应的 Entry（条目）类型。条目的作用旨在 消除冗余的 Map 查找。

获取或创建学生记录：

rust">// 已经有关于此学生的记录了吗？
if !student_map.contains_key(name) {
 // 没有：创建一个
 student_map.insert(name.to_string(), Student::new());
}
// 现在，肯定存在一条记录了
let record = student_map.get_mut(name).unwrap();
...

会访问 student_map 两次或 3 次，每次都进行同样的查找。

对于这些条目，我们应该只进行一次查找，生成一个 Entry 值，然后将其用于 所有后续操作。

rust">let record = student_map.entry(name.to_string()).or_insert_with(Student::new);

student_map.entry(name.to_string()) 返回的 Entry 值是对 Map 中某个位置的可变引用，该位置要么由键-值对占用着，要么是空的（意味着那 里还没有条目）。如果为空，那么条目的 .or_insert_with() 方法就会插入 一个新的 Student。Entry 的大多数用法也是这样的：小而美。 所有 Entry 值都是由同一个方法创建的。 map.entry(key)（按 key 取条目） 　返回给定 key 的 Entry。如果 Map 中没有这样的键，则返回一个空的 Entry。 　此方法会通过可变引用获取其 self 参数并返回与其生命周期一致的 Entry：

rust">pub fn entry<'a>(&'a mut self, key: K) -> Entry<'a, K, V>

Entry 类型有一个生命周期参数 'a，因为它实际上是一种奇特的对 Map 的可变引用。只要 Entry 存在，它就拥有对此 Map 的独占访问权。

遗憾的是，如果 Map 具有 String 型的键，则无法将 &str 类型的引用传给此方法。在这种情况下，.entry() 方法需要一个真正的 String 型的值。 Entry 值提供了以下 3 个方法来处理空条目：

• map.entry(key).or_insert(value)（取条目或插入） 　确保 map 包含具有给定 key 的条目，如果需要，就插入具有给定 value 的新条目。此方法会返回对新值或现有值的可变引用。 　假设我们需要统计选票。可以这样写：

  rust">let mut vote_counts: HashMap<String, usize> = HashMap::new();
  for name in ballots {
   let count = vote_counts.entry(name).or_insert(0);
   *count += 1;
  }
  

  .or_insert() 会返回一个可变引用，所以 count 的类型是 &mut usize。

• map.entry(key).or_default()（取条目或插入默认值）确保 map 包含具有给定键的条目，如果需要，就插入一个具有 Default::default() 返回值的新条目。这仅适用于实现了 Default 的类 型。与 or_insert 类似，此方法会返回对新值或现有值的可变引用。

• map.entry(key).or_insert_with(default_fn)（取条目或借助 default_fn 插入） 　与前两个方法类似，不过当需要创建一个新条目时，此方法会调用 default_fn() 来生成默认值。如果 map 中已经有了 key 条目，则不会调用 default_fn。

哪些词出现在了哪些文件中：

rust">// 对于每个单词，这个`Map`包含一组曾出现过此单词的文件
let mut word_occurrence: HashMap<String, HashSet<String>> = HashMap::new();
for file in files {
 for word in read_words(file)? {
     let set = word_occurrence
     .entry(word)
     .or_insert_with(HashSet::new);
     set.insert(file.clone());
 }
}

仅修改现有字段的便捷方法:

map.entry(key).and_modify(closure)（取条目并修改） 　如果存在具有键 key 的条目，则调用 closure，并传入对该值的可变引用。此方法会返回 Entry，因此可以与其他方法做链式调用。

计算字符串中单词出现的次数

rust">// 这个`Map`包含给定字符串的所有单词以及单词的出现次数
let mut word_frequency: HashMap<&str, u32> = HashMap::new();
for c in text.split_whitespace() {
 word_frequency.entry(c)
 .and_modify(|count| *count += 1)
 .or_insert(1);
}

对 Map 进行迭代

• 按值迭代（for (k, v) in map）以生成 (K, V) 对。这会消耗 Map。
• 按共享引用迭代（for (k, v) in &map）以生成 (&K, &V) 对。
• 按可变引用迭代（for (k, v) in &mut map）以生成 (&K, &mut V) 对。（同样，无法对存储在 Map 中的键进行可变访问，因为这些条目是通 过它们的键进行组织的。）

与向量类似，Map 也有 .iter() 方法和 .iter_mut() 方法，它们会返回针对 “条目引用”的迭代器，可用来迭代 &map 或 &mut map。此外，还有以下迭代方 法。

• map.keys()（所有键的迭代器） 　返回只有“键引用”的迭代器。
• map.values()（所有值的迭代器） 　返回只有“值引用”的迭代器。
• map.values_mut()（所有值的可变迭代器） 　返回只有“值可变引用”的迭代器。
• map.into_iter()（转为迭代器）、map.into_keys()（转为键迭代 器）和 map.into_values()（转为值迭代器） 　消耗此 Map，分别返回遍历键值元组 (K, V)、键或值的迭代器。

所有 HashMap 迭代器都会以任意顺序访问 Map 的条目，而 BTreeMap 迭代器 会按 key 的顺序访问它们。

HashSet哈希Set & BTreeSetB树Set

Set 是用于快速进行元素存在性测试的集合：Set 中值都是单一的 不会重复。

Set 就像一个只有键（而非键-值 对）的 Map。事实上，Rust 的两个 Set 类型 HashSet 和 BTreeSet 都是通过对 HashMap 和 BTreeMap 的浅层包装实现的

• HashSet::new()（新建）和 BTreeSet::new()（新建） 　创建新 Set。
• iter.collect()（收集） 　可用于从任意迭代器创建出新 Set。如果 iter 多次生成了同一个值，则重 复项将被丢弃。
• HashSet::with_capacity(n)（自带容量） 　创建一个至少有 n 个值空间的空 HashSet。

HashSet 和 BTreeSet 有以下几个公共的基本方法：

• set.len()（长度） 　返回 set 中值的数量。
• set.is_empty()（为空？） 　如果 set 不包含任何元素，就返回 true。
• set.contains(&value)（包含） 　如果 set 包含给定 value，就返回 true。
• set.insert(value)（插入） 　向 set 中添加一个 value。如果新增了一个值，就返回 true；如果它先 前已是此 set 的成员，则返回 false。
• set.remove(&value)（移除） 　从 set 中移除一个 value。如果移除了一个值，就返回 true；如果它之 前不是此 set 的成员，则返回 false。
• set.retain(test)（留下） 　移除所有未通过给定测试的元素。test 参数是实现了 FnMut(&T) -> bool 的函数或闭包。对于 set 中的每个元素，此方法都会调用 test(&value)，如果它返回 false，则该元素将被从此 set 中移除并丢弃。 　除了性能上略有差异，类似于： set = set.into_iter().filter(test).collect();

与 Map 一样，通过引用查找值的方法对于可以从 T 借用来的类型都是通用的。

对 Set 进行迭代

• 按值迭代（for v in set）会生成 Set 的成员并消耗掉此 Set。
• 按共享引用（for v in &set）迭代会生成对 Set 成员的共享引用。

不支持通过可变引用迭代 Set。无法获取对存储在 Set 中的值的可变引用。

set.iter()（迭代器） 　返回 set 中成员引用的迭代器。

与 HashMap 迭代器类似，HashSet 迭代器会以任意顺序生成它们的值。 BTreeSet 迭代器会按顺序生成值，就像一个排好序的向量。

当相等的值不完全相同时

两个内容相同的 String 值会将它们的字符存 储在内存中的不同位置：

rust">let s1 = "hello".to_string();
let s2 = "hello".to_string();
println!("{:p}", &s1 as &str); // 0x7f8b32060008
println!("{:p}", &s2 as &str); // 0x7f8b32060010

如果 set 不包含匹配值，下面的每个方法都会返回一个为 None 的 Option。

• set.get(&value)（取值） 　返回对等于 value 的 set 成员的共享引用（如果有的话）。返回类型是 Option<&T>。
• set.take(&value)（拿出值） 　与 set.remove(&value) 类似，但此方法会返回所移除的值（如果有的 话）。返回类型是 Option<T>。
• set.replace(value)（替换为） 　与 set.insert(value) 类似，但如果 set 已经包含一个等于 value 的 值，那么此方法就会替代并返回原来的值。返回类型是 Option<T>。

针对整个 Set 的运算

• set1.intersection(&set2)（交集） 　返回同时出现在 set1 和 set2 中的值的迭代器。

  rust">for student in brain_class.intersection(&rocket_class) {
   println!("{}", student);
  }
  

  &set1 & &set2 会返回一个新 Set，该 Set 是 set1 和 set2 的交集。 这是把“二进制按位与”运算符应用在了两个引用之间。这样就会找到同时存在于 set1 和 set2 中的值。

• set1.union(&set2)（并集） 　返回存在于 set1 或 set2 中或者同时存在于两者中的值的迭代器。 　&set1 | &set2 会返回包含所有这些值的新 Set。它会找出所有存在于 set1 或 set2 中的值。

• set1.difference(&set2)（差集） 　返回存在于 set1 但不在于 set2 中的值的迭代器。 　&set1 - &set2 会返回包含所有此类值的新 Set。

• set1.symmetric_difference(&set2)（对称差集，异或） 　返回存在于 set1 或 set2 中但不同时存在于两者中的迭代器。 　&set1 ^ &set2 会返回包含所有此类值的新 Set。

以下是测试 Set 之间关系的 3 个方法：

• set1.is_disjoint(set2)（有交集？） 　如果 set1 和 set2 没有共同的值，就返回 true——它们之间的交集为 空。
• set1.is_subset(set2)（是子集？）　　如果 set1 是 set2 的子集，就返回 true。也就是说，set1 中的所有值 都在 set2 中。
• set1.is_superset(set2)（是超集？） 　与上一个方法相反：如果 set1 是 set2 的超集，就返回 true。
• Set 还支持使用 == 和 != 进行相等性测试。如果两个 Set 包含完全相同的一组值，那它们就是相等的。

哈希

std::hash::Hash 是可哈希类型的标准库特型。HashMap 的键和 HashSet 的元素都必须实现 Hash 和 Eq。

大多数实现了 Eq 的内置类型也会实现 Hash。整数、char 和 String 都是可哈希的。对元组、数组、切片和向量来说，只要它们的元素是可哈希的，它们自身就是可哈希的。 标准库的一个设计原则是，无论将值存储在何处或如何指向它，都应具有相同的哈希码。因此，引用与其引用的值具有相同的哈希码，而 Box 与其封装的值也 具有相同的哈希码。向量 vec 与包含其所有数据的切片 &vec[..] 具有相同的 哈希码。String 与具有相同字符的 &str 具有相同的哈希码。

默认情况下，结构体和枚举没有实现 Hash，但可以派生一个实现：

rust">/// 博物馆藏品中某件物品的ID号
#[derive(Clone, PartialEq, Eq, Hash)]
enum MuseumNumber {
 ...
}

只要此类型的字段都是可哈希的，就可以这样用。 如果为一个类型手动实现了 PartialEq，那么也应该手动实现 Hash。假设我 们有一个代表无价历史宝藏的类型：

rust">struct Artifact {
 id: MuseumNumber,
 name: String,
 cultures: Vec<Culture>,
 date: RoughTime, ...
}

如果两个 Artifact 具有相同的 ID，那么就认为它们是相等的：

rust">impl PartialEq for Artifact {
 fn eq(&self, other: &Artifact) -> bool {
 	self.id == other.id
 }
}
impl Eq for Artifact {}

由于我们仅是根据这些收藏品的 ID 来比较它们，因此也必须以相同的方式对这些收藏品进行哈希处理：

rust">use std::hash::{Hash, Hasher};
impl Hash for Artifact {
 fn hash<H: Hasher>(&self, hasher: &mut H) {
     // 把哈希工作委托给藏品编号
     self.id.hash(hasher);
 }
}

否则，HashSet 将无法正常工作。与所有哈希表一样，它要求 如果 a == b，则必然 hash(a) == hash(b)

完成上述工作 允许我们创建一个 Artifact 的 HashSet：

rust">let mut collection = HashSet::<Artifact>::new();

即使要手动实现 Hash，也不需要了解任何有关 哈希算法的知识。.hash() 会接收一个表示哈希算法的 Hasher 引用作为参 数。你只需将与 == 运算符相关的所有数据提供给这个 Hasher 即可。Hasher 会根据你提供的任何内容计算哈希码。

使用自定义哈希算法

hash 方法是泛型的

Rust 支持可替换哈希算法的方式。第三个特型 std::hash::BuildHasher 是表示哈希算法初始状态的类型的特型。每个 Hasher 都是单次使用的，就像迭代器一样：用过一次就扔掉了。而 BuildHasher 是可重用的。 每个 HashMap 都包含一个 BuildHasher，每次需要计算哈希码时都会用到。 BuildHasher 值包含哈希算法每次运行时所需的键、初始状态或其他参数。 计算哈希码的完整协议如下所示：

rust">use std::hash::{Hash, Hasher, BuildHasher};
fn compute_hash<B, T>(builder: &B, value: &T) -> u64
 where B: BuildHasher, T: Hash
{
 let mut hasher = builder.build_hasher(); // 1. 开始此算法
 value.hash(&mut hasher); // 2. 填入数据
 hasher.finish() // 3. 结束，生成u64
}

HashMap 每次需要计算哈希码时都会调用这 3 个方法。所有的方法都是可内联 的，所以速度非常快。

Rust 的默认哈希算法是著名的 SipHash-1-3 算法。SipHash 的速度很快，而且非常擅长减少哈希冲突。事实上，它也是一个加密算法：目前还没有已知的有效方法能刻意生成与 SipHash-1-3 冲突的值。只要每个哈希表使用不同且无法预测的 密钥，Rust 就可以安全地抵御一种称为 HashDoS 的拒绝服务攻击，在这种攻击 中，攻击者会故意使用哈希冲突来触发服务器的最坏性能。 不过，也许你的应用程序不需要此算法。如果要存储诸如整数或非常短的字符串之类的小型键，则可以实现更快的哈希函数，但代价是要牺牲 HashDoS 的安全性。fnv crate 实现了这样的一个算法，即 Fowler-Noll-Vo (FNV) 哈希。要尝试 此算法，请将如下依赖添加到你的 Cargo.toml 中：

[dependencies]
fnv = "1.0"

然后从 fnv 中导入 Map 类型和 Set 类型：

rust">use fnv::{FnvHashMap, FnvHashSet};

/// 使用默认FNV哈希器的`HashMap`
pub type FnvHashMap<K, V> = HashMap<K, V, FnvBuildHasher>;
/// 使用默认FNV哈希器的`HashSet`
pub type FnvHashSet<T> = HashSet<T, FnvBuildHasher>;

可以使用这两种类型作为 HashMap 和 HashSet 的无缝替代品。

自定义集合

在 Rust 中创建一个新的自定义集合类型和在其他语言中非常相似。通过组合语言提供的部件（结构体和枚举、标准集合、Option、Box 等）来组织数据。

如果你习惯于在 C++ 中实现数据结构，使用裸指针、手动内存管理、定位放置 （placement）new 和显式析构函数调用来获得最佳性能，那么你无疑会发现这 在安全的 Rust 中处处受限。所有这些工具本质上都是不安全的。可以在 Rust 中 使用它们，但前提是要使用不安全的代码【unsafe块】。

但这些标准集合的 API 让你尽可能少写unsafe代码。