Ch 12: HashMap 和 HashSet

1. 引言

HashMap<K, V> 和 HashSet<T> 是 Rust 标准库提供的高效键值对存储和集合数据类型。它们基于哈希表实现，提供了平均 O(1) 时间复杂度的查找、插入和删除操作。本章将详细讲解这两个类型的核心方法。

2. HashMap 基础

创建 HashMap：

use std::collections::HashMap;

fn main() {
    // 空 HashMap
    let mut map: HashMap<String, i32> = HashMap::new();

    // 使用 from_iter
    let map: HashMap<_, _> = vec![("a", 1), ("b", 2)].into_iter().collect();

    // with_capacity 预分配
    let mut map = HashMap::with_capacity(10);
}

3. insert - 插入键值对

基本用法：

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();

    // insert 返回 Option<V>（如果键已存在，返回旧值）
    let old = map.insert("key".to_string(), 42);

    println!("old: {:?}", old);  // None（之前不存在）

    // 插入已存在的键
    let old = map.insert("key".to_string(), 100);

    println!("old: {:?}", old);  // Some(42)
    println!("{:?}", map);       // {"key": 100}
}

4. get - 获取值

不可变获取：

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    map.insert("apple".to_string(), 3);

    // get 返回 Option<&V>
    match map.get("apple") {
        Some(&count) => println!("苹果数量: {}", count),
        None => println!("没有苹果"),
    }

    // 使用 get_copy（返回 Copy 类型）
    let count = map.get(&"apple").copied().unwrap_or(0);
    println!("{}", count);  // 3
}

可变获取：

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    map.insert("counter".to_string(), 0);

    // get_mut 返回 Option<&mut V>
    if let Some(counter) = map.get_mut("counter") {
        *counter += 1;
    }

    println!("{:?}", map);  // {"counter": 1}
}

5. entry - 键入口API

entry API 是 HashMap 最强大的特性之一，用于安全地处理键不存在的情况：

方法签名：

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

Entry 枚举：

pub enum Entry<'_, K, V> {
    Occupied(OccupiedEntry<'_, K, V>),
    Vacant(VacantEntry<'_, K, V>),
}

示例 - 使用 or_insert：

use std::collections::HashMap;

fn main() {
    let mut map: HashMap<&str, Vec<i32>> = HashMap::new();

    // 键不存在时插入默认值
    map.entry("numbers").or_insert(vec![]);

    // 获取并修改
    map.entry("numbers").or_insert(vec![]).push(42);

    println!("{:?}", map);  // {"numbers": [42]}
}

示例 - 使用 or_insert_with：

use std::collections::HashMap;

fn main() {
    let mut map: HashMap<String, Vec<i32>> = HashMap::new();

    let key = String::from("numbers");

    // 使用闭包生成默认值
    map.entry(key).or_insert_with(Vec::new).push(1);

    // or_insert_with 只在键不存在时调用
    map.entry(String::from("other")).or_insert_with(|| {
        println!("创建新条目！");
        vec![]
    });

    println!("{:?}", map);
}

示例 - 使用 and_modify：

use std::collections::HashMap;

fn main() {
    let mut map: HashMap<&str, Vec<i32>> = HashMap::new();

    // 键不存在时插入，存在时修改
    map.entry("numbers")
        .and_modify(|v| v.push(1))
        .or_insert(vec![1, 2, 3]);

    println!("{:?}", map);  // {"numbers": [1, 2, 3]}

    // 再次调用 and_modify
    map.entry("numbers")
        .and_modify(|v| v.push(10))
        .or_insert(vec![]);

    println!("{:?}", map);  // {"numbers": [1, 2, 3, 10]}
}

6. HashSet 基础

创建 HashSet：

use std::collections::HashSet;

fn main() {
    // 空 Set
    let mut set: HashSet<i32> = HashSet::new();

    // 从迭代器创建
    let set: HashSet<_> = vec![1, 2, 3, 2, 1].into_iter().collect();
    println!("{:?}", set);  // {1, 2, 3}（自动去重）

    // with_capacity
    let set = HashSet::with_capacity(10);
}

7. HashSet 的常用操作

insert - 添加元素：

use std::collections::HashSet;

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

    let inserted = set.insert(1);
    println!("inserted 1: {}", inserted);  // true

    let inserted = set.insert(1);
    println!("inserted 1 again: {}", inserted);  // false（已存在）

    println!("{:?}", set);  // {1}
}

contains - 检查元素：

use std::collections::HashSet;

fn main() {
    let set: HashSet<_> = [1, 2, 3].into();

    println!("contains 2: {}", set.contains(&2));  // true
    println!("contains 4: {}", set.contains(&4));  // false
}

remove - 移除元素：

use std::collections::HashSet;

fn main() {
    let mut set: HashSet<_> = [1, 2, 3].into();

    let removed = set.remove(&2);
    println!("removed 2: {}", removed);  // true

    let removed = set.remove(&2);
    println!("removed 2 again: {}", removed);  // false

    println!("{:?}", set);  // {1, 3}
}

8. Set 运算

is_subset 和 is_superset - 子集关系：

use std::collections::HashSet;

