📚

哈希表：图书馆索书号——按编号直接到抽屉

1000 个键值，找任意一个平均只要「一步半」：先算编号，再翻那个抽屉的短名单。

💡 打个比方：图书馆索书号

图书馆找书不用一本本翻：每本书有索书号，看号码直接走到对应的书架抽屉。哈希表也一样：哈希函数把 key「翻译」成抽屉编号，直接去那个抽屉——找 = 算一次编号 + 翻一个短名单。

📖 术语小抄：哈希表（hash table） = 用「编号直接定位」的查找表；哈希函数（hash function） = 把 key 变地址的规则；取余法 = 地址 = key % 表大小；冲突（collision） = 不同 key 算出同一地址；拉链法（chaining） = 每个抽屉挂一条链表，撞了排成一列；查找（lookup） = 算地址 + 翻那个抽屉。

🖼️ 大图看明白：7 个抽屉的哈希表 + 一次冲突

哈希表（大小 7）：每个抽屉 0..6 0 1 2 3 4 5 6 （空） （空） （空） 3 （空） 5 12 （空） 手算：key % 7 = 抽屉号 insert 5： 5 % 7 = 5 → 抽屉 5 insert 12：12 % 7 = 5 → 抽屉 5（冲突！排队） insert 3： 3 % 7 = 3 → 抽屉 3 查找：算地址 → 翻那个抽屉 find(12)：12 % 7 = 5 → 抽屉 5 名单 [5 → 12]：5？不是 → 12？命中！YES find(9)：9 % 7 = 2 → 抽屉 2（空）→ NO 冲突怎么办？ 每个抽屉挂一条链表（拉链法）： 撞进同一抽屉的 key 排成一列， 查找时把这一列逐个比完。 key 在抽屉里　红框 + 红箭头 = 冲突后排进链表　（空）= 这个抽屉没人

🧩 子任务 1：哈希函数——把 key 变成「抽屉编号」

🎯 小目标：会用取余法算地址 key % 表大小，记住哈希函数的两条铁律。
// 哈希函数：把 key（号码）翻译成地址（抽屉号）
// 最常用的：取余法
//   地址 = key % 表大小
//
// 表大小 7 时：
//   5 % 7 = 5    12 % 7 = 5    3 % 7 = 3    9 % 7 = 2
//
// 两条铁律：
//   1. 同一个 key → 永远同一个抽屉（确定性，否则插进去就找不回来）
//   2. 不同的 key → 可能同一个抽屉（这叫「冲突」，不丢人，要处理）
// 附带性质：地址一定落在 0 .. 表大小 - 1（取余的规矩），不会越界
✅ 小检查：① 表大小 7，key 20 进哪个抽屉？② key 7 呢？③ 地址的范围是什么？为什么取余法保证不越界？
看看答案 ① 20 % 7 = 6 → 抽屉 6。 ② 7 % 7 = 0 → 抽屉 0（整除的 key 都进 0 号抽屉）。 ③ 地址 ∈ 0 .. 6（表大小 - 1 = 6）。因为「任何整数除以 7 的余数」只能是 0~6，所以地址永远不会超出抽屉范围。
⚠️ 易错：以为「不同 key 一定去不同抽屉」——错了！不同 key 可以撞进同一抽屉（5 和 12 都是 5 号）。看到两个 key 地址相同不是 bug，是冲突，接下来子任务 2 处理它。

🧩 子任务 2：冲突——两个 key 挤进同一抽屉；拉链法

🎯 小目标：理解冲突为什么必然发生；掌握拉链法「每格挂链表」的插入/查找动作。
// 冲突：5 % 7 = 5 且 12 % 7 = 5 —— 两个 key 都要住 5 号抽屉。
// 抽屉只有一个，怎么办？
//
// 拉链法（chaining）：每个抽屉后面挂一条小链表
//   插入：算地址 → 把 key 接到那个抽屉链表的尾部
//   查找：算地址 → 把那个抽屉链表从头到尾逐个比，找到就命中
//   删除：在链表里找到它 → 按链表删除的方式摘掉
//
// 代价：链表越长，查找越慢（退化成 O(n) 逐个翻）
//   表太小 / 塞太满 → 链平均变长 → 变慢
//   工程对策：太满时「扩容」——换更大的表，所有 key 重新取余搬进新家
//   （「满不满」用 装载因子 = key 数 / 表大小 来量，一般 > 0.75 就扩容）
✅ 小检查：① 两个 key 撞进同一抽屉，谁先进、谁后进有关系吗？② 为什么表「太满」要扩容？③ 如果每个格子只能存 1 个 key（不挂链表），第二个进来的 key 会怎样？
看看答案 ① 没关系的顺序：先来的在链表头、后来的接尾部（或反过来都一样）——查找会把整条链比完，谁先谁后不影响「找得到」。 ② 太满 → 每个抽屉的链表变长 → 查找从「平均 O(1)」退化到「翻长链」；扩容后 key 被摊开到更多抽屉，链变短，速度恢复。 ③ 后来的 key 要么把先来的顶掉（数据丢了），要么得另想办法找空位（那是「开放地址法/线性探测」的活，有自己的坑）。拉链法最直观：一格一条链。
⚠️ 易错：① 查找时算完地址只比了链表第一个就下结论「没有」——必须把整条链比完；② 插入忘「先取余再定位」，直接把 key 当抽屉号用（key 12 去开 12 号抽屉 → 表只有 7 格直接越界）。

