HashMap实战总结

> 综合运用HashMap知识，通过实战示例巩固键值对操作，识别常见错误与性能优化技巧。

HashMap 常用方法大全

rust

use std::collections::HashMap;

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

    // ========== 基本操作 ==========
    // 插入
    map.insert(String::from("a"), 1);

    // 获取
    let val = map.get(&String::from("a"));  // Option<&i32>

    // 获取可变引用
    let val = map.get_mut(&String::from("a"));  // Option<&mut i32>

    // 删除
    let removed = map.remove(&String::from("a"));  // Option<i32>

    // ========== 查询 ==========
    // 是否包含键
    let exists = map.contains_key(&String::from("a"));  // bool

    // 是否为空
    let empty = map.is_empty();  // bool

    // 长度
    let len = map.len();  // usize

    // ========== entry API ==========
    // 获取或插入
    let val = map.entry(String::from("b")).or_insert(2);

    // 获取或插入（使用闭包）
    let val = map.entry(String::from("c")).or_insert_with(|| 3);

    // 如果存在则修改
    map.entry(String::from("a")).and_modify(|v| *v += 1);

    // ========== 容量管理 ==========
    // 容量
    let cap = map.capacity();

    // 缩小容量
    map.shrink_to_fit();

    // 保留容量
    map.reserve(100);

    // ========== 批量操作 ==========
    // 清空
    map.clear();

    // 保留满足条件的元素
    map.retain(|k, v| *v > 0);

    // ========== 迭代器 ==========
    // 迭代（借用）
    for (k, v) in map.iter() {
        println!("{}: {}", k, v);
    }

    // 迭代（可变借用）
    for (k, v) in map.iter_mut() {
        *v += 1;
    }

    // 只迭代键
    for k in map.keys() {
        println!("{}", k);
    }

    // 只迭代值
    for v in map.values() {
        println!("{}", v);
    }
}

▶ Run

完整示例

示例 1：通讯录管理系统

rust

use std::collections::HashMap;

#[derive(Debug)]
struct Contact {
    name: String,
    phone: String,
    email: String,
    group: String,
}

struct AddressBook {
    contacts: HashMap<String, Contact>,
}

impl AddressBook {
    fn new() -> Self {
        AddressBook {
            contacts: HashMap::new(),
        }
    }

    fn add(&mut self, name: String, phone: String, email: String, group: String) {
        let contact = Contact {
            name: name.clone(),
            phone,
            email,
            group,
        };
        self.contacts.insert(name, contact);
        println!("✓ 已添加联系人");
    }

    fn find(&self, name: &str) -> Option<&Contact> {
        self.contacts.get(name)
    }

    fn find_mut(&mut self, name: &str) -> Option<&mut Contact> {
        self.contacts.get_mut(name)
    }

    fn remove(&mut self, name: &str) -> Option<Contact> {
        self.contacts.remove(name)
    }

    fn list_by_group(&self, group: &str) {
        println!("\n{} 组联系人:", group);
        println!("{:-<50}", "");

        for (name, contact) in &self.contacts {
            if contact.group == group {
                println!("  {}: {} - {}", name, contact.phone, contact.email);
            }
        }
    }

    fn list_all(&self) {
        if self.contacts.is_empty() {
            println!("通讯录为空");
            return;
        }

        println!("\n全部联系人:");
        println!("{:-<50}", "");

        // 按名字排序输出
        let mut names: Vec<_> = self.contacts.keys().collect();
        names.sort();

        for name in names {
            let contact = &self.contacts[name];
            println!("  {} [{}] {} - {}",
                     contact.name,
                     contact.group,
                     contact.phone,
                     contact.email);
        }
    }

    fn statistics(&self) -> HashMap<String, usize> {
        let mut stats = HashMap::new();

        for contact in self.contacts.values() {
            *stats.entry(contact.group.clone()).or_insert(0) += 1;
        }

        stats
    }
}