fn main() {
    let a: HashSet<_> = [1, 2, 3].into();
    let b: HashSet<_> = [1, 2, 3, 4, 5].into();
    let c: HashSet<_> = [1, 2].into();

    println!("c is subset of a: {}", c.is_subset(&a));     // true
    println!("a is subset of b: {}", a.is_subset(&b));    // true
    println!("b is superset of a: {}", b.is_superset(&a)); // true
}

intersection - 交集：

use std::collections::HashSet;

fn main() {
    let a: HashSet<_> = [1, 2, 3].into();
    let b: HashSet<_> = [2, 3, 4].into();

    let intersection: HashSet<_> = a.intersection(&b).cloned().collect();

    println!("intersection: {:?}", intersection);  // {2, 3}
}

union - 并集：

use std::collections::HashSet;

fn main() {
    let a: HashSet<_> = [1, 2, 3].into();
    let b: HashSet<_> = [2, 3, 4].into();

    let union: HashSet<_> = a.union(&b).cloned().collect();

    println!("union: {:?}", union);  // {1, 2, 3, 4}
}

difference - 差集：

use std::collections::HashSet;

fn main() {
    let a: HashSet<_> = [1, 2, 3].into();
    let b: HashSet<_> = [2, 3, 4].into();

    let difference: HashSet<_> = a.difference(&b).cloned().collect();

    println!("a - b: {:?}", difference);  // {1}
}

symmetric_difference - 对称差集：

use std::collections::HashSet;

fn main() {
    let a: HashSet<_> = [1, 2, 3].into();
    let b: HashSet<_> = [2, 3, 4].into();

    let diff: HashSet<_> = a.symmetric_difference(&b).cloned().collect();

    println!("a △ b: {:?}", diff);  // {1, 4}
}

9. raw_entry - 低级哈希API

raw_entry 提供了更底层的哈希表操作接口：

方法签名：

pub fn raw_entry(&mut self) -> RawEntryBuilder<_, K, V, S>

示例：

use std::collections::HashMap;
use std::hash::BuildHasherDefault;
use std::collections::hash_map::RandomState;

fn main() {
    let mut map: HashMap<String, i32> = HashMap::new();
    map.insert(String::from("hello"), 42);

    // 使用 raw_entry_mut 进行更灵活的操作
    map.raw_entry_mut()
        .from_key("hello")
        .map(|(k, v)| {
            println!("found: {} = {}", k, v);
        });

    // 修改
    map.raw_entry_mut()
        .from_key("hello")
        .or_insert(String::from("hello"), 100);
}

10. 实战示例：词频统计

use std::collections::HashMap;

fn word_frequency(text: &str) -> HashMap<&str, usize> {
    let mut freq = HashMap::new();

    for word in text.split_whitespace() {
        // 使用 or_insert 增加计数
        *freq.entry(word).or_insert(0) += 1;
    }

    freq
}

fn main() {
    let text = "hello world hello rust hello world rust rust";

    let freq = word_frequency(text);

    println!("词频统计:");
    for (word, count) in &freq {
        println!("{}: {}", word, count);
    }
}

11. 实战示例：分组统计

use std::collections::HashMap;

#[derive(Debug)]
struct Person {
    name: String,
    age: u32,
}

fn group_by_age(people: Vec<Person>) -> HashMap<u32, Vec<Person>> {
    let mut groups: HashMap<u32, Vec<Person>> = HashMap::new();

    for person in people {
        groups
            .entry(person.age)
            .or_insert_with(Vec::new)
            .push(person);
    }

    groups
}

fn main() {
    let people = vec![
        Person { name: "Alice".to_string(), age: 30 },
        Person { name: "Bob".to_string(), age: 25 },
        Person { name: "Charlie".to_string(), age: 30 },
        Person { name: "Diana".to_string(), age: 25 },
    ];

    let grouped = group_by_age(people);

    for (age, persons) in &grouped {
        println!("年龄 {}: {:?}", age, persons);
    }
}

12. 需要注意的点

1. entry API 是最推荐的方式：它比 get + insert 更高效，避免了双重查找。

2. HashMap 和 HashSet 默认使用 RandomState：提供防止 Hash DoS 攻击的安全性。

3. K 必须实现 Eq + Hash：大多数标准库类型都实现了这两个 trait。

4. HashMap 和 HashSet 是 !Sync（当 K 或 V 不是 Sync 时）：注意线程安全。

5. raw_entry 更底层：普通情况下应该使用 entry API，只有在需要自定义哈希逻辑时才使用 raw_entry。

13. 总结

HashMap 和 HashSet 是 Rust 中最常用的哈希表实现：

HashMap 方法	作用
insert	插入键值对，返回旧值
get	获取值（不可变）
get_mut	获取值（可变）
entry	键入口 API
remove	移除键值对
contains_key	检查键是否存在
len/is_empty	大小信息

HashSet 方法	作用
insert	添加元素
contains	检查元素
remove	移除元素
union/intersection/difference	集合运算
is_subset/is_superset	子集关系

Entry API	作用
or_insert	不存在时插入默认值
or_insert_with	不存在时用闭包生成值
and_modify	存在时修改值

掌握这些方法能够让你高效地处理键值对和集合操作。