Lesson 0416 · 哈希表：unordered_map / unordered_set

④ 数据结构与算法 — 第 16 课

1. 什么时候需要它

先看一个对比。同样是「查某个东西在不在」，两种键的差别很大：

2. C++ 里的四个工具

四个工具的常用操作几乎一样，记住这几个就够：

unordered_map<int, int> cnt;

cnt[key] = v;              // 写入（★ 键不存在时会先插入一个默认值 0 再赋值）
cnt[key]++;                // 计数最常用
auto it = cnt.find(key);   // 查找；没找到返回 cnt.end()
if (it != cnt.end()) { /* it->second 是值 */ }
if (cnt.count(key)) { }    // 只判「在不在」
cnt.erase(key);            // 删除

for (auto& [k, v] : cnt) { }   // 遍历（无序！相同代码两次运行顺序可能不同）

3. P3613 寄包柜：把一对下标编码成一个整数

关键在于：格子总数 10⁷ 开不下二维数组（10⁵ × 10⁵ 更不可能），而实际用到的格子最多 q 个。这正是哈希表的典型场景：只有 (i, j) 真的被写过，才占内存。

两种存法：

// ① 把 (i, j) 编码成一个整数当键（推荐：一张表，省内存也快）
const long long BASE = 1000005;
unordered_map<long long, int> box;      // key = i * BASE + j

// ② 每个柜子一张表：柜子多、每个柜子只用到少数格子时，空表本身也很占地方
vector<unordered_map<int, int>> box2(n + 1);

主循环（两种存法只是查询那一行不同）：

int op; cin >> op;
if (op == 1) {
    int i, j, k; cin >> i >> j >> k;
    long long key = (long long)i * BASE + j;
    if (k == 0) box.erase(key);        // 清空 = 删掉这个键
    else        box[key] = k;
} else {
    int i, j; cin >> i >> j;
    cout << box[(long long)i * BASE + j] << '\n';   // 查过的格子保证有值
}

实测（q = 10⁵ 次操作，一半写入一半查询）

另外用 200 组小规模数据与「二维数组」对拍（含 k = 0 的清空操作）：0 次不一致。

4. P1102 A-B 数对：一遍扫为什么是错的

最自然的想法是「扫一遍，对每个 a_i 看看前面有没有 ai − C」：

// ✗ 错写法：只统计了「B 出现在 A 前面」的对
unordered_map<int, int> cnt;
long long ans = 0;
for (int x : a) {
    auto it = cnt.find(x - C);
    if (it != cnt.end()) ans += it->second;
    cnt[x]++;
}

它漏掉了先出现 A、后出现 B 的情况。比如 a = [5, 3]、C = 2：扫到 5 时表里还没有 3，扫到 3 时又去找 3−2=1 —— 正确的那一对从头到尾没被数。

实测：这个写法在 500 组随机小数据上错了 336 组。正确写法是先把整张表建好，再统一查：

// ✓ 两遍：先建全表，再对每个 B 查 B + C 的个数
unordered_map<int, int> cnt;
cnt.reserve(a.size() * 2);          // 先要够空间，省掉反复扩容
for (int x : a) cnt[x]++;
long long ans = 0;                  // ★ 答案最大 4×10^10，必须 long long
for (int x : a) {
    auto it = cnt.find(x + C);
    if (it != cnt.end()) ans += it->second;
}
cout << ans << '\n';

两遍写法在同样的 500 组数据上0 次不一致。

和「排序 + 二分」比一比

两个结论：

• 哈希不一定更快。随机数据上排序 + 二分反而赢，因为 unordered_map 每次操作要算哈希、跳内存，缓存不友好；而排序后二分是连续内存访问。数据规模不大时（10⁵ 级）两者差别完全可以忽略，选你写得顺手的。
• 答案会超 int。全相同时是 n² = 4×1010，int 直接溢出。这题的正确打开方式是先算上界再定类型。

5. P1918 保龄球：值 → 位置

unordered_map<int, int> pos;    // 值 → 位置
pos.reserve(n * 2);
for (int i = 1; i <= n; i++) {
    int x; cin >> x;
    pos[x] = i;
}

int Q; cin >> Q;
while (Q--) {
    int m; cin >> m;
    auto it = pos.find(m);
    cout << (it == pos.end() ? 0 : it->second) << '\n';
}

同一件事有三种做法，实测（n = Q = 10⁵）：

map 建表慢了一倍多（每个节点都要维护红黑树），但查询一样快 —— 因为 10⁵ 次查询的 log 只有 17 步，差别被内存访问吃掉了。只有在「需要按键顺序遍历」时才值得用 map。

6. 性能：reserve 与「被卡哈希」

reserve 是真的有用

差别来自「扩容」：元素多了要重新分配桶、把所有元素搬一遍。知道大概有多少个键时，一行 reserve 能省掉近一半时间。

什么时候哈希表会被卡

内存开销

哈希表每个元素除了键和值，还要存指针/节点信息（典型 32–56 字节），是数组的几倍。所以「10⁷ 个 int」用数组只要 40 MB，用 unordered_map 可能爆内存 —— 这时还是排序或离散化更稳。

7. 坑点清单

• mp[k] 会插入：判断存在性只能用 find / count
• 答案用 long long：数对的答案能到 n²（P1102 的 4×10¹⁰ 就是典型）
• 编码 key 的 BASE 要够大：i * BASE + j 里 BASE 必须 > j 的最大值
• 一遍扫可能漏掉逆序对：需要「两边都算」时，先建全表再查询
• 遍历顺序不固定：unordered_map 两次运行可能打印顺序不同；要顺序输出就换 map 或自己排序
• 边遍历边插入会崩：for (auto& [k,v] : mp) mp[newKey] = 1; 会导致迭代器失效（rehash），要改就另建一张表
• 键类型要能哈希：pair / 自定义结构体不能直接当键（要自己写 hash），用编码整数代替
• 大输入先 reserve，能省近一半时间

8. 小测

9. 动手练习

1. P3613 寄包柜 —— 主战场。把 (i, j) 编码成一个 long long；记住 k = 0 是清空（用 erase，不是存一个 0）。n、q ≤ 10⁵。
2. P1102 A-B 数对 —— 别用「扫一遍查 x−C」那个错写法；先建全表再查。答案记得 long long。
3. P1918 保龄球 —— 值 → 位置；这题也可以排序 + 二分，两种都写一遍对比一下耗时。

本课小结

• 哈希表解决「键不是小整数」的查询：数组下标 → 任意键，平均 O(1)
• 四个工具：unordered_map / unordered_set（哈希，无序）、map / set（有序树，O(log n)）
• mp[k] 会插入，判存在用 find / count
• 编码 key：i * BASE + j，BASE 取 j 的上界 + 1（P3613 实测：一张表 5.3 ms vs 每柜一张 11.7 ms）
• P1102 的教训：一遍扫漏逆序对（500 组错 336 组），先建全表再查才是对的；答案到 4×1010，必须 long long
• 哈希不一定比排序二分快（随机 2×10⁵：37.3 vs 22.4 ms），别迷信
• reserve 能省一半（10⁶ 次插入：317 → 180 ms）
• 会被卡哈希：需要稳定或有序时换 map 或排序二分