HashMap基础

> HashMap是基于哈希表的键值对存储结构，提供O(1)时间复杂度的查找、插入和删除操作。

为什么需要 HashMap？

问题场景

// 问题：存储和查找学生的分数
// 方案 1：使用 Vec 存储元组（低效）
let students: Vec<(String, i32)> = vec![
    (String::from("Alice"), 90),
    (String::from("Bob"), 85),
    (String::from("Charlie"), 95),
];

// 查找 Alice 的分数需要遍历整个 Vec
fn find_score(students: &[(String, i32)], name: &str) -> Option<i32> {
    for (n, score) in students {
        if n == name {
            return Some(*score);
        }
    }
    None
}
// 时间复杂度：O(n)

// 方案 2：使用 HashMap（高效）
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Alice"), 90);
scores.insert(String::from("Bob"), 85);

let alice_score = scores.get("Alice");  // O(1) 查找！

▶ Run

HashMap 的核心特点

┌─────────────────────────────────────────────────────┐
│              HashMap 特点                            │
├─────────────────────────────────────────────────────┤
│                                                     │
│  核心特性                                            │
│  ├── 键值对存储（Key-Value）                        │
│  ├── O(1) 平均时间复杂度查找/插入/删除              │
│  ├── 键必须唯一（自动去重）                         │
│  └── 无序存储（不保证插入顺序）                     │
│                                                     │
│  与 Vec/数组对比                                     │
│  ┌────────────┬────────────┬─────────────┐          │
│  │ 操作       │ Vec/数组   │ HashMap     │          │
│  ├────────────┼────────────┼─────────────┤          │
│  │ 按索引访问 │ O(1)       │ N/A         │          │
│  │ 按键查找   │ O(n)       │ O(1)        │          │
│  │ 插入       │ O(1)*      │ O(1)        │          │
│  │ 删除       │ O(n)       │ O(1)        │          │
│  └────────────┴────────────┴─────────────┘          │
│  * Vec 末尾插入 O(1)，中间插入 O(n)                  │
│                                                     │
│  使用场景                                            │
│  ✓ 需要通过键快速查找值                             │
│  ✓ 统计词频/数量                                    │
│  ✓ 缓存系统                                         │
│  ✓ 建立映射关系                                     │
│                                                     │
└─────────────────────────────────────────────────────┘

HashMap 工作原理（简化）

HashMap 使用哈希函数实现快速查找：

┌─────────────────────────────────────────────────────┐
│              HashMap 内部结构                        │
├─────────────────────────────────────────────────────┤
│                                                     │
│  键"apple" → 哈希函数 → 哈希值 (如 1726384)         │
│                      ↓                              │
│              映射到桶索引 (如 5)                     │
│                      ↓                              │
│  桶数组：                                            │
│  ┌───┬───┬───┬───┬───┬───┬───┐                     │
│  │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ ...                 │
│  ├───┼───┼───┼───┼───┼───┼───┤                     │
│  │   │   │   │   │   │ → │   │                     │
│  └───┴───┴───┴───┴───┴─┬─┴───┘                     │
│                        ↓                            │
│                  ┌──────────┐                       │
│                  │ "apple"  │                       │
│                  │    5     │                       │
│                  └──────────┘                       │
│                                                     │
│  哈希冲突处理：                                      │
│  • 链地址法：同一位置存储多个元素（链表）           │
│  • 开放寻址：寻找下一个空位                         │
│  • Rust 使用： 开放寻址 + 探测                       │
│                                                     │
└─────────────────────────────────────────────────────┘

---

小结

• HashMap：键值对存储，O(1) 平均查找/插入/删除，无序
• 哈希原理：键→哈希函数→桶索引→存储位置
• 适用场景：快速查找、词频统计、缓存、映射关系
• 与Vec对比：按键查找HashMap更优，按索引访问Vec更优

练习题

详见：练习题