fn main() {
    let mut book = AddressBook::new();

    // 添加联系人
    book.add(
        String::from("Alice"),
        String::from("123-4567"),
        String::from("alice@example.com"),
        String::from("同事"),
    );
    book.add(
        String::from("Bob"),
        String::from("987-6543"),
        String::from("bob@example.com"),
        String::from("朋友"),
    );
    book.add(
        String::from("Charlie"),
        String::from("555-1234"),
        String::from("charlie@example.com"),
        String::from("同事"),
    );
    book.add(
        String::from("Diana"),
        String::from("444-5678"),
        String::from("diana@example.com"),
        String::from("家人"),
    );

    // 列出所有联系人
    book.list_all();

    // 按组列出
    book.list_by_group("同事");

    // 查找联系人
    if let Some(contact) = book.find("Alice") {
        println!("\n找到 Alice:");
        println!("  电话：{}", contact.phone);
        println!("  邮箱：{}", contact.email);
        println!("  组别：{}", contact.group);
    }

    // 修改联系人
    if let Some(contact) = book.find_mut("Bob") {
        contact.phone = String::from("999-9999");
        println!("\n✓ 已更新 Bob 的电话");
    }

    // 删除联系人
    if let Some(contact) = book.remove("Charlie") {
        println!("\n✓ 已删除联系人：{}", contact.name);
    }

    // 统计
    println!("\n联系人统计:");
    for (group, count) in book.statistics() {
        println!("  {}: {} 人", group, count);
    }

    // 最终列表
    book.list_all();
}

▶ Run

示例 2：简单的缓存系统

rust

use std::collections::HashMap;

struct Cache<K, V> {
    data: HashMap<K, V>,
    capacity: usize,
}

impl<K: std::hash::Hash + Eq + Clone, V: Clone> Cache<K, V> {
    fn new(capacity: usize) -> Self {
        Cache {
            data: HashMap::with_capacity(capacity),
            capacity,
        }
    }

    fn get(&self, key: &K) -> Option<V> {
        self.data.get(key).cloned()
    }

    fn insert(&mut self, key: K, value: V) -> Option<V> {
        // 如果缓存已满且是新键，删除最旧的键
        if self.data.len() >= self.capacity && !self.data.contains_key(&key) {
            // 简单实现：删除第一个键
            if let Some(first_key) = self.data.keys().next().cloned() {
                self.data.remove(&first_key);
            }
        }
        self.data.insert(key, value)
    }

    fn contains(&self, key: &K) -> bool {
        self.data.contains_key(key)
    }

    fn len(&self) -> usize {
        self.data.len()
    }

    fn is_empty(&self) -> bool {
        self.data.is_empty()
    }

    fn clear(&mut self) {
        self.data.clear();
    }

    fn keys(&self) -> impl Iterator<Item = &K> {
        self.data.keys()
    }
}

fn main() {
    let mut cache = Cache::new(3);

    // 添加数据
    cache.insert("url1", "data1");
    cache.insert("url2", "data2");
    cache.insert("url3", "data3");

    println!("缓存内容:");
    for key in cache.keys() {
        if let Some(value) = cache.get(key) {
            println!("  {}: {}", key, value);
        }
    }

    // 添加新数据（应该淘汰最旧的）
    cache.insert("url4", "data4");

    println!("\n添加 url4 后:");
    for key in cache.keys() {
        if let Some(value) = cache.get(key) {
            println!("  {}: {}", key, value);
        }
    }

    // 检查缓存命中
    println!("\n缓存命中率测试:");
    println!("url1 在缓存中：{}", cache.contains(&"url1"));
    println!("url2 在缓存中：{}", cache.contains(&"url2"));
}

▶ Run

示例 3：图的邻接表表示

rust

use std::collections::{HashMap, HashSet};

type Node = String;
type Graph = HashMap<Node, Vec<Node>>;

fn create_graph() -> Graph {
    let mut graph = HashMap::new();

    graph.insert(String::from("A"), vec![String::from("B"), String::from("C")]);
    graph.insert(String::from("B"), vec![String::from("D"), String::from("E")]);
    graph.insert(String::from("C"), vec![String::from("F")]);
    graph.insert(String::from("D"), vec![]);
    graph.insert(String::from("E"), vec![String::from("F")]);
    graph.insert(String::from("F"), vec![]);

    graph
}

// 广度优先搜索
fn bfs(graph: &Graph, start: &str, end: &str) -> Option<Vec<String>> {
    use std::collections::VecDeque;

    let mut queue = VecDeque::new();
    queue.push_back(vec![start.to_string()]);

    let mut visited = HashSet::new();
    visited.insert(start);

    while let Some(path) = queue.pop_front() {
        let node = path.last().unwrap();

        if node == end {
            return Some(path);
        }

        if let Some(neighbors) = graph.get(node) {
            for neighbor in neighbors {
                if visited.insert(neighbor.clone()) {
                    let mut new_path = path.clone();
                    new_path.push(neighbor.clone());
                    queue.push_back(new_path);
                }
            }
        }
    }

    None
}

