这一篇在干嘛？
BST 查找最快也要 ；散列（hashing）直接”算出”元素的位置，把平均查找做到 ——数据库索引、缓存、编译器符号表、去重集合，底层全是它。本章解决两个核心问题：怎么设计哈希函数（把键均匀打撒），冲突了怎么办（三种排解法各有什么代价）。
5.1 一般思路
理想状态：每个键通过一个函数 映射到大小为 的表中的某个位置，直接存取。理想很美好，现实有两个拦路虎：
- 哈希函数不完美：不同的键可能算出同一个位置——这叫冲突（collision），必然发生（鸽笼原理：键的数量远超表大小）。
- 表不能无限大：装填因子 越高，冲突越频繁。
白话：散列像”把书按书名首字母放进 26 个格子”。首字母分布不均（冲突多）或格子太少（ 高）都会让某个格子变成一摞书。散列设计的全部艺术 = 好函数 + 合适的 + 冲突排解策略。
5.2 哈希函数设计
整数键：最常用 key % TableSize。表大小选质数是重要习惯——若表大小是 10 而键全是 10 的倍数，全撞一个位置；质数能”打碎”输入中的规律。
字符串键：经典做法是把字符当成多项式系数计算：
size_t hash(const string &s) {
size_t h = 0;
for (char c : s)
h = 37 * h + c; // 相当于把字符串看成 37 进制数
return h;
}白话：只加首尾字符（书里的坏例子）会让 “abc” 和 “cba” 撞车；多项式滚动哈希让每个字符、每个位置都参与运算，分布均匀。哈希函数的合格标准：快 + 均匀，均匀是冲突率的前提。
5.3 分离链接（Separate Chaining）：冲突就挂链
每个位置挂一条链表，冲突的元素全塞进同一条链：
操作与代价：查找 = 先算哈希定位桶（），再在链内逐一比较。链长期望 ，所以平均查找 ——保持 （表装得不太满）就是关键。
bool contains(const HashedObj &x) const {
auto &whichList = theLists[myhash(x)];
return find(whichList.begin(), whichList.end(), x) != whichList.end();
}
bool remove(const HashedObj &x) {
auto &whichList = theLists[myhash(x)];
auto itr = find(whichList.begin(), whichList.end(), x);
if (itr == whichList.end())
return false;
whichList.erase(itr);
--currentSize;
return true;
}白话：策略最简单、实现最直白，代价是多一层链表指针的内存开销和缓存不友好。实践中另一半流派是”不挂链”，见下。
5.4 开放定址（Open Addressing）：撞了就找下一个空位
所有元素直接住在表里，冲突时按探测序列（probe sequence） 找空位。删除只能打”懒惰删除”标记（墓碑），不能真删——否则会截断别人的探测链。
线性探测：试 f(i)=i
冲突就试下一个格、再下一个……问题叫一次聚集（primary clustering）：任何键撞上”一段连续占用区”后，都会把它变得更长，形成恶性循环。期望探测次数在 时约 2.5 次、 时暴涨到约 50 次。
平方探测：试 f(i)=i²
冲突后试 1、4、9、16… 位置。它打破连续聚集（探测位置不再连成一片），且有个漂亮的定理保证：
定理 5.1：表大小为质数且表至少有一半为空（）时，平方探测总能找到一个空位。
白话：平方探测可能撞重复位置（i² mod M 在 i 跨半周期后重复），质数表 + 半空保证”前 ⌊M/2⌋ 次探测位置全不相同”。代价：表满了必须再散列（rehash，见 5.5），不能就地增长。次要问题是二次聚集：哈希值相同的键走同一条探测路径——影响小于一次聚集，可用双散列消除。
双散列：试 f(i)=i·hash₂(x)
用第二个哈希函数决定步长，彻底打散探测路径。选 hash₂ 时要保证永不为 0（否则原地打转），常见 R - (x % R)（R 为质数）。
5.5 再散列（Rehashing）
表太满（平方探测要求 ；分离链接一般 时扩容），就建一张约 2 倍大、下一个质数的新表，把所有元素按新表大小重新哈希插入。总代价 ，但触发频率低（扩容翻倍），摊还每次插入仍是 。
白话：和 vector 扩容一模一样的思路——“搬家摊还”。唯一区别是搬进新家后每个元素的门牌号要重算（哈希值依赖表大小）。
5.6 STL 的无序容器
unordered_set / unordered_map：接口与 set/map 相同，底层就是哈希表（典型为分离链接），平均 、最坏 。自定义类型的哈希要显式提供：
struct CaseInsensitiveHash {
size_t operator()(const string &s) const {
size_t h = 0;
for (char c : s)
h = 37 * h + tolower(c); // 大小写不敏感的哈希
return h;
}
};
struct CaseInsensitiveEqual {
bool operator()(const string &lhs, const string &rhs) const {
int n = lhs.size();
if (rhs.size() != n) return false;
for (int i = 0; i < n; ++i)
if (tolower(lhs[i]) != tolower(rhs[i])) return false;
return true;
}
};
unordered_set<string, CaseInsensitiveHash, CaseInsensitiveEqual> s;白话：换哈希表别忘了相等判断也要配套换（哈希相等 ≠ 真相等）。选 set 还是 unordered_set：要有序遍历/范围查询选 set；只要去重和查找、数据量大的选 unordered。
5.7 最坏情形也想 O(1)：布谷鸟散列一瞥
分离链接和开放定址的最坏情形都是 （全撞一格）。布谷鸟散列（cuckoo hashing）用两张表、两个哈希函数：每个元素只可能住在两个位置之一，查找最多比较 2 次——最坏情形 。
插入冲突时把”鸠占鹊巢”：把占位的旧元素踢出去，旧元素去它的另一个备选位置，可能连环踢。若踢入死循环，触发再散列换哈希函数重来。
白话：查找快到极致（两次定点查询），代价是插入可能连环搬迁。名字来自杜鹃鸟”把别人的蛋踢出窝”的习性。
常见坑
① 表大小用了合数：
key % TableSize遇规律输入全撞一格——质数是免费保险。② 开放定址的真删除：直接置空会截断他人的探测链，必须懒惰删除（墓碑），墓碑多了触发再散列。③ 平方探测表装太满：定理保证的前提是 且表大小为质数，破了前提可能探测不全表就死循环。
通关标准
学完本篇你应该能做到：① 手写字符串多项式哈希并解释为什么表大小要取质数；② 写出分离链接的 contains/remove；③ 说清线性探测的一次聚集、平方探测的定理条件、双散列的步长要求；④ 解释再散列为什么摊还 O(1)；⑤ 知道布谷鸟散列凭什么做到最坏 O(1) 查找。
为什么哈希表的表大小要用质数？
取模会把输入中的规律（如全部是偶数、全是表大小的倍数）映射到少数位置。质数与常见输入规律”互质”，能最大化分散；同时平方探测的定理也要求表大小为质数。
开放定址法为什么不能物理删除元素？
探测链会经过被删位置：真删等于”此路不通”标记消失，后续查找会提前撞到空位、误判不存在。只能打墓碑标记，并在墓碑过多时再散列清理。
分离链接的查找为什么是 O(1+λ)？λ 取多大合适？
定位桶 O(1)，链长期望 = 装填因子 λ，所以 O(1+λ)。λ=1（元素数≈表大小）是常用平衡点：内存开销可控，链长期望 1。
平方探测的定理为什么要求"表至少一半为空"？
表大小为质数 M 时，探测序列前 ⌊M/2⌋ 项两两不同（i² ≡ (M−i)² mod M），若空位少于一半，⌊M/2⌋ 次探测内可能全是占用位，无法保证成功插入。
再散列和 vector 扩容的异同？
相同：都是翻倍搬家、摊还 O(1)。不同：vector 搬家按原顺序复制，哈希表搬家要按新表大小重新计算每个元素的位置，因为哈希值依赖表大小。