作者：李俊才 （jcLee95）：https://blog.csdn.net/qq_28550263?spm=1001.2101.3001.5343
邮箱 ：291148484@163.com
本文地址：https://blog.csdn.net/qq_28550263/article/details/130876735

【介绍】：本文介绍 Rust 中哈希结构相关概念及其使用。在 Rust 中，提供了两种哈希表，一个是 HashMap，另外一个是 HashSet，本文都将逐一介绍，并介绍 哈希函数 的用法。

1. 概述

1.1 什么是哈希表

哈希表（Hash Table），也被称为 散列表，是一种数据结构，它提供了快速插入、删除和查找操作的能力。在计算机科学中，哈希表是非常重要的，因为它们可以在平均情况下实现 O(1) 的时间复杂度，这使得它们在许多场景中都非常有用，例如数据库、编译器和缓存系统。

哈希表的基本原理是将键（Key）通过哈希函数（Hash Function）映射到一个数组中的位置（也称为“桶”），然后将值（Value）存储在该位置。当需要查找某个键对应的值时，只需再次应用哈希函数，找到对应的位置，即可快速获取值。

1.2 Rust 语言中的哈希表

哈希映射（HashMap）和 哈希集（HashSet）是Rust 标准库提供的两种基于哈希表的数据结构，以下我们用 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 { ... }
  }
  

  详见：https://doc.rust-lang.org/std/cmp/trait.PartialEq.html

例如：

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）。

因此为了选择合适的哈希表大小，我们需要考虑以下几点：

下面是一个示例，展示如何创建一个具有指定容量的哈希表：

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 冲突的处理

哈希冲突的发生会影响哈希表的性能和效率。当多个键值对被分配到同一个存储位置时，需要采取一定的策略来处理冲突。一般常见的解决冲突的方法有以下几种：

在 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 方法可以根据键查找对应的值。即使发生了哈希冲突，仍然可以正确地检索到对应的值。