// 深度优先搜索
fn dfs(graph: &Graph, start: &str, end: &str) -> Option<Vec<String>> {
    fn dfs_helper(
        graph: &Graph,
        current: &str,
        end: &str,
        visited: &mut HashSet<String>,
        path: &mut Vec<String>,
    ) -> Option<Vec<String>> {
        visited.insert(current.to_string());
        path.push(current.to_string());

        if current == end {
            return Some(path.clone());
        }

        if let Some(neighbors) = graph.get(current) {
            for neighbor in neighbors {
                if !visited.contains(neighbor) {
                    if let Some(result) = dfs_helper(graph, neighbor, end, visited, path) {
                        return Some(result);
                    }
                }
            }
        }

        path.pop();
        None
    }

    let mut visited = HashSet::new();
    let mut path = Vec::new();
    dfs_helper(graph, start, end, &mut visited, &mut path)
}

fn main() {
    let graph = create_graph();

    println!("图结构:");
    for (node, neighbors) in &graph {
        println!("  {} -> {:?}", node, neighbors);
    }

    // BFS 查找路径
    if let Some(path) = bfs(&graph, "A", "F") {
        println!("\nBFS 路径：{}", path.join(" -> "));
    } else {
        println!("\n未找到路径");
    }

    // DFS 查找路径
    if let Some(path) = dfs(&graph, "A", "F") {
        println!("DFS 路径：{}", path.join(" -> "));
    }
}

▶ Run

性能优化技巧

预分配容量

rust

use std::collections::HashMap;

// ❌ 低效：可能多次重新分配
fn inefficient() -> HashMap<i32, String> {
    let mut map = HashMap::new();
    for i in 0..1000 {
        map.insert(i, format!("value{}", i));
    }
    map
}

// ✅ 高效：预分配容量
fn efficient() -> HashMap<i32, String> {
    let mut map = HashMap::with_capacity(1000);
    for i in 0..1000 {
        map.insert(i, format!("value{}", i));
    }
    map
}

▶ Run

使用 entry 避免多次查找

rust

use std::collections::HashMap;

// ❌ 低效：两次查找
fn inefficient_count(map: &mut HashMap<String, usize>, word: &str) {
    if map.contains_key(word) {
        let count = map.get(word).unwrap();
        map.insert(word.to_string(), count + 1);
    } else {
        map.insert(word.to_string(), 1);
    }
}

// ✅ 高效：一次查找
fn efficient_count(map: &mut HashMap<String, usize>, word: &str) {
    *map.entry(word.to_string()).or_insert(0) += 1;
}

▶ Run

避免不必要的克隆

rust

use std::collections::HashMap;

// ❌ 不必要的克隆
fn unnecessary_clone(map: &HashMap<String, i32>, key: &str) -> Option<i32> {
    if map.contains_key(key) {
        map.get(key).cloned()  // 这里可以优化
    } else {
        None
    }
}

// ✅ 直接使用引用
fn use_reference(map: &HashMap<String, i32>, key: &str) -> Option<&i32> {
    map.get(key)  // 返回引用，无需克隆
}

▶ Run

常见错误

错误 1：键类型不匹配

rust

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    map.insert(String::from("key"), 1);

    // ❌ 错误：类型不匹配
    // let val = map.get("key");  // &str vs &String

    // ✅ 正确
    let val = map.get(&String::from("key"));
    let val = map.get("key");  // HashMap 支持 Borrow  trait
}

▶ Run

错误 2：迭代时修改 HashMap

rust

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    map.insert(1, 10);
    map.insert(2, 20);

    // ❌ 错误：迭代时不能修改
    // for (k, v) in &map {
    //     map.insert(*k, *v + 1);
    // }

    // ✅ 正确：先收集再更新
    let updates: Vec<_> = map
        .iter()
        .map(|(&k, &v)| (k, v + 1))
        .collect();

    for (k, v) in updates {
        map.insert(k, v);
    }
}

▶ Run

错误 3：忘记 entry 返回的是引用

rust

use std::collections::HashMap;

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

    // ❌ 错误：尝试直接赋值
    // scores.entry("Blue").or_insert(0) = 10;

    // ✅ 正确：通过解引用修改
    *scores.entry("Blue".to_string()).or_insert(0) = 10;

    // ✅ 或者累加
    *scores.entry("Blue".to_string()).or_insert(0) += 10;
}

▶ Run

错误 4：依赖遍历顺序

rust

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    map.insert(1, "one");
    map.insert(2, "two");
    map.insert(3, "three");

    // ❌ 错误：HashMap 不保证顺序
    // 不要依赖这个顺序
    for (k, v) in &map {
        println!("{}: {}", k, v);
    }

    // ✅ 正确：如果需要顺序，使用 BTreeMap
    use std::collections::BTreeMap;
    let mut sorted = BTreeMap::new();
    sorted.insert(1, "one");
    sorted.insert(2, "two");
    sorted.insert(3, "three");

    for (k, v) in &sorted {
        println!("{}: {}", k, v);  // 保证按键排序
    }
}