🧩 子任务 3：手推——表大小 7，插 3 个 key（含一次冲突），再查

🎯 小目标：对 key 5、12、3 逐个手推「取余 → 进抽屉 → 撞了挂链」的全过程，再手推 find(12) 和 find(9)。
// 表大小 7（抽屉 0..6），拉链法。依次插入 5、12、3：
//
// insert 5：  5 % 7 = 5 → 抽屉 5，链表空 → 直接进：[5]
// insert 12：12 % 7 = 5 → 抽屉 5，链表不空 → 冲突！接尾部：[5 → 12]
// insert 3：  3 % 7 = 3 → 抽屉 3，链表空 → 直接进：[3]
//
// 此刻每个抽屉：0 空、1 空、2 空、3: [3]、4 空、5: [5 → 12]、6 空
//
// find(12)：12 % 7 = 5 → 去 5 号抽屉
//   链表 [5 → 12]：比 5？不是 → 比 12？命中！→ 返回 YES（比了 2 次）
// find(9)：9 % 7 = 2 → 去 2 号抽屉
//   链表空 → 返回 NO（比了 0 次）
✅ 小检查：① 插入完成后，3 号抽屉和 5 号抽屉各是什么？② find(12) 的完整路径是什么？比较了几次？③ 如果表大小改成 12，key 5、12、3 各进哪个抽屉？还会有冲突吗？
看看答案 ① 3 号：[3]；5 号：[5 → 12]（5 和 12 撞了，排成一列）。 ② 12 % 7 = 5 → 抽屉 5 → 比 5（不是）→ 比 12（命中）→ YES，共比较 2 次。 ③ 5 % 12 = 5、12 % 12 = 0、3 % 12 = 3——三个 key 落在三个不同抽屉，没有冲突。表越大，撞的概率越小。
⚠️ 易错：① 插入时「忘了先取余」直接拿 key 当抽屉号（key 12 → 12 号抽屉，表只有 7 格，越界）；② 查 12 时「比了 5 不是就报 NO」——链没翻完不能下结论；③ 冲突发生时把两个 key 都写在同一个格子里（格子只有一格，得挂链）。

🧩 子任务 4：快在哪——平均 O(1)，对比数组和链表

🎯 小目标：说清哈希表查找为什么平均 O(1)；对比数组（要连续下标）和链表（O(n)）；知道最坏情况。
// 三种「找东西」结构的速度对比：
//
// 数组：O(1)，但 key 必须能当下标（非负、连续、范围小）
//   key = 学号 1..100 → 开 int a[101]，a[学号] 直接拿，飞快
//   key = 手机号（11 位）→ 要开 1000 亿格，99.99% 是空的，内存爆炸
//
// 链表：O(n)，从表头一格格翻，1000 个找 1 个，最坏翻 1000 次
//
// 哈希表：平均 O(1)——key 可以是任意大的数（甚至字符串）
//   一次取余（O(1)）+ 翻一条短链（平均也就 1~2 个）≈ 常数时间
//
// 最坏情况：所有 key 全撞进同一个抽屉 → 链长 = n → 退化 O(n)
//   → 所以哈希函数要「摊得均匀」，表不能太满（满了扩容）
// 一句话：数组快但挑 key，链表不挑 key 但慢，
//   哈希表 = 不挑 key + 平均快，代价是可能退化。
✅ 小检查：① 为什么「按手机号查人」用数组不划算，用哈希表划算？② 哈希表查找最坏 O(几)？什么时候发生？③ 链表 1000 个元素找一个，最坏多少次？哈希表（表大小 1009、1000 个 key）平均多少次？
看看答案 ① 手机号 11 位，数组得开 1000 亿格（int 要 400GB），而且大部分是空的；哈希表开几千格就够，key 多大都能取余映射进去，内存省 + 速度 O(1)。 ② 最坏 O(n)：所有 key 的 key%表大小 全相同（挤进一个抽屉），退化成翻长链。 ③ 链表最坏 1000 次（目标在表尾）；哈希表平均常数次（1 次取余 + 链上平均 1~2 次比较）。
⚠️ 易错：① 「平均 O(1)」≠「永远 O(1)」——写复杂度分析要区分平均和最坏；② 题目里看到「查某个数出没出现过 / 出现几次」且 key 是分散的大整数，先想到哈希表（C++ 里就是 unordered_map / unordered_set，下一课细说）。

