VecDeque<T>Vec 可以实现在队列两端高效添加和移除元素。如果要把值保存在队列中间，Vec 的处理效率就相对较慢。
双端队列 std::collections::VecDeque<T>：实现了环形缓冲区，支持前端和后端的高效添加和移除操作。
deque.push_front(value)：在队列前面添加值。deque.push_back(value)：在队列后面添加值。deque.pop_front()：移除并返回队列前面的值，返回 Option<T>，队列为空时返回 None。deque.pop_back：移除并返回队列后面的值，返回 Option<T>，队列为空时返回 None。deque.front() 和 deque.back()：返回队列前端和后端元素的共享引用，返回 Option<T>，队列为空时返回 None。deque.front_mut() 和 deque.back_mut：返回队列前端和后端元素的可修改引用引用，返回 Option<&mut T>。队列在内存中不是连续存储的，并没有继承切片的所有方法。如果要在队列数据上执行向量和切片的操作，需要把 VecDeque 转换为 Vec，执行完操作后，再转换回去。
Vec<T> 实现了 From<VecDeque<T>>，因此 Vec::from(deque) 可以将队列转换为向量。
VecDeque<T> 实现了 From<Vec<T>>，因此 VecDeque::from(vec) 可以将向量转换为队列。
// 通过指定元素来创建队列的方法
use std::collections::VecDeque;
let v = VecDeque::from(vec![1, 2, 3, 4]);
LinkedList<T>链表的每个值都存储在独立的堆内存中，是一种存储序列值的方式。
std::collections::LinkedList<T> 是双向链表
支持
VecDeque
的部分方法：
LinkedList::new() 等支持把两个列表非常快速地组合到一起：list1.append(&mut list2)，把 list2 中的元素都转移到 list1 中。vec 和 VecDeque 也支持 append 方法，但是会把很多值从一个堆阵列转移到另一个。
BinaryHeap<T>BinaryHeap<T> 用于存储松散元素，最大值始终会冒泡到队列前端。
常用的方法：
heap.push(value)：向堆中添加值。heap.pop()：从堆中移除并返回最大值。返回类型为 Option<T>，如果堆为空则返回 None。heap.peek()：返回堆中最大值的引用。返回类型为 Option<&T>。也支持 Vec 的部分方法：
BinaryHeap::new()；heap.len()；heap.is_empty()；heap.capacity()；heap.clear()；heap.append(&mut heap2)。实现了内置特型 Ord 的任何类型，都可以保存在 BinaryHeap 中。
常用于制作工作队列：
定义一个任务结构体，基于优先级实现 Ord，让高优先级任务大于低优先级任务。然后，创建一个 BinaryHeap 保存所有带完成的任务。可以调用.pop() 方法始终返回接下来要做的最重要的任务。
可以使用 while 循环消费：
while let Some(task) = heap.pop() {
handle(task);
}
BinaryHeap 是可迭代类型，也有自己的.iter() 方法，迭代器的顺序是任意的。
HashMap<K, V> 和 BTreeMap<K, V>映射（map）是一种键 — 值对（称为条目）集合。
HashMap<K, V> 把键和值保存在一个分配在堆上的散列表里，因此要求键的类型 K 实现标准的散列和相等性特型 Hash 和 Eq。
BTreeMap<K, V> 按照键的顺序存储条目，总体为树形结构，因此要求键的类型 K 实现 Ord。
Rust 的标准库使用 B 树，而不是平衡二叉树。二叉树每次搜索所必须的次数，比 B 树少；但搜索 B 树的领域性（locality）更好。B 树可以使得内存访问的集合在一起，而不是分散到整个堆上。这样 CPU 缓存就很少错失，从而显著提高速度。
创建映射的方法：
HashMap::new() 和 BTreeMap::new() 创建新的空映射；iter.collect()：用于从键 — 值对创建和填充新的 HashMap 或 BTreeMap。iter 必须是一个 Iterator<Item=(K, V)> 的迭代器。HashMap::with_capacity(n)：可以创建新的空散列表，至少能容纳 n 个条目。HashMap 单独支持容量相关的方法：hash_map.capacity()、hash_map.reserve(additional) 和 hash_map.shrink_to_fit()。HashMap
和
BTreeMap
共同支持以下核心方法：
map.len()：返回条目数量。map.is_empty()：在 map 没有条目时返回 true。map.contains_key(&key)：在映射又条目的键为 key 时返回 true。map.get(&key)：搜索 map 中具有给定 key 的条目。如果找到匹配的条目，返回 Some(r)，其中 r 是相对应的引用。否则返回 None。map.get_mut(&key)：功能与上同，但是返回对值的可修改引用。对于值可以随意修改，但键鼠鱼映射本身，不能修改。map.insert(key, value)：向 map 中插入条目 (key, value)。如果映射中已经存在为 key 的条目，则会插入新的值 value，覆盖原来的值。如果覆盖了原来的值，会返回原来的值，返回类型为 Option<V>。map.extend(iterable)：迭代 iterable 的 (K, V) 条目，并将每个键 — 值对插入 map 中。map.append(&mut map2)：将 map2 的所有条目转移到 map 中，map2 会变为空。map.remove(&key)：查找并移除 map 中键为 key 的条目。如果有值被移除，则返回移除的值。返回类型为 Option<V>。map.clear()：移除所有条目。map[&key]：用方括号语法查询映射。如果不存在为 key 的条目，则会诧异，类似数组访问越界。BTreeMap<K, V>
因为可以按键排序并存储条目，还支持
btree_map.split_off(key)
：
btree_map 一分为二；key 的条目会留在 btree_map 中。BTreeMap<K, V> 包含其他条目。Entry 条目类型：用于消除多余的映射查找。
let record = student_map.entry(name.to_string()).or_insert_with(Student);
student_map.entry(name.to_string) 返回的 Entry 值类似于指向映射中某个位置的可修改引用；
如果引用为空，则.or_insert_with() 方法会插入一个新的 Student。
Entry 是一个枚举类型：
// std::collections::hash_map
pub enum Entry<'a, K: 'a, V: 'a> {
Occupied(OccupiedEntry<'a, K, V>),
Vacant(VacantEntry<'a, K, V>)
}
创建 Entry 值的方法：map.entry(key)。
返回键为 key 的 Entry。
如果映射中没有，则返回一个空的 Entry。
接收自己的可修改引用，返回生命期匹配的 Entry：
pub fn entry<'a>(&'a mut self, key: K) -> Entry<'a, K, V>
如果映射的键是 String 类型，则不能给这个方法传入 &str 类型的引用。此时要给.entry() 方法传入真正的 String。
填充空条目的方法：
map.entry(key).or_insert(value)：必须保证 map 包含键为 key 的条目，必要时会给定默认 value 插入新条目。返回对新的或已有值的可修改引用。
// 举例：计算投票数
let mut vote_counts: HashMap<String, usize> = HashMap::new();
for name in ballots {
let count = vote_counts.entry(name).or_insert(0);
*count += 1; // count的类型为&mut usize。
}
map.entry(key).or_insert_with(default_fn)：功能与上同，但是在需要创建新条目时会调用 default_fn() 函数，以产生默认值。如果 map 中已经存在了为 key 的条目，则不会用到 default_fn()。
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());
}
}
HashMap 迭代器支持以任意顺序访问映射的条目；BTreeMap 迭代器，必须按键顺序访问条目。for (k, v) in map）：产生 (K, V) 对。这样会消费映射。for (k, v) in &map）：产生 (&K, &V) 对。for (k, v) in &mut map）：产生 (&K, &mut v) 对。.iter() 和.iter_mut()：返回迭代器且产生值引用的方法；map.keys()：返回产生键引用的迭代器。map.values()：返回产生值引用的迭代器。map.values_mut()：返回产生可修改值引用的迭代器。HashSet<T> 和 BTreeSet<T>Set 集：支持快速测试成员关系而组织值。集中永远不会包含同一个值的多个副本。
let b1 = large_vector.contains("needle"); // 在向量中查找元素比较慢，需要检查每个元素
let b2 = large_hash_set.contains("needle"); // 在集中查找元素比较快，支持散列查找
集类似于只有键的映射。HashSet<T> 和 BTreeSet<T> 都是以的包装类型形式实现的：
HashSet::new() 和 BTreeSet::new() 创建新集。iter.collect() 可用于从任何迭代器创建新集。如果产生了重复值，则重复的值会被清除。HashSet::with_capacity(n) 创建空的 HashSet，至少容纳 n 个值。HashSet<T> 和 BTreeSet<T> 共有的方法：
set.len()：返回 set 中值的数量。set.is_empty()：在集中不包含元素值返回 true。set.contains(&value)：在集中包含给定值 value 时返回 true。set.insert(value)：向集中添加 value。如果添加成功就返回 true，如果集里面已经存在同样的值就返回 false。set.remove(&value)：从集里面移除 value。如果移除成功就返回 true。如果没有这个值，则返回 false。与映射类似，按引用查询值的方法也是通用的，只要可以从 T 借用到该类型。
for v in set 产生集的成员，并且消费集。for v in &set 产生集成员的共享引用。set.iter() 返回迭代器，产生 set 成员的引用。HashSet 迭代器支持以任意顺序访问映射的条目；BTreeSet 迭代器，必须按键顺序访问条目。取得存储在集中的实际值的方法：这些方法都返回 Option，如果 set 不包含匹配的值，则返回 None。
set.get(&value)：返回 set 中等于 value 的成员的共享引用，返回类型是 Option<&T>。set.take(&value)：类似于 set.remove(&value)，但返回移除的值，返回类型是 Option<T>。set.replace(value)：类似于 set.insert(value)，但如果 set 中已经包含等于 value 的值，那么就返回原来的值。返回类型是 Option<T>set1.intersection(&set2)：返回同时包含在 set1 和 set2 中的所有值的迭代器。&set1 & &set2：返回 set1 和 set2 的交集。set1.union(&set2)：返回同时包含在 set1 和 set2 种，或只在 set1 或 set2 的值的迭代器。&set1 | &set2：返回包含这两个集中所有值的新集。set1.difference(&set2)：返回包含在 set1 但不包含在 set2 中的值的迭代器。&set1 - &set2：返回包含在 set1 但不包含在 set2 的所有这些值的新集。set1.symmetric_difference(&set2)：返回只包含在 set1 中，或只包含在 set2 中，但不同时包含在两个集中的值的迭代器。&set1 ^ &set2：返回只包含在 set1 中，或只包含在 set2 中，但不同时包含在两个集中的值的新集。set1.is_disjoint(set2)：如果交集为空，则返回 true。set1.is_subset(set2)：如果 set1 是 set2 的子集，则返回 true。set1.is_superset(set2)：如果 set1 是 set2 的超集，则返回 true。== 和 != 的相等性测试：两个集包相同的值，那么它们相等。std::hash::Hash 是标准库中可散列类型的特型。
一个值无论保存在哪里，或者怎么指向它，都应该有相同的散列码。
Box 与装箱的值有相同的散列码；vec 与包含所有其数据的切片 &ved[..] 有相同的散列码；String 与引用相同字符的 &str 有相同的散列码。结构体和枚举默认没有实现 Hash，但可以派生一个实现：
#[derive(Clone, PartialEq, Eq, Hash)]
enum MN {
...
}
如果手工为一个类型实现了 PartialEq，那么必须为它实现 Hash。
hash 方法是泛型的。
计算散列码的完整协议：
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(); // 算法开始
value.hash(&mut hasher); // 传入数据
hasher.finish() // 算法完成，产生u64值。
}
Rust 默认使用 SipHash-1-3 算法作为散列算法。只要有不同之处，每个散列表就会使用无法预测的键。因此可以防止 HashDoS 的拒绝服务攻击，即攻击者故意使用散列冲突来出发服务器中最差的性能。
如果为了想要更快的散列实现，而牺牲安全性，那么可以使用 fnv 包实现的 Fowler-Noll-Vo 散列算法。
// 在Cargo.toml中添加：
[dependencies]
fnv = "1.0"
// 导入映射和散列类型
extern crate fnv;
use fnv::{FnvHashMap, FnvHashSet}; // 代替HashMap和HashSet。
Rust 支持在 unsafe 块中实现 C++ 的数据结构：原始指针、手工内存管理、放置 new、显示调用析构函数。
详见《Rust 程序设计》（吉姆 - 布兰迪、贾森 - 奥伦多夫著，李松峰译）第十六章
原文地址