▶ Run

调试技巧

打印 HashMap

rust

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    map.insert("a", 1);
    map.insert("b", 2);

    // 基本输出
    println!("{:?}", map);

    // 美化格式
    println!("{:#?}", map);
}

▶ Run

调试容量和负载

rust

use std::collections::HashMap;

fn main() {
    let mut map: HashMap<i32, i32> = HashMap::with_capacity(10);

    println!("初始容量：{}", map.capacity());

    for i in 0..20 {
        map.insert(i, i * 2);
        println!("插入 {} 后：len={}, cap={}", i, map.len(), map.capacity());
    }
}

▶ Run

练习

练习 1：字符频率统计

编写函数，统计字符串中每个字符出现的次数：

rust

fn char_frequency(text: &str) -> HashMap<char, usize> {
    // 实现
}

▶ Run

练习 2：两数之和

给定一个整数数组和一个目标值，找出两个数的索引，使它们的和等于目标值：

rust

fn two_sum(nums: Vec<i32>, target: i32) -> Option<(usize, usize)> {
    // 使用 HashMap 实现 O(n) 解法
}

▶ Run

练习 3：分组聚合

给定一个 (姓名，分数) 的列表，计算每个人的平均分数：

rust

fn average_scores(scores: Vec<(&str, i32)>) -> HashMap<String, f64> {
    // 实现
}

▶ Run

练习 4：LRU 缓存

实现一个简单的 LRU（最近最少使用）缓存：

get(key) - 获取值，并将其标记为最近使用
put(key, value) - 插入值，如果超出容量则删除最久未使用的

小结

HashMap 核心概念

概念	说明
键值对	Key-Value 存储
哈希函数	将键映射到桶索引
O(1) 查找	平均时间复杂度
无序	不保证遍历顺序
键唯一	自动覆盖已存在的键

常用方法速查

方法	说明	返回值
`insert(k, v)`	插入键值对	`Option<V>`
`get(&k)`	获取值	`Option<&V>`
`get_mut(&k)`	获取可变引用	`Option<&mut V>`
`remove(&k)`	删除键值对	`Option<V>`
`contains_key(&k)`	检查键存在	`bool`
`entry(k)`	entry API	`Entry`
`keys()`	键迭代器	`Keys`
`values()`	值迭代器	`Values`
`retain(\|k, v\| ...)`	保留满足条件的元素	-

entry API 模式

rust

// 模式 1：计数
*map.entry(key).or_insert(0) += 1;

// 模式 2：构建列表
map.entry(key).or_insert_with(Vec::new).push(value);

// 模式 3：条件更新
map.entry(key).and_modify(|v| *v = new_value);

▶ Run

关键要点

HashMap 无序：需要有序时使用 BTreeMap
键必须实现 Hash + Eq：自定义类型需要派生这些 trait
entry API 高效：避免多次查找
借用灵活：可以使用不同类型的键进行查找
预分配容量：已知大小时优化性能

练习题

详见：练习题

HashMap实战总结 ​

HashMap 常用方法大全 ​

完整示例 ​

示例 1：通讯录管理系统 ​

示例 2：简单的缓存系统 ​

示例 3：图的邻接表表示 ​

性能优化技巧 ​

预分配容量 ​

使用 entry 避免多次查找 ​

避免不必要的克隆 ​

常见错误 ​

错误 1：键类型不匹配 ​

错误 2：迭代时修改 HashMap ​

错误 3：忘记 entry 返回的是引用 ​

错误 4：依赖遍历顺序 ​

调试技巧 ​

打印 HashMap ​

调试容量和负载 ​

练习 ​

练习 1：字符频率统计 ​

练习 2：两数之和 ​

练习 3：分组聚合 ​

练习 4：LRU 缓存 ​

小结 ​

HashMap 核心概念 ​

常用方法速查 ​

entry API 模式 ​

关键要点 ​

练习题 ​

HashMap实战总结

HashMap 常用方法大全

完整示例

示例 1：通讯录管理系统

示例 2：简单的缓存系统

示例 3：图的邻接表表示

性能优化技巧

预分配容量

使用 entry 避免多次查找

避免不必要的克隆

常见错误

错误 1：键类型不匹配

错误 2：迭代时修改 HashMap

错误 3：忘记 entry 返回的是引用

错误 4：依赖遍历顺序

调试技巧

打印 HashMap

调试容量和负载

练习

练习 1：字符频率统计

练习 2：两数之和

练习 3：分组聚合

练习 4：LRU 缓存

小结

HashMap 核心概念

常用方法速查

entry API 模式

关键要点

练习题