💻 完整代码：模拟拉链哈希表（vector<list>）插入 + 查找

🎯 小目标：读懂「7 个抽屉，每格一条链表」的插入与查找；样例输出 YES、NO、YES。
// 表大小 7：vector 存 7 条 list = 7 个抽屉各挂一条链
#include <bits/stdc++.h>
using namespace std;

const int SZ = 7;
vector<list<int>> table(SZ);    // table[0..6]，初始都是空链

void insert(int key) {
    int addr = key % SZ;         // 哈希：取余法
    table[addr].push_back(key);  // 接到那个抽屉链表的尾部
}

bool find(int key) {
    int addr = key % SZ;
    for (int x : table[addr])    // 把整条链逐个比
        if (x == key) return true;
    return false;                // 链翻完了还没有 → 不在表里
}

int main() {
    insert(5);
    insert(12);   // 冲突：12 % 7 = 5，和 5 同一个抽屉
    insert(3);
    cout << (find(12) ? "YES" : "NO") << endl;  // YES
    cout << (find(9)  ? "YES" : "NO") << endl;  // NO
    cout << (find(5)  ? "YES" : "NO") << endl;  // YES
    return 0;
}

// 运行过程对照：
//   插 5  → 5 % 7 = 5 → table[5] = [5]
//   插 12 → 12 % 7 = 5 → 冲突，接尾 → table[5] = [5, 12]
//   插 3  → 3 % 7 = 3 → table[3] = [3]
//   find(12)：查 table[5]，比 5 不是、比 12 命中 → YES
//   find(9) ：查 table[2]，空链 → NO
//   find(5) ：查 table[5]，比 5 命中 → YES

✋ 你来试试

第 1 题：表大小 7，依次插入 1、8、15。每个抽屉最终是什么？ 1 % 7 = 1、8 % 7 = 1、15 % 7 = 1——三个 key 全撞进 1 号抽屉：table[1] = [1, 8, 15]，其余抽屉空。find(15) 要比较 3 次——撞得越狠越慢，这就是「退化」。
第 2 题：表大小 7，插入 5、12、3 之后，find(20)：去哪个抽屉？20 没插过，返回什么？ 20 % 7 = 6 → 6 号抽屉；6 号是空链，链翻完（0 次比较）→ 返回 NO。（如果 6 号抽屉里碰巧有别的 key，就要逐个比完才说 NO。）
第 3 题：1000 个学号存链表，找学号 998 最坏比多少次？改存哈希表（表大小 1009）平均比多少次？ 链表最坏 1000 次（998 排在表尾）；哈希表平均常数次（1 次取余 + 链上平均 1~2 次比较，1009 是质数、1000 个 key 摊开后链很短）。
第 4 题（加餐）：表大小 10，key 全是 10 的倍数（10、20、30、…）。key 会落到哪？说明了什么？ 10 % 10 = 20 % 10 = 30 % 10 = 0——全部落进 0 号抽屉，彻底退化成链表 O(n)。说明：哈希函数必须「摊得均匀」；工程上表大小一般取质数，让「都是 10 的倍数」这种规律难撞成一锅。反过来想：表大小 7（质数）时，10 的倍数 10%7=3、20%7=6、30%7=2，就散开了。
🎯 一句话记住：哈希表 = 图书馆索书号——哈希函数（取余 key % 表大小）把 key 变成抽屉号，直接定位；不同 key 可能撞进同一抽屉（冲突），用拉链法每格挂链表、查找把整条链比完；速度 = 1 次取余 + 翻短链，平均 O(1)（不挑 key，任意大数/字符串都行）；最坏全撞一格退化 O(n)，所以「摊得均匀 + 别太满（满了扩容）」。
← 上一课：泛洪 fill 下一课：哈希表应用 →