Rust 笔记Rust 语言中映射（HashMap）与集合（HashSet）及其用法
1. 概述
1.1 什么是哈希表
哈希表（Hash Table），也被称为 散列表，是一种数据结构，它提供了快速插入、删除和查找操作的能力。在计算机科学中，哈希表是非常重要的，因为它们可以在平均情况下实现 O(1) 的时间复杂度，这使得它们在许多场景中都非常有用，例如数据库、编译器和缓存系统。
哈希表的基本原理是将键（Key）通过哈希函数（Hash Function）映射到一个数组中的位置（也称为“桶”），然后将值（Value）存储在该位置。当需要查找某个键对应的值时，只需再次应用哈希函数，找到对应的位置，即可快速获取值。
1.2 Rust 语言中的哈希表
哈希映射（HashMap）和 哈希集（HashSet）是Rust 标准库提供的两种基于哈希表的数据结构，以下我们用 Map 和 Set 简称它们，并做以比较：
| 项目 | 描述 |
| 元素存储方面 | 哈希映射 （Map）是一种键值对（key-value）的集合，每个元素由一个唯一的键和对应的值组成。键用于唯一标识元素，值表示与键关联的数据。哈希集是一种唯一元素的集合，其中每个元素都是唯一的，没有键值对的概念。 |
| 数据访问方面 | 哈希映射（Map）中，可以通过键来访问和操作与之关联的值，因为每个键都是唯一的。 而 哈希集 （Set）中，只能访问集合中的元素本身，没有与之关联的值。 |
| API功能方面 | 哈希映射（Map）额外提供了根据键来进行操作的方法，如根据键获取对应的值、根据键删除元素等。 而 哈希集（Set）主要关注集合的元素操作，如插入元素、删除元素、判断元素是否存在等。 |
| 用途方面 | 哈希映射（Map）提供了键值对的存储方式，常用于需要根据键快速查找和操作值的场景。例如，可以使用哈希映射实现字典、缓存等数据结构。 哈希集（Set）则常用于需要存储唯一元素的场景，可以快速判断元素是否存在于集合中。 |
虽然哈希映射和哈希集在某些方面有所不同，但它们都基于哈希表实现，具有快速的插入、删除和查找操作。在使用时，根据需求选择适合的数据结构，可以充分利用哈希表的高效性能。
2. Rust HashMap 用法
HashMap 的官方文档地址为：https://doc.rust-lang.org/std/collections/struct.HashMap.htm
文本未能讲解到的，可以参考官方文档了解更多技术细节。
2.1 HashMap的 创建和初始化
在使用哈希表之前，需要创建并初始化一个空的哈希表对象。Rust 提供了HashMap类型来表示哈希表，并且可以使用 HashMap::new() 方法创建一个新的空哈希表。
例如：
use std::collections::HashMap; fn main() { // 创建一个新的空哈希表 let mut hashmap: HashMap<KeyType, ValueType> = HashMap::new(); }
2.2 HashMap的 插入和更新
2.2.1 insert
该方法用于向HashMap中插入键值对。如果键已经存在，则会替换对应的值。
其语法格式为：
fn insert(&mut self, key: K, value: V) -> Option<V>`
其中参数：
key：要插入的键value：要插入的值
返回被替换的值（如果存在）或者None
例如：
use std::collections::HashMap; let mut map: HashMap<u32, &str> = HashMap::new(); map.insert(1, "apple"); map.insert(2, "banana");
2.2.2 try_insert
该方法尝试向HashMap中插入键值对。如果键已经存在，则返回错误。
其语法格式为：
fn try_insert(&mut self, key: K, value: V) -> Result<Option<V>, InsertError>
其中参数：
key：要插入的键value：要插入的值
返回被替换的值（如果存在）或者返回InsertError错误
例如：
use std::collections::HashMap; let mut map: HashMap<u32, &str> = HashMap::new(); map.try_insert(1, "apple").unwrap(); map.try_insert(1, "banana").unwrap_err();
2.2.3 remove
该方法用于从HashMap中移除指定键的键值对，并返回被移除的值。
其语法格式为：
fn remove(&mut self, key: &K) -> Option<V>`
其中参数：
key：要移除的键的引用
返回被移除的值（如果存在）或者 None。
例如：
use std::collections::HashMap; let mut map: HashMap<u32, &str> = HashMap::new(); map.insert(1, "apple"); map.insert(2, "banana"); let removed_value = map.remove(&1);
2.2.4 remove_entry
该方法用于从HashMap中移除指定键的键值对，并返回被移除的键值对。其语法格式为：
fn remove_entry(&mut self, key: &K) -> Option<(K, V)>`
其中参数：
key：要移除的键的引用
返回被移除的键值对（如果存在）或者 None。
例如：
use std::collections::HashMap; let mut map: HashMap<u32, &str> = HashMap::new(); map.insert(1, "apple"); map.insert(2, "banana"); let removed_entry = map.remove_entry(&1);
2.2.5 retain
该方法根据指定的闭包条件，从HashMap中保留满足条件的键值对，移除不满足条件的键值对。其语法格式为：
fn retain<F>(&mut self, f: F) where F: FnMut(&K, &mut V) -> bool
其中参数：
f: 用于判断保留条件的闭包函数
例如：
use std::collections::HashMap; let mut map: HashMap<u32, &str> = HashMap::new(); map.insert(1, "apple"); map.insert(2, "banana"); map.insert(3, "cherry"); map.retain(|key, value| *key % 2 == 0);
2.3 HashMap 容量 相关的API
2.3.1 capacity
该方法用于获取HashMap当前能够容纳的元素数量，即内部桶的数量。其语法格式为：
fn capacity(&self) -> usize
返回当前 HashMap 内部桶的数量。
例如：
use std::collections::HashMap; let map: HashMap<u32, u32> = HashMap::new(); println!("Initial capacity: {}", map.capacity()); let mut map: HashMap<u32, u32> = HashMap::with_capacity(10); println!("New capacity: {}", map.capacity());
2.3.2 reserve
该方法用于为HashMap预分配内部桶的数量，以便容纳更多的元素。其语法格式为：
fn reserve(&mut self, additional: usize)
其中参数：
- additional - 需要额外预留的元素数量
例如：
use std::collections::HashMap; let mut map: HashMap<u32, u32> = HashMap::new(); map.reserve(100);
2.3.2 shrink_to
该方法将HashMap的内部桶数量缩减为最小，以节省内存空间。
其语法格式为：
fn shrink_to(&mut self, min_capacity: usize)`
其中参数：
- min_capacity - 希望HashMap缩减到的最小内部桶数量
例如：
use std::collections::HashMap; let mut map: HashMap<u32, u32> = HashMap::with_capacity(100); map.insert(1, 1); map.insert(2, 2); map.shrink_to(10);
2.3.4 shrink_to_fit
该方法将HashMap的内部桶数量缩减为当前元素数量所需的最小值，以节省内存空间。其语法格式为：
fn shrink_to_fit(&mut self)`
例如：
use std::collections::HashMap; let mut map: HashMap<u32, u32> = HashMap::with_capacity(100); map.insert(1, 1); map.insert(2, 2); map.shrink_to_fit();
2.3.5 with_capacity
该方法用于创建一个具有指定初始容量的HashMap。其语法格式为：
fn with_capacity(capacity: usize) -> HashMap<K, V>`
其中参数：
- capacity - 初始容量
返回具有指定初始容量的HashMap实例。
例如：
use std::collections::HashMap; let map: HashMap<u32, u32> = HashMap::with_capacity(100);
2.3.6 with_capacity_and_hasher
该方法用于创建一个具有指定初始容量和哈希函数的HashMap。其语法格式为：
fn with_capacity_and_hasher(capacity: usize, hasher: S) -> HashMap<K, V, S>`
其中参数：
- capacity - 初始容量
- hasher - 哈希函数实例
返回值具有指定初始容量和哈希函数的HashMap实例
例如：
use std::collections::HashMap; use std::hash::BuildHasherDefault; #[derive(Default)] struct CustomHasher; type CustomHashMap<K, V> = HashMap<K, V, BuildHasherDefault<CustomHasher>>; let map: CustomHashMap<u32, u32> = CustomHashMap::with_capacity_and_hasher(100, Default::default());
2.4 HashMap的 清空与判空
2.4.1 clear
该方法用于清空HashMap，移除所有的键值对。其语法格式为：
fn clear(&mut self)
例如：
use std::collections::HashMap; let mut map: HashMap<u32, &str> = HashMap::new(); map.insert(1, "apple"); map.insert(2, "banana"); map.clear();
2.4.2 is_empty
该方法用于判断 HashMap 是否为空，即是否没有任何键值对。其语法格式为：
fn is_empty(&self) -> bool`
返回一个bool值，表示 HashMap 是否为空。如果为空，则返回 true，否则返回 false。
例如：
use std::collections::HashMap; let mut map: HashMap<u32, &str> = HashMap::new(); assert!(map.is_empty()); map.insert(1, "apple"); assert!(!map.is_empty());
2.5 哈希表内容的查询和获取
2.5.1 insert
该方法用于向 HashMap** 中插入一个键值对。如果键已经存在，则会覆盖原有的值，并返回旧值；如果键不存在，则插入新的键值对，并返回 None。其语法格式为：
fn insert(&mut self, key: K, value: V) -> Option<V>
其中参数：
- key: 插入的键，类型为K。
- value: 插入的值，类型为V。
如果键已存在，则返回 Some (旧值)，否则返回 None。
例如：
use std::collections::HashMap; let mut map: HashMap<u32, &str> = HashMap::new(); map.insert(1, "apple"); // 插入新的键值对 let old_value = map.insert(1, "orange"); // 键已存在，覆盖原有的值 assert_eq!(old_value, Some("apple"));
2.5.2 try_insert
该方法用于尝试向HashMap中插入一个键值对。如果键已经存在，则返回错误；如果键不存在，则插入新的键值对，并返回Ok(())。
其语法格式为：
fn try_insert(&mut self, key: K, value: V) -> Result<(), V>
其中参数：
- key: 插入的键，类型为K。
- value: 插入的值，类型为V。
如果键已存在，则返回 Err(值)，否则返回Ok(())。
例如：
use std::collections::HashMap; let mut map: HashMap<u32, &str> = HashMap::new(); map.try_insert(1, "apple").unwrap(); // 插入新的键值对 let result = map.try_insert(1, "orange"); // 键已存在，返回错误 assert_eq!(result, Err("orange"));
2.5.3 remove
该方法用于从HashMap中移除指定键的键值对，并返回被移除的值。其语法格式为：
fn remove(&mut self, key: &K) -> Option<V>
其中参数：
- key: 要移除的键的引用，类型为 &K。
如果键存在，则返回 Some(被移除的值)，否则返回 None。
例如：
use std::collections::HashMap; let mut map: HashMap<u32, &str> = HashMap::new(); map.insert(1, "apple"); let removed_value = map.remove(&1); // 移除键为1的键值对 assert_eq!(removed_value, Some("apple"));
2.5.4 remove_entry
该方法用于从HashMap中移除指定键的键值对，并返回被移除的键值对。
其语法格式为：
fn remove_entry(&mut self, key: &K) -> Option<(K, V)>`
其中参数：
- key: 要移除的键的引用，类型为&K。
如果键存在，则返回 Some((被移除的键, 被移除的值))，否则返回 None。
例如：
use std::collections::HashMap; let mut map: HashMap<u32, &str> = HashMap::new(); map.insert(1, "apple"); let removed_entry = map.remove_entry(&1); // 移除键为1的键值对 assert_eq!(removed_entry, Some((1, "apple")));
2.5.5 retain
该方法用于保留满足指定条件的键值对，移除不满足条件的键值对。
其语法格式为：
fn retain<F>(&mut self, f: F) where F: FnMut(&K, &mut V) -> bool
其中参数：
f: 一个闭包函数，接受当前键和值的引用，并返回一个bool值，用于判断键值对是否要保留。
例如：
use std::collections::HashMap; let mut map: HashMap<u32, &str> = HashMap::new(); map.insert(1, "apple"); map.insert(2, "banana"); map.insert(3, "orange"); map.retain(|key, value| key % 2 == 0); // 保留键为偶数的键值对，移除键为奇数的键值对 assert_eq!(map.len(), 1); assert_eq!(map.get(&2), Some(&"banana"));
2.6 哈希表的遍历和迭代
2.6.1 iter
该方法用于返回一个HashMap的不可变迭代器，遍历HashMap中的所有键值对。
其语法格式为：
fn iter(&self) -> Iter<'_, K, V>
返回一个Iter迭代器，用于按顺序遍历HashMap中的键值对。
例如：
use std::collections::HashMap; let mut map: HashMap<u32, &str> = HashMap::new(); map.insert(1, "apple"); map.insert(2, "banana"); map.insert(3, "orange"); for (key, value) in map.iter() { println!("Key: {}, Value: {}", key, value); }
2.6.2 iter_mut
该方法用于返回一个HashMap的可变迭代器，遍历HashMap中的所有键值对，可以修改值。
其语法格式为：
fn iter_mut(&mut self) -> IterMut<'_, K, V>
返回一个IterMut迭代器，用于按顺序遍历HashMap中的键值对，并允许修改值。
例如：
use std::collections::HashMap; let mut map: HashMap<u32, &str> = HashMap::new(); map.insert(1, "apple"); map.insert(2, "banana"); map.insert(3, "orange"); for (_, value) in map.iter_mut() { *value = "fruit"; // 修改值为"fruit" } for (key, value) in map.iter() { println!("Key: {}, Value: {}", key, value); }
2.6.3 drain
该方法用于创建一个从HashMap中移除所有键值对的迭代器，该迭代器将所有的键值对逐个返回。其语法格式为：
fn drain(&mut self) -> Drain<'_, K, V>
返回值一个Drain迭代器，用于按顺序遍历并移除HashMap中的键值对。
例如：
use std::collections::HashMap; let mut map: HashMap<u32, &str> = HashMap::new(); map.insert(1, "apple"); map.insert(2, "banana"); map.insert(3, "orange"); let drained: Vec<(u32, &str)> = map.drain().collect(); for (key, value) in drained { println!("Key: {}, Value: {}", key, value); }
2.6.4 drain_filter
这个方法在目前的Rust中不稳定。
This is a nightly-only experimental API. (hash_drain_filter #59618)
该方法用于创建一个从HashMap中移除满足指定条件的键值对的迭代器。其语法格式为：
fn drain_filter<P>(&mut self, pred: P) -> DrainFilter<'_, K, V, P>` where P: FnMut(&K, &mut V) -> bool
其中参数：
pred: 一个闭包函数，接受当前键和值的引用，并
返回一个bool值，用于判断键值对是否要移除。
返回一个DrainFilter迭代器，用于按顺序遍历并移除满足条件的键值对。
例如：
use std::collections::HashMap; let mut map: HashMap<u32, &str> = HashMap::new(); map.insert(1, "apple"); map.insert(2, "banana"); map.insert(3, "orange"); let drained: Vec<(u32, &str)> = map.drain_filter(|key, _| key % 2 == 0).collect(); for (key, value) in drained { println!("Key: {}, Value: {}", key, value); }
这里由于是 nightly-only experimental API 无法直接使用，可以通过 retain 等其它方法来实现类似的功能，例如：
use std::collections::HashMap; fn main() { let mut map: HashMap<u32, &str> = HashMap::new(); map.insert(1, "apple"); map.insert(2, "banana"); map.insert(3, "orange"); let mut drained: Vec<(u32, &str)> = Vec::new(); map.retain(|key, value| { if key % 2 == 0 { drained.push((*key, *value)); false } else { true } }); for (key, value) in drained { println!("Key: {}, Value: {}", key, value); } }
输出结果为：
Key: 2, Value: banana
2.6.5 raw_entry
该方法用于返回一个RawEntryBuilder实例，提供对HashMap中键值对的低级别操作。其语法格式为：
fn raw_entry(&self) -> RawEntryBuilder<'_, K, V, S>
返回一个 RawEntryBuilder 实例，用于对HashMap中的键值对进行低级别操作。
例如：
use std::collections::HashMap; use std::collections::hash_map::RawEntryBuilder; let mut map: HashMap<u32, &str> = HashMap::new(); map.insert(1, "apple"); map.insert(2, "banana"); map.insert(3, "orange"); let raw_entry = map.raw_entry(); // 在低级别上操作HashMap中的键值对 // ... // 示例：查找键为1的键值对并进行操作 match raw_entry.from_key(&1) { RawEntryBuilder::Vacant(entry) => { // 键不存在的处理逻辑 } RawEntryBuilder::Occupied(entry) => { // 键存在的处理逻辑 } }
3. Rust HashSet 用法
HashSet 的官方文档地址为：https://doc.rust-lang.org/std/collections/struct.HashSet.htm
文本未能讲解到的，可以参考官方文档了解更多技术细节。
3.1 创建和初始化
在Rust中，我们可以使用HashSet类型来创建和初始化哈希集。HashSet是一个存储唯一值的集合，它基于哈希表实现，提供高效的插入、删除和查找操作。
3.1.1 new
new方法用于创建一个空的HashSet。其语法格式如下：
fn new() -> HashSet<T, S>
该方法不接受任何参数，返回一个新的空HashSet实例。
示例：
use std::collections::HashSet; let set: HashSet<u32> = HashSet::new();
3.1.2 with_capacity
with_capacity方法用于创建一个具有指定初始容量的HashSet。其语法格式如下：
fn with_capacity(capacity: usize) -> HashSet<T, S>
该方法接受一个capacity参数，表示期望的初始容量。返回一个具有指定容量的新的HashSet实例。
示例：
use std::collections::HashSet; let set: HashSet<u32> = HashSet::with_capacity(10);
3.1.3 with_capacity_and_hasher
with_capacity_and_hasher方法用于创建一个具有指定初始容量和哈希函数的HashSet。其语法格式如下：
fn with_capacity_and_hasher(capacity: usize, hasher: S) -> HashSet<T, S>
该方法接受一个capacity参数表示期望的初始容量，以及一个hasher参数表示用于计算哈希值的哈希函数。返回一个具有指定容量和哈希函数的新的HashSet实例。
示例：
use std::collections::HashSet; use std::hash::BuildHasherDefault; let hasher = BuildHasherDefault::<MyHasher>::default(); let set: HashSet<u32, _> = HashSet::with_capacity_and_hasher(10, hasher);
3.1.4 with_hasher
with_hasher方法用于创建一个具有指定哈希函数的HashSet，并使用默认的初始容量。其语法格式如下：
fn with_hasher(hasher: S) -> HashSet<T, S>
该方法接受一个hasher参数表示用于计算哈希值的哈希函数。返回一个具有指定哈希函数的新的HashSet实例。
示例：
use std::collections::HashSet; use std::hash::BuildHasherDefault; let hasher = BuildHasherDefault::<MyHasher>::default(); let set: HashSet<u32, _> = HashSet::with_hasher(hasher);
以上是关于创建和初始化HashSet的几种常用方法和示例。根据实际需求，可以选择合适的方法来创建和初始化哈希集。
3.2 添加和删除元素
在Rust中，HashSet提供了一系列方法用于添加和删除元素。下面介绍了常用的方法及其用法。
3.2.1 insert
insert方法用于向HashSet中插入一个元素。如果元素已经存在，则插入操作将被忽略。
其语法格式如下：
fn insert(&mut self, value: T) -> bool
其中参数value表示要插入的元素，返回值为bool类型，表示插入操作是否成功（即元素是否已存在）。
示例：
use std::collections::HashSet; let mut set: HashSet<u32> = HashSet::new(); assert!(set.insert(1)); // 插入元素1 assert!(set.insert(2)); // 插入元素2 assert!(!set.insert(1)); // 元素1已存在，插入失败
3.2.2 remove
remove方法用于从HashSet中移除指定的元素。如果元素存在，则将其从集合中删除，并返回true；如果元素不存在，则返回false。
其语法格式如下：
fn remove(&mut self, value: &T) -> bool
其中参数value表示要移除的元素的引用，返回值为bool类型，表示移除操作是否成功（即元素是否存在）。
示例：
use std::collections::HashSet; let mut set: HashSet<u32> = HashSet::new(); set.insert(1); set.insert(2); assert!(set.remove(&1)); // 移除元素1 assert!(!set.remove(&3)); // 元素3不存在，移除失败
3.2.3 replace
replace方法用于替换HashSet中指定元素的值，并返回被替换的值。如果元素存在，则进行替换操作；如果元素不存在，则插入新的键值对。
其语法格式如下：
fn replace(&mut self, value: T) -> Option<T>
其中参数value表示要插入或替换的元素，返回值为Option<T>类型，表示被替换的值（如果存在）或None（如果元素不存在）。
示例：
use std::collections::HashSet; let mut set: HashSet<u32> = HashSet::new(); set.insert(1); let replaced_value = set.replace(2); // 替换元素1为2 assert_eq!(replaced_value, Some(1)); let new_replaced_value = set.replace(3); // 插入元素3 assert_eq!(new_replaced_value, None);
3.2.4 get_or_insert
get_or_insert方法用于获取HashSet中指定元素的引用，如果元素存在，则返回其引用；如果元素不存在，则插入新的键值对，并返回新插入元素的可变引用。
其语法格式如下：
fn get_or_insert(&mut self, value: T) -> &mut T
其中参数value表示要获取或插入的元素，返回值为&mut T类型，表示获取或插入元素的可变引用。
示例：
use std::collections::HashSet; let mut set: HashSet<u32> = HashSet::new(); let value = set.get_or_insert(1); // 获取或插入元素1 assert_eq!(*value, 1); *value = 2; // 修改插入的元素的值 assert_eq!(*value, 2);
3.2.5 get_or_insert_owned
get_or_insert_owned方法用于获取HashSet中指定元素的值的所有权，如果元素存在，则返回其值的所有权；如果元素不存在，则插入新的键值对，并返回新插入元素的值的所有权。
其语法格式如下：
fn get_or_insert_owned(&mut self, value: T) -> T
其中参数value表示要获取或插入的元素，返回值为T类型，表示获取或插入元素的值的所有权。
示例：
use std::collections::HashSet; let mut set: HashSet<u32> = HashSet::new(); let value = set.get_or_insert_owned(1); // 获取或插入元素1 assert_eq!(value, 1); set.insert(2); let new_value = set.get_or_insert_owned(2); // 获取元素2的所有权 assert_eq!(new_value, 2);
3.2.6 get_or_insert_with
get_or_insert_with方法用于获取HashSet中指定元素的引用，如果元素存在，则返回其引用；如果元素不存在，则根据提供的函数生成新的值，并插入新的键值对，并返回新插入元素的可变引用。
其语法格式如下：
fn get_or_insert_with<F>(&mut self, value: K, f: F) -> &mut V where K: Borrow<Q>, Q: Hash + Eq + ?Sized, F: FnOnce() -> V
其中参数value表示要获取或插入的元素，参数f表示用于生成新值的闭包函数。返回值为&mut V类型，表示获取或插入元素的可变引用。
示例：
use std::collections::HashSet; let mut set: HashSet<u32> = HashSet::new(); let value = set.get_or_insert_with(1, || { println!("Generating new value"); 10 }); // 获取或插入元素1 assert_eq!(*value, 1); let new_value = set.get_or_insert_with(1, || { println!("Generating new value"); 20 }); // 获取元素1的引用 assert_eq!(*new_value, 1);
3.2.7 drain
drain方法用于移除HashSet中所有元素，并返回一个迭代器，用于访问被移除的元素。
其语法格式如下：
fn drain(&mut self) -> Drain<'_, T>
所返回的Drain类型是一个迭代器，可用于遍历被移除的元素。
示例：
use std::collections::HashSet; let mut set: HashSet<u32> = HashSet::new(); set.insert(1); set.insert(2); set.insert(3); let drained: Vec<u32> = set.drain().collect(); // 移除所有元素 assert_eq!(drained, vec![1, 2, 3]); assert_eq!(set.len(), 0);
3.2.8 drain_filter
drain_filter方法用于根据指定的条件移除HashSet中的元素，并返回一个迭代器，用于访问被移除的元素。
其语法格式如下：
fn drain_filter<P>(&mut self, pred: P) -> DrainFilter<'_, T, P> where P: FnMut(&mut T) -> bool
其中参数pred表示用于过滤元素的闭包函数，返回值为bool类型，表示元素是否应该被移除。返回的DrainFilter类型是一个迭代器，可用于遍历被移除的元素。
示例：
use std::collections::HashSet; let mut set: HashSet<u32> = HashSet::new(); set.insert(1); set.insert(2); set.insert(3); let drained: Vec<u32> = set.drain_filter(|value| *value % 2 == 0).collect(); // 移除所有偶数元素 assert_eq!(drained, vec![2]); assert_eq!(set.len(), 2);
3.2.9 clear
clear方法用于移除HashSet中的所有元素，使其变为空集合。
其语法格式如下：
fn clear(&mut self)
示例：
use std::collections::HashSet; let mut set: HashSet<u32> = HashSet::new(); set.insert(1); set.insert(2); set.clear(); // 移除所有元素 assert_eq!(set.len(), 0);
3.2.10 retain
retain方法用于根据指定的条件保留HashSet中的元素，移除不满足条件的元素。
其语法格式如下：
fn retain(&mut self, pred: impl FnMut(&T) -> bool)
其中参数pred表示用于保留元素的闭包函数，返回值为bool类型，表示元素是否应该被保留。
例如：
use std::collections::HashSet; let mut set: HashSet<u32> = HashSet::new(); set.insert(1); set.insert(2); set.insert(3); set.retain(|value| *value % 2 == 0); // 保留所有偶数元素 assert_eq!(set.len(), 1); assert!(set.contains(&2));
3.2.11 take
take方法用于从HashSet中移除并返回指定元素的所有权，如果元素存在，则返回其值的所有权并从集合中删除；如果元素不存在，则返回None。
其语法格式如下：
fn take(&mut self, value : &T) -> Option<T>
其中参数value表示要取出的元素的引用，返回值为Option<T>类型，表示取出的元素的值的所有权（如果存在）或None（如果元素不存在）。
示例：
use std::collections::HashSet; let mut set: HashSet<u32> = HashSet::new(); set.insert(1); set.insert(2); let taken_value = set.take(&1); // 移除并返回元素1的所有权 assert_eq!(taken_value, Some(1)); assert!(!set.contains(&1));
3.3查询和检查HashSet
3.3.1 capacity
capacity方法用于返回HashSet的当前容量，即它可以容纳的元素数量而不会重新分配内存。
其语法格式如下：
fn capacity(&self) -> usize
返回值为usize类型，表示当前容量。
示例：
use std::collections::HashSet; let set: HashSet<u32> = HashSet::with_capacity(10); assert_eq!(set.capacity(), 10);
3.3.2 contains
contains方法用于检查HashSet是否包含指定的元素。
其语法格式如下：
fn contains(&self, value: &T) -> bool
其中参数value表示要检查的元素的引用，返回值为bool类型，表示是否包含该元素。
示例：
use std::collections::HashSet; let set: HashSet<u32> = [1, 2, 3].iter().cloned().collect(); assert!(set.contains(&2)); assert!(!set.contains(&4));
3.3.3 get
get方法用于获取HashSet中与指定键对应的值的引用。
其语法格式如下：
fn get(&self, value: &T) -> Option<&T>
其中参数value表示要获取值的键的引用，返回值为Option<&T>类型，表示与指定键对应的值的引用（如果存在）或None（如果键不存在）。
示例：
use std::collections::HashSet; let set: HashSet<u32> = [1, 2, 3].iter().cloned().collect(); assert_eq!(set.get(&2), Some(&2)); assert_eq!(set.get(&4), None);
3.3.4 hasher
hasher方法用于获取用于哈希计算的哈希函数。
其语法格式如下：
fn hasher(&self) -> &S
返回值类型为哈希函数类型的引用。
示例：
use std::collections::HashSet; use std::hash::BuildHasherDefault; let hasher = BuildHasherDefault::<std::collections::hash_map::DefaultHasher>::default(); let set: HashSet<u32, _> = HashSet::with_hasher(hasher); assert_eq!(set.hasher().hash(&1), set.hasher().hash(&1));
3.3.5 is_disjoint
is_disjoint方法用于检查两个HashSet是否没有共同的元素，即它们的交集是否为空。
其语法格式如下：
fn is_disjoint(&self, other: &HashSet<T, S>) -> bool
其中参数other表示要比较的另一个HashSet，返回值为bool类型，表示两个集合是否没有共同的元素。
示例：
use std::collections::HashSet; let set1: HashSet<u32> = [1, 2, 3].iter().cloned().collect(); let set2: HashSet<u32> = [4, 5, 6].iter().cloned().collect(); let set3: HashSet<u 32> = [3, 4, 5].iter().cloned().collect(); assert!(set1.is_disjoint(&set2)); assert!(!set1.is_disjoint(&set3));
3.3.6 is_empty
is_empty方法用于检查HashSet是否为空，即其中是否没有元素。
其语法格式如下：
fn is_empty(&self) -> bool
返回值为bool类型，表示集合是否为空。
示例：
use std::collections::HashSet; let set: HashSet<u32> = HashSet::new(); assert!(set.is_empty());
3.3.7 is_subset
is_subset方法用于检查一个HashSet是否是另一个HashSet的子集，即它是否包含于另一个集合中。
其语法格式如下：
fn is_subset(&self, other: &HashSet<T, S>) -> bool
其中参数other表示要比较的另一个HashSet，返回值为bool类型，表示一个集合是否是另一个集合的子集。
示例：
use std::collections::HashSet; let set1: HashSet<u32> = [1, 2, 3].iter().cloned().collect(); let set2: HashSet<u32> = [1, 2, 3, 4, 5].iter().cloned().collect(); let set3: HashSet<u32> = [4, 5, 6].iter().cloned().collect(); assert!(set1.is_subset(&set2)); assert!(!set1.is_subset(&set3));
3.3.8 is_superset
is_superset方法用于检查一个HashSet是否是另一个HashSet的超集，即它是否包含另一个集合。
其语法格式如下：
fn is_superset(&self, other: &HashSet<T, S>) -> bool
其中参数other表示要比较的另一个HashSet，返回值为bool类型，表示一个集合是否是另一个集合的超集。
示例：
use std::collections::HashSet; let set1: HashSet<u32> = [1, 2, 3, 4, 5].iter().cloned().collect(); let set2: HashSet<u32> = [1, 2, 3].iter().cloned().collect(); let set3: HashSet<u32> = [4, 5, 6].iter().cloned().collect(); assert!(set1.is_superset(&set2)); assert!(!set1.is_superset(&set3));
3.3.9 len
len方法用于获取HashSet中的元素数量。
其语法格式如下：
fn len(&self) -> usize
返回值为usize类型，表示元素的数量。
示例：
use std::collections::HashSet; let set: HashSet<u32> = [1, 2, 3].iter().cloned().collect(); assert_eq!(set.len(), 3);
3.4 集合操作
3.4.1 difference
difference方法用于计算一个HashSet与另一个HashSet的差集，即返回在第一个集合中但不在第二个集合中的元素。
其语法格式如下：
fn difference(&self, other: &HashSet<T, S>) -> HashSet<&T, S>
其中参数other表示要比较的另一个HashSet，返回值为一个新的HashSet，包含差集元素的引用。
示例：
use std::collections::HashSet; let set1: HashSet<u32> = [1, 2, 3, 4].iter().cloned().collect(); let set2: HashSet<u32> = [2, 3, 5].iter().cloned().collect(); let difference: HashSet<&u32> = set1.difference(&set2).collect(); assert_eq!(difference, [1, 4].iter().collect::<HashSet<&u32>>());
3.4.2 intersection
intersection方法用于计算一个HashSet与另一个HashSet的交集，即返回同时存在于两个集合中的元素。
其语法格式如下：
fn intersection(&self, other: &HashSet<T, S>) -> HashSet<&T, S>
其中参数other表示要比较的另一个HashSet，返回值为一个新的HashSet，包含交集元素的引用。
示例：
use std::collections::HashSet; let set1: HashSet<u32> = [1, 2, 3, 4].iter().cloned().collect(); let set2: HashSet<u32> = [2, 3, 5].iter().cloned().collect(); let intersection: HashSet<&u32> = set1.intersection(&set2).collect(); assert_eq!(intersection, [2, 3].iter().collect::<HashSet<&u32>>());
3.4.3 symmetric_difference
symmetric_difference方法用于计算一个HashSet与另一个HashSet的对称差集，即返回只存在于其中一个集合中的元素。
其语法格式如下：
fn symmetric_difference(&self, other: &HashSet<T, S>) -> HashSet<&T, S>
其中参数other表示要比较的另一个HashSet，返回值为一个新的HashSet，包含对称差集元素的引用。
示例：
use std::collections::HashSet; let set1: HashSet<u32> = [1, 2, 3, 4].iter().cloned().collect(); let set2: HashSet<u32> = [2, 3, 5].iter().cloned().collect(); let symmetric_difference: HashSet<&u32> = set1.symmetric_difference(&set2).collect(); assert_eq!(symmetric_difference, [1, 4, 5].iter().collect::<HashSet<&u32>>());
3.4.4 union
union方法用于计算一个HashSet与另一个HashSet的并集，即返回两个集合中所有的元素，去除重复的元素。
其语法格式如下：
fn union(&self, other: &HashSet<T, S>) -> HashSet<&T, S>
其中参数other表示要比较的另一个HashSet，返回值为一个新的HashSet，包含并集元素的引用。
示例：
use std::collections::HashSet; let set1: HashSet<u32> = [1, 2, 3].iter().cloned().collect(); let set2: HashSet<u32> = [2, 3, 4].iter().cloned().collect(); let union: HashSet<&u32> = set1.union(&set2).collect(); assert_eq!(union, [1, 2, 3, 4].iter().collect::<HashSet<&u32>>());
3.5 迭代与遍历
3.5.1 iter
iter方法用于创建一个迭代器，用于按顺序访问HashSet中的元素。
其语法格式如下：
fn iter(&self) -> Iter<'_, T>
返回一个不可变引用的迭代器Iter，它产生&T类型的元素引用。
示例：
use std::collections::HashSet; let set: HashSet<u32> = [1, 2, 3].iter().cloned().collect(); for &item in set.iter() { println!("Item: {}", item); }
3.5.2 iter_mut
iter_mut方法用于创建一个迭代器，用于按顺序可变地访问HashSet中的元素。
其语法格式如下：
fn iter_mut(&mut self) -> IterMut<'_, T>
返回一个可变引用的迭代器IterMut，它产生&mut T类型的元素引用。
示例：
use std::collections::HashSet; let mut set: HashSet<u32> = [1, 2, 3].iter().cloned().collect(); for item in set.iter_mut() { *item += 1; println!("Updated Item: {}", item); }
3.5.3 into_iter
into_iter方法用于创建一个迭代器，用于按顺序取出HashSet中的所有元素，消耗HashSet本身。
其语法格式如下：
fn into_iter(self) -> IntoIter<T>
返回一个拥有所有权的迭代器IntoIter，它产生T类型的元素。
示例：
use std::collections::HashSet; let set: HashSet<u32> = [1, 2, 3].iter().cloned().collect(); for item in set.into_iter() { println!("Item: {}", item); }
3.5.4 drain
drain方法用于创建一个迭代器，用于按顺序可变地访问HashSet中的元素，并且在迭代过程中删除元素。
其语法格式如下：
fn drain(&mut self) -> Drain<T>
返回一个可变引用的迭代器Drain，它产生T类型的元素，并在迭代过程中删除元素。
示例：
use std::collections::HashSet; let mut set: HashSet<u32> = [1, 2, 3].iter().cloned().collect(); for item in set.drain() { println!("Item: {}", item); } assert_eq!(set.len(), 0);
3.6 内存管理
3.6.1 reserve
reserve方法用于预留足够的内存空间，以容纳指定数量的额外元素，减少插入操作的重新分配次数。
其语法格式如下：
fn reserve(&mut self, additional: usize)
参数additional表示要额外容纳的元素数量。
示例：
use std::collections::HashSet; let mut set: HashSet<u32> = HashSet::new(); set.insert(1); set.insert(2); set.reserve(10); assert!(set.capacity() >= 12);
3.6.2 try_reserve
try_reserve方法用于尝试预留足够的内存空间，以容纳指定数量的额外元素。与reserve方法不同的是，try_reserve方法不会触发内存分配失败的 panic，而是返回一个Result类型。
其语法格式如下：
fn try_reserve(&mut self, additional: usize) -> Result<(), CollectionAllocErr>
参数additional表示要额外容纳的元素数量。
返回Ok(())表示成功预留内存空间，返回Err(CollectionAllocErr)表示内存分配失败。
示例：
use std::collections::HashSet; let mut set: HashSet<u32> = HashSet::new(); set.insert(1); set.insert(2); if let Err(e) = set.try_reserve(10) { println!("Failed to reserve memory: {}", e); } else { assert!(set.capacity() >= 12); }
3.6.3 shrink_to
shrink_to方法用于缩小HashSet的容量，使其正好适应当前元素的数量。这可以节省内存空间。
其语法格式如下：
fn shrink_to(&mut self, min_capacity: usize)
参数min_capacity表示缩小后的最小容量。
示例：
use std::collections::HashSet; let mut set: HashSet<u32> = HashSet::new(); set.insert(1); set.insert(2); set.insert(3); set.shrink_to(2); assert!(set.capacity() >= 2);
3.6.4 shrink_to_fit
shrink_to_fit方法用于缩小HashSet的容量，使其尽可能地适应当前元素的数量，释放多余的内存空间。
其语法格式如下：
fn shrink_to_fit(&mut self)
示例：
use std::collections::HashSet; let mut set: HashSet<u32> = HashSet::new(); set.insert(1); set.insert(2); set.insert(3); set.shrink_to_fit(); assert!(set.capacity() >= 3);
4. 哈希函数
4.1 什么是哈希函数
哈希函数是一种特殊的函数，用于 将数据映射为固定长度的哈希值。
哈希函数接受 输入数据 作为参数，并生成 对应的哈希值，其目的是将 大规模的数据集 映射为 较小的哈希值，以便在数据结构（如哈希表）中进行 快速 查找、插入 和 删除 操作。
哈希函数具有以下特点：
- 输入数据的微小变化会导致输出哈希值的巨大变化，称为哈希函数的散列性质；
- 相同的输入始终产生相同的输出；
- 不同的输入几乎不可能产生相同的输出，称为哈希函数的唯一性；
- 哈希函数的输出具有均匀性，即输出哈希值在输出空间中均匀分布。
4.2 Rust 中的哈希函数
4.2.1 概述
在Rust中，哈希函数通常用于数据结构如 HashMap（哈希映射）、HashSet（哈希集） 等的实现中，用于快速索引和查找数据。Rust提供了多种哈希函数的实现，包括 默认哈希函数 和 自定义的哈希函数。
4.2.2 默认哈希函数
Rust标准库提供了默认的哈希函数实现，可以直接在HashMap等数据结构中使用。默认哈希函数基于MurmurHash算法，它具有较好的散列性能和低碰撞率。例如：
use std::collections::hash_map::DefaultHasher; use std::hash::{Hash, Hasher}; fn main() { let mut hasher = DefaultHasher::new(); let data = "Hello, world!"; data.hash(&mut hasher); let hash_value = hasher.finish(); println!("'{}'的哈希值为：{}", data, hash_value); }
outputs：
'Hello, world!'的哈希值为：7092736762612737980
该例演示了如何使用默认哈希函数来计算字符串的哈希值，其中我们创建了一个 DefaultHasher 对象，并使用 hash 方法 计算字符串 data 的哈希值。最后，我们通过 finish 方法获取最终的哈希值，并打印出来。
4.2.3 自定义的哈希函数
除了默认哈希函数，Rust 还支持自定义哈希函数。通过实现Hash trait，我们可以为特定类型自定义哈希函数的行为。
其中 Hash trait 是 Rust 标准库中定义的一个特征，用于表示可以进行哈希计算的类型。它定义了一个 hash 方法，用于计算类型的哈希值：
pub trait Hash { fn hash<H: Hasher>(&self, state: &mut H); }
在使用哈希相关的数据结构（如 HashMap、HashSet）时，这将非常有用，可以使得自定义类型能够正确地进行哈希计算和比较。
需要注意的是，实现 Hash trait 的类型通常还需要实现 Eq 和 PartialEq trait，以确保在进行哈希计算和比较时的一致性。
其中：
- Eq 是等价关系的相等比较的trait：
pub trait Eq: PartialEq<Self> { }
- 详见：https://doc.rust-lang.org/std/cmp/trait.Eq.html
- PartialEq 用于相等比较的trait：
pub trait PartialEq<Rhs = Self> where Rhs: ?Sized, { // Required method fn eq(&self, other: &Rhs) -> bool; // Provided method fn ne(&self, other: &Rhs) -> bool { ... } }
例如：
use std::collections::hash_map::DefaultHasher; use std::hash::{Hash, Hasher}; #[derive(Debug)] // 使用属性自动生成 Debug trait 的实现 struct Person { name: String, age: u32, } impl Hash for Person { fn hash<H: Hasher>(&self, state: &mut H) { self.name.hash(state); self.age.hash(state); } } fn main() { let mut hasher = DefaultHasher::new(); let person = Person { name: "Jack".to_owned(), age: 27, }; person.hash(&mut hasher); let hash_value = hasher.finish(); println!("{:?} 的哈希值为：{} ", person, hash_value); }
outPuts：
Person { name: "Jack", age: 27 } 的哈希值为：4733333810739663368
此例为自定义结构体 Person 实现了哈希函数。在示例中，我们为 Person 结构体实现了 Hash trait，并在hash方法中调用了内部字段的hash方法来计算哈希值。最终，我们获得了 Person 对象的哈希值并进行打印。
通过上述示例代码，我们展示了 Rust 中使用默认哈希函数和自定义哈希函数的方法。你可以根据具体需求选择适合的哈希函数来处理数据，并在实际开发中灵活运用哈希函数的相关知识。
5. 关于 Rust 中 哈希表的大小选择
在 Rust 中，哈希表的大小选择对于性能和内存占用都很重要。适当选择哈希表的大小可以提高查询和插入操作的效率，并减少 哈希冲突 的概率。
在 Rust 的哈希表实现中，哈希表的大小通常通过两个因素确定：容量（capacity） 和 负载因子（load factor）。
| 项目 | 描述 |
| 容量 | 容量是指哈希表中存储元素的槽位数量，也可以理解为哈希表的 桶数。较大的容量可以容纳更多的元素，减少哈希冲突的可能性。容量通常以 2 的幂次方表示，这有助于哈希函数的分布更加均匀。 根据预估的键值对数量选择合适的初始容量，可以使用 HashMap::with_capacity() 方法来指定初始容量。选择适当的初始容量可以减少哈希表的扩容操作，提高性能。一般来说，初始容量应该稍微大于实际键值对数量的预估值，以避免频繁的扩容操作。 |
| 负载因子 | 负载因子是指 已存储的键值对数量 与 哈希表容量的 比值。 过高的负载因子会增加哈希碰撞的概率，影响性能。建议在负载因子接近设定的阈值时，考虑进行扩容操作，以维持较低的碰撞概率。 Rust 中的哈希表默认的负载因子为 0.75，这是一个通常的经验值。 |
因此为了选择合适的哈希表大小，我们需要考虑以下几点：
| 项目 | 描述 |
| 预估元素数量 | 根据实际需求和预期存储的元素数量，选择合适的初始容量。如果预估的元素数量较大，可以选择较大的初始容量以减少扩容操作的次数。 |
| 负载因子 | 根据预估的元素数量和哈希表的容量，计算负载因子。选择适当的负载因子值，确保在存储元素的同时，保持较低的哈希冲突。 |
| 动态扩容 | 哈希表通常具有动态扩容的机制，即在元素数量超过容量的一定阈值时，自动进行扩容。这样可以在保持较低负载因子的同时，提供足够的容量。对于大部分情况，Rust 的哈希表实现能够自动处理扩容操作，无需手动干预。 |
下面是一个示例，展示如何创建一个具有指定容量的哈希表：
use std::collections::HashMap; fn main() { // 创建一个初始容量为 16 的哈希表 let mut map: HashMap<u32, &str> = HashMap::with_capacity(16); // 插入元素 map.insert(1, "apple"); map.insert(2, "orange"); map.insert(3, "banana"); // 获取当前容量 let capacity = map.capacity(); println!("当前容量：{}", capacity); }
outPuts：
当前容量：28
在上面的示例中，通过 HashMap::with_capacity(16) 创建了一个初始容量为 16 的哈希表，并插入了一些元素。通过 capacity() 方法可以获取当前哈希表的容量。
需要注意的是，选择合适的哈希表大小是根据具体的使用情况和需求而定的。对于小规模的数据集，初始容量选择较小的值可能更为合适，而对于大规模数据集，初始容量的选择要更为慎重，以避免过多的扩容操作。
6. 关于 哈希冲突 的说明
6.1 什么是 哈希冲突
在哈希表中，哈希冲突是指不同的键值对经过哈希函数计算后，得到了相同的哈希值，导致它们在哈希表中被分配到相同的存储位置（槽位）的情况。哈希冲突是在使用哈希函数和哈希表时常常遇到的一种情况。
哈希冲突的发生是由于哈希函数的映射空间有限，而键的集合却往往是无限的。因此，不同的键经过哈希函数计算后可能得到相同的哈希值。这种情况下，哈希表就需要处理这些键值对的冲突，以便能够正确地存储和检索数据。
6.2 冲突的处理
哈希冲突的发生会影响哈希表的性能和效率。当多个键值对被分配到同一个存储位置时，需要采取一定的策略来处理冲突。一般常见的解决冲突的方法有以下几种：
| 方法 | 描述 |
| 链地址法 | 将哈希表的每个槽位都存储一个链表（或其他数据结构），具有相同哈希值的键值对会被链接在一起。当发生哈希冲突时，新的键值对会被添加到对应槽位的链表中。 |
| 开放地址法 | 当发生哈希冲突时，尝试寻找哈希表中的其他槽位来存储冲突的键值对，而不是直接链接到链表。常见的开放地址法有线性探测（Linear Probing）、二次探测（Quadratic Probing）和双重哈希（Double Hashing）等。 |
| 再哈希法 | 当发生哈希冲突时，通过应用其他哈希函数对冲突的键值对进行再哈希，得到一个新的哈希值，并尝试将键值对存储到新的槽位中。 |
在 Rust 中，哈希表的实现（例如 HashMap 和 HashSet）采用了 链地址法 来解决哈希冲突。当发生哈希冲突时，具有 相同哈希值的键值对会被 链接在同一个链表中。
通过这种方式以保证在哈希表的 查找、插入 和 删除 操作中，仍然能够高效地 处理冲突，保持良好的性能。
比如：
use std::collections::HashMap; fn main() { // 创建一个哈希表 let mut hashmap = HashMap::new(); // 插入具有相同哈希值的键值对 hashmap.insert("apple", 1); hashmap.insert("orange", 2); hashmap.insert("banana", 3); // 查找键为 "apple" 的值 let apple_value = hashmap.get("apple"); println!("Value of 'apple': {:?}", apple_value); // 查找键为 "orange" 的值 let orange_value = hashmap.get("orange"); println!("Value of 'orange': {:?}", orange_value); }
outPuts：
'apple'的值： Some(1) 'orange'的值： Some(2)
其中：
- 被插入的键值对
"apple"、"orange"和"banana"经过哈希函数计算后得到相同的哈希值，它们被存 储在同一个槽位的链表中。 - 通过
get方法可以根据键查找对应的值。即使发生了哈希冲突，仍然可以正确地检索到对应的值。
