第五章：数据结构与集合类型

5.3 哈希表与集合

在 Rust 中，除了线性数据结构如向量和字符串，我们还需要能够通过键（Key）来高效地查找值（Value）的集合。HashMap 和 HashSet 就是为此而生的两种核心数据结构。它们都基于哈希表实现，提供了近乎常数时间复杂度的插入、查找和删除操作。

5.3.1 什么是 HashMap<K, V>

HashMap<K, V> 是一种键值对（Key-Value Pair）的存储结构。它使用一个哈希函数将键 K 映射到一个存储位置，从而快速定位对应的值 V。

  • 键唯一性：每个键在 HashMap 中只能出现一次。如果插入一个已存在的键，新的值会覆盖旧的值。
  • 无序性：HashMap 不保证元素的存储顺序，遍历时元素的顺序是任意的。

创建与插入

使用 HashMap 前需要引入 std::collections::HashMap。

use std::collections::HashMap;

fn main() {
    // 1. 创建一个空的 HashMap
    let mut scores = HashMap::new();

    // 2. 插入键值对
    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);

    // 3. 使用 collect 方法从元组向量创建
    let teams = vec![String::from("Blue"), String::from("Yellow")];
    let initial_scores = vec![10, 50];
    let scores_from_vec: HashMap<_, _> = teams.iter().zip(initial_scores.iter()).collect();
    // scores_from_vec 的类型是 HashMap<&String, &i32>
}

访问值

使用 get 方法根据键获取值，返回 Option<&V>。

let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);

let team_name = String::from("Blue");
let score = scores.get(&team_name); // 返回 Option<&i32>

match score {
    Some(s) => println!("Blue team score: {}", s),
    None => println!("Team not found"),
}

遍历

可以使用 for 循环遍历 HashMap 中的每一个键值对。

for (key, value) in &scores {
    println!("{}: {}", key, value);
}

更新策略

  1. 覆盖值：直接使用 insert 方法。
  2. 仅在键不存在时插入：使用 entry 方法配合 or_insert。
  3. 根据旧值更新：先获取可变引用，然后修改。
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);

// 仅在 "Blue" 键不存在时插入
scores.entry(String::from("Blue")).or_insert(50); // 不会改变值
scores.entry(String::from("Yellow")).or_insert(50); // 会插入

// 根据旧值更新
let text = "hello world wonderful world";
let mut map = HashMap::new();
for word in text.split_whitespace() {
    let count = map.entry(word).or_insert(0);
    *count += 1; // 解引用并增加计数
}
println!("{:?}", map); // 输出: {"hello": 1, "wonderful": 1, "world": 2}
5.3.2 什么是 HashSet<T>

HashSet<T> 实际上是 HashMap<T, ()> 的一个简单封装，它只关心元素 T 是否存在，而不关心与之关联的值。因此，它是一个不包含重复元素的集合。

  • 元素唯一性：集合中的每个元素都是唯一的。
  • 无序性：同样不保证元素的顺序。

创建与插入

use std::collections::HashSet;

fn main() {
    let mut books = HashSet::new();

    // 插入元素
    books.insert("The Rust Programming Language".to_string());
    books.insert("Programming Rust".to_string());
    books.insert("Rust in Action".to_string());

    // 插入重复元素会被忽略
    books.insert("The Rust Programming Language".to_string());

    println!("Number of books: {}", books.len()); // 输出: 3
}

集合运算

HashSet 的强大之处在于它支持标准的集合运算，如并集、交集、差集和对称差集。

let set_a: HashSet<_> = [1, 2, 3, 4].iter().cloned().collect();
let set_b: HashSet<_> = [3, 4, 5, 6].iter().cloned().collect();

// 并集 (Union): 属于 a 或 b 的所有元素
let union: HashSet<_> = set_a.union(&set_b).cloned().collect(); // {1, 2, 3, 4, 5, 6}

// 交集 (Intersection): 同时属于 a 和 b 的元素
let intersection: HashSet<_> = set_a.intersection(&set_b).cloned().collect(); // {3, 4}

// 差集 (Difference): 属于 a 但不属于 b 的元素
let difference: HashSet<_> = set_a.difference(&set_b).cloned().collect(); // {1, 2}

// 对称差集 (Symmetric Difference): 属于 a 或 b 但不同时属于两者的元素
let sym_diff: HashSet<_> = set_a.symmetric_difference(&set_b).cloned().collect(); // {1, 2, 5, 6}
5.3.3 所有权与哈希函数
  • 所有权：对于实现了 Copy trait 的类型（如 i32、bool），插入 HashMap 或 HashSet 时会复制值。对于拥有所有权的类型（如 String），插入操作会移动所有权，原变量将不再可用。
  • 哈希函数：默认情况下，Rust 使用一种名为 SipHash 的高性能、抗哈希碰撞攻击的哈希函数。如果你不需要这种安全性，并且需要更高的性能，可以使用 FnvHashMap 或 FxHashMap 等替代实现。
5.3.4 性能与选择
  • HashMap：当你需要通过键快速查找、插入或删除对应的值时，这是首选。例如，存储用户 ID 到用户信息的映射。
  • HashSet：当你需要检查一个元素是否存在于一个集合中，或者需要进行集合间的数学运算时，这是最佳选择。例如，检查一个单词是否在字典中，或者找出两个列表中的共同元素。

小结

HashMap 和 HashSet 是 Rust 标准库中提供的最重要的两种基于哈希表的数据结构。它们为高效的数据检索和集合操作提供了坚实的基础。理解它们的创建、访问、更新以及 HashSet 的集合运算，是编写高效 Rust 程序的关键一步。在使用时，需要特别注意所有权转移的问题，并了解默认哈希函数的特性。

Last Updated::