查找与哈希表

10.1 查找的基本概念与平均查找长度

10.1.1 什么是查找表

查找（search）的定义非常朴素：在由同一类型数据元素（或记录）构成的集合中， 找出一个关键字等于给定值的元素。这个集合就叫查找表（search table）。 注意查找表在逻辑上是一种集合——元素之间除了「同属一张表」之外没有别的约束， 但一旦落到存储结构上，它可能是顺序表、链表、树或者散列表， 而存储结构直接决定了你能用哪种查找算法。

按允许的操作，查找表分成两类，这是选择题的常客：

10.1.2 关键字：主关键字与次关键字

关键字（key）是数据元素中用来标识该元素的那个数据项的值。 如果这个数据项能唯一标识一个元素，就称为主关键字（primary key）； 若它可能标识出多个元素，就称为次关键字（secondary key）。

主关键字

能唯一区分每个记录。例如学号、身份证号、数据库主键。用主关键字查找，结果要么是恰好一个元素，要么「不存在」。

次关键字

可能重复。例如「姓名」「班级」「性别」。用次关键字查找，结果可能是一组元素——所以工程上叫「范围查询 / 多值查询」。

查找成功 / 不成功

表中存在关键字等于给定值的元素，叫查找成功（successful search）； 找遍全表也不存在，叫查找不成功（unsuccessful search），通常返回一个特殊标记（-1、nullptr、end()）。

平均查找长度 ASL

Average Search Length。查找过程中关键字比较次数的期望值，是衡量查找算法优劣的核心指标（而不是简单的「最坏情况」）。

10.1.3 ASL 的定义与公式

设查找表有 n 个元素，查找第 i 个元素的概率为 pi， 找到它所需要的关键字比较次数为 ci，那么查找成功的平均查找长度定义为：

在等概率假设下（即 pi = 1/n，绝大多数考题都这么假设），公式退化为：

而查找不成功的 ASL 是另一个式子：把「失败」的每种可能情形（折半查找里是每个外部结点、 哈希表里是每个探测起点、分块查找里是每个索引块）当作一次「等可能的查找」， 若共有 m 种失败情形、第 j 种需要 dj 次比较，则

上表是「先建立全局印象」用的，每个数字的推导都在后面的小节里，请务必自己推一遍再回来对照。

10.1.4 查找算法的评价维度

比较两个查找算法时，按下面五个维度看，基本不会漏：

10.2 顺序查找：从哨兵到有序表

10.2.1 一句话本质与三种扫描方向

顺序查找（sequential search，又称线性查找 linear search）的本质是一句话： 从表的一端开始，用给定值 key 逐个与表中元素的关键字比较，相等就成功，扫完全表都找不到就失败。 它不需要数据有序、不需要顺序存储（链表也能用），是唯一「什么结构都能上」的查找方法。

10.2.2 顺序表的顺序查找与成功 ASL 推导

设表长为 n（下标 1..n，这是教材惯用的 1 基写法，方便写 ASL 公式）， 从前往后扫。查找第 i 个元素需要比较 ci = i 次。 在等概率假设下 pi = 1/n：

这个结果要能脱口而出。直观理解：如果每次查的都是「第一个元素」要 1 次、「最后一个」要 n 次， 平均下来就是首尾的算术平均值 (1+n)/2。

注意一个细节：等概率假设一旦不成立，结论就变了。如果各元素的查找概率 pi 已知， 把概率大的元素放在靠前的位置可以让 ASL 变小——这正是「按访问频率排序的自组织线性表」的思想：

10.2.3 失败 ASL：n 还是 n+1？

这是顺序查找里最容易被扣分的地方。结论先给： 无序表的顺序查找，失败时平均比较次数是 n；带哨兵的实现是 n+1。 两者不是矛盾，而是数法约定不同。看下面这张逐次比较的拆解：

10.2.4 有序表的顺序查找：失败 ASL 为什么能减半

如果表是有序的（比如从小到大），顺序查找依然可以从前扫到后， 但它多了一个「提前刹车」的机会：一旦发现 a[i] > key，就可以立刻断定失败， 因为后面所有元素只会更大。

我们把「失败」的所有情形按 key 的落点分类。有序表 a[1..n] 把数轴切成了 n+1 个区间： (−∞, a[1])、(a[1], a[2])、…、(a[n−1], a[n])、(a[n], +∞)。 假设 key 等可能地落在任意一个区间里（这是标准假设，也解释了分母为什么是 n+1）：

于是（注意最后一种情况的比较次数也是 n）：

当 n 较大时，n/(n+1) → 1，所以 ASL失败 ≈ n/2 + 1 —— 相比无序表的 n，几乎砍掉了一半。这非常符合直觉：有序表里 key 一旦比当前元素小， 就知道后面不用看了，「平均只要看一半」。

10.2.5 链式存储上的顺序查找

链表只能顺序查找，而且缺点被放大了：每访问一个结点都要解引用一次指针， cache 命中率极低（CPU 预取器对随机地址无能为力），常数因子通常是数组的 3~10 倍。 链表做顺序查找的 ASL 与顺序表完全一样（(n+1)/2 与 n）， 因为比较次数只取决于链表长度，与存储方式无关。

唯一的「优势」是：如果要在有序链表上找 key，找到第一个 > key 的结点即可停， 与有序顺序表同理；而且链表上的插入删除是 O(1)（已知前驱时）， 所以「频繁增删 + 查找不多」的场景，链表 + 顺序查找反而合适。

10.2.6 优缺点、适用场景与 C++ 实现

#include <iostream>
#include <vector>
using namespace std;

/* =====================================================================
   顺序查找的三种写法（本文件统一用 1 基下标，a[0] 空出或作哨兵）
   约定：每次"访问一个存储位置并做关键字判定"记 1 次比较
   ===================================================================== */

/* ---------- ① 朴素版：从前往后扫（0 基） ---------- */
// 成功：c_i = i+1   → ASL_success = (n+1)/2
// 失败：n 次比较     → ASL_fail   = n
int seqSearchPlain(const vector<int>& a, int key) {
    for (int i = 0; i < (int)a.size(); ++i)
        if (a[i] == key) return i;          // 命中
    return -1;                              // 扫完全表都没找到
}

/* ---------- ② 带哨兵版：从后往前扫（1 基，a[0] 是哨兵） ---------- */
// a[1..n] 存数据。把 key 放进 a[0]，循环里就不必判断 i > 0：
// 即使全表都没有 key，也一定会在 a[0] 处停下 —— 这就是"哨兵"的作用。
// 成功：c_i = n-i+1 → ASL_success = (n+1)/2
// 失败：n+1 次比较（含与哨兵的那一次）→ ASL_fail = n+1
int seqSearchSentinel(vector<int>& a, int key) {
    int n = (int)a.size() - 1;              // a[0] 不存数据
    a[0] = key;                             // 设置哨兵
    int i = n;
    while (a[i] != key) --i;                // 没有 i >= 1 的判断！
    return i;                               // i == 0 表示查找失败
}

/* ---------- ③ 有序表的顺序查找：可以提前刹车 ---------- */
// a[0..n-1] 严格递增。一旦 a[i] > key，后面只会更大，直接判定失败。
// 成功：仍为 (n+1)/2
// 失败：ASL_fail = n/2 + n/(n+1)   （见正文推导）
int seqSearchOrdered(const vector<int>& a, int key) {
    int n = (int)a.size();
    for (int i = 0; i < n; ++i) {
        if (a[i] == key) return i;
        if (a[i] > key)  return -1;         // 提前刹车，省掉后面所有比较
    }
    return -1;
}

int main() {
    vector<int> v = {17, 25, 39, 42, 58, 66, 73};      // 共 7 个元素，已有序

    cout << seqSearchPlain(v, 39)     << "\n";          // 2
    cout << seqSearchPlain(v, 100)    << "\n";          // -1

    vector<int> w;                                     // 1 基存储：w[0] 是哨兵位
    w.push_back(0);                                    // 占位
    for (int x : v) w.push_back(x);
    cout << seqSearchSentinel(w, 39)  << "\n";          // 3（因为 39 在 w[3]）
    cout << seqSearchSentinel(w, 100) << "\n";          // 0 → 失败

    cout << seqSearchOrdered(v, 39)   << "\n";          // 2
    cout << seqSearchOrdered(v, 40)   << "\n";          // -1，只比了 4 次就刹车

    /* 验证 ASL 公式：统计所有成功查找的总比较次数 */
    int total = 0, n = (int)v.size();
    for (int i = 0; i < n; ++i) total += (i + 1);       // 第 i 个元素要 i+1 次
    cout << "ASL_success = " << (double)total / n << "\n";   // (7+1)/2 = 4
    return 0;
}

10.2.7 动手看三种写法的比较次数

下面这个动画把 ①朴素（从前往后）、②带哨兵（从后往前）、③有序表提前刹车 三种写法 放在同一组数据上同步演示：逐格高亮当前比较的元素，并分别统计比较次数。 先用一个能查到的 key 看成功路径，再用两个查不到的 key 对比三种写法的失败代价。

10.3 折半查找：判定树与 ASL 手推

10.3.1 前提条件与一句话本质

折半查找（binary search，又称二分查找）的本质是一句话： 每次拿区间中点元素与 key 比较，一次比较就能砍掉一半的候选区间。 但天下没有免费的午餐，它有两个硬性前提，缺一不可：

10.3.2 算法流程与 C++ 实现

用闭区间 [left, right] 表示还在候选范围内的下标， 每轮取 mid = left + (right − left) / 2 （不要写 (left + right) / 2！当 left 与 right 都接近 INT_MAX 时它会在加法处溢出，得到负数下标，程序直接崩溃。 这是 LeetCode 上都写进题解的老坑）。

每轮三分支：

• a[mid] == key → 查找成功，返回 mid；
• a[mid] < key → 目标只可能在右半区间，令 left = mid + 1；
• a[mid] > key → 目标只可能在左半区间，令 right = mid − 1。

重复直到 left > right（区间为空）→ 查找失败。

先看它一步步怎么收缩区间，注意右侧判定树是怎么同步长出来的：

#include <iostream>
#include <vector>
using namespace std;

/* ============ 折半查找：迭代版 ============
   前提：a 已按升序排好，且支持 O(1) 随机访问
   返回 key 所在下标，找不到返回 -1
   约定：每执行一次 a[mid] 与 key 的比较记 1 次 */
int binarySearch(const vector<int>& a, int key, int* cmpCnt = nullptr) {
    int left = 0, right = (int)a.size() - 1, cnt = 0;
    while (left <= right) {                     // 闭区间 [left, right] 非空
        int mid = left + (right - left) / 2;    // 防溢出！不要写 (left+right)/2
        ++cnt;
        if (a[mid] == key) { if (cmpCnt) *cmpCnt = cnt; return mid; }
        else if (a[mid] < key) left  = mid + 1; // 目标在右半边
        else                   right = mid - 1; // 目标在左半边
    }
    if (cmpCnt) *cmpCnt = cnt;
    return -1;
}

/* ============ 折半查找：递归版 ============
   递归深度 = 判定树高度 = ⌈log2(n+1)⌉，所以空间 O(log n)（栈帧） */
int binarySearchRec(const vector<int>& a, int key, int left, int right) {
    if (left > right) return -1;                // 区间为空 → 失败
    int mid = left + (right - left) / 2;
    if (a[mid] == key)      return mid;
    if (a[mid] <  key)      return binarySearchRec(a, key, mid + 1, right);
    return binarySearchRec(a, key, left, mid - 1);
}

/* ============ 用递归版数判定树层数与 ASL（就是"逐层统计"） ============ */
// 在判定树上，比较次数 = 结点所在层号（根为第 1 层）
int cntAtLevel(const vector<int>& a, int key, int left, int right, int depth) {
    if (left > right) return 0;                 // 落到外部结点，表示失败
    int mid = left + (right - left) / 2;
    if (a[mid] == key) return depth;            // 成功：返回所在层号
    if (a[mid] <  key) return cntAtLevel(a, key, mid + 1, right, depth + 1);
    return cntAtLevel(a, key, left, mid - 1, depth + 1);
}

int main() {
    /* 造一个 n = 11 的有序表，方便和正文的判定树对照（值 10,20,...,110） */
    vector<int> a;
    for (int i = 1; i <= 11; ++i) a.push_back(i * 10);

    int cmp = 0;
    cout << binarySearch(a, 70, &cmp) << " 比较次数=" << cmp << "\n";   // 6 比较次数=1
    cout << binarySearch(a, 110, &cmp) << " 比较次数=" << cmp << "\n";  // 10 比较次数=4
    cout << binarySearch(a, 75, &cmp) << " 比较次数=" << cmp << "\n";   // -1 比较次数=4

    cout << binarySearchRec(a, 10, 0, 10) << "\n";                    // 0

    /* ---- 逐元素统计"成功比较次数"，用程序验证 ASL = 33/11 = 3 ----
       注意：判定树的形状只由"下标"决定，与元素的值无关。
       下面是本程序对 n = 11 实际算出的层号表（与正文判定树完全一致）：
         下标 :  0  1  2  3  4  5  6  7  8  9  10
         层号 :  3  4  2  3  4  1  3  4  2  3   4
       逐层汇总：第1层1个 + 第2层2个 + 第3层4个 + 第4层4个
       比较次数总和 = 1*1 + 2*2 + 3*4 + 4*4 = 33  →  ASL = 33/11 = 3   */
    const int Lv[11] = {3, 4, 2, 3, 4, 1, 3, 4, 2, 3, 4};
    int total = 0, cntLevel[5] = {0, 0, 0, 0, 0};
    for (int i = 0; i < 11; ++i) {
        int lv = cntAtLevel(a, a[i], 0, 10, 1);      // 查"下标 i 上的值"，就能拿到下标 i 的层号
        total += lv;
        ++cntLevel[lv];
        cout << "a[" << i << "]=" << a[i] << " 层号=" << lv
             << "（表里写的是 " << Lv[i] << "）\n";
    }
    for (int d = 1; d <= 4; ++d)
        cout << "第 " << d << " 层有 " << cntLevel[d] << " 个结点\n";
    cout << "ASL_success = " << total << "/11 = " << (double)total / 11 << "\n";   // 33/11 = 3
    return 0;
}

10.3.3 判定树（比较树）：折半查找的灵魂

折半查找的执行过程可以完整地用一棵二叉树表示，这棵树叫判定树（decision tree） 或比较树（comparison tree）。构造规则只有三条，务必背下来：

1. 取整个区间的 mid 作为根结点（根上写的是元素值，但它的身份是「下标 mid」）；
2. 左子树递归地由左半区间 [left, mid−1] 构造，右子树由右半区间 [mid+1, right] 构造；
3. 区间为空的地方挂一个方形外部结点（失败结点），表示查找不成功。

因为 mid 总是取中点，左右子区间的长度最多相差 1， 所以：折半查找的判定树一定是一棵平衡二叉树 （更准确地说：任一结点的左右子树高度差不超过 1，且所有外部结点只出现在最后两层）。 这个性质可以推出树高：

推导思路：层数为 h 的二叉树最多有 2h − 1 个结点， 要让 n 个内部结点都放得下，需要 2h − 1 ≥ n， 即 h ≥ log2(n+1)，取整得 h = ⌈log2(n+1)⌉。 而折半查找的判定树恰好是「尽量填满」的形状，所以它取到了这个下界—— 这就是折半查找最优的根本原因。

10.3.4 不成功 ASL：把外部结点数清楚

查找不成功时，算法会一路走到某个空区间，对应判定树上的一个外部结点（方形结点）。 有几个空区间？n + 1 个——因为 n 个内部结点把有序数组切成了 n+1 段空隙， 每段空隙对应一个外部结点。等概率假设下，ASL失败 就是所有外部结点深度的平均值。

外部结点的深度怎么数？规则是：外部结点的深度 = 它的父结点（内部结点）的层号 + 1， 也就是「走到那个死胡同之前，一共和多少个元素比过」。 对 n = 11 逐个统计（内部结点分四层，个数 1、2、4、4）：

10.3.5 任意 n 的 ASL 公式

设 h = ⌈log2(n+1)⌉ 为判定树层数。满二叉树情形（n = 2h − 1） 最容易推：第 i 层有 2i−1 个结点，于是

代入 n = 2h − 1 化简得 ASL ≈ h − 1 + 1/n → log2(n+1) − 1。 对一般的 n，判定树的最下面一层没填满，结论仍是：

观察：n = 2^h−1（满树）时 ASL 恰好等于 h − 1 + 1/n，与 log2(n+1) − 1 几乎重合； 非满树时精确值略大于估算值。考试写 ASL ≈ log2(n+1) − 1 一般都给分。

10.3.6 折半查找的局限：为什么需要树和 B 树

折半查找 O(log n) 已经很快了，那为什么还要发明二叉排序树、平衡二叉树、B 树、跳表？ 因为折半查找有三个致命限制：

对应的解决方案（本讲只做地图式介绍，细节留给后续章节）：

10.3.7 复杂度 O(log n) 的推导

为什么折半查找是 O(log n)？两种等价的说法，都要会说：

说法一（区间长度）：设第 t 轮结束后区间长度为 Lt， 初始 L0 = n，每轮砍半 Lt = Lt−1 / 2 = n / 2t。 区间长度为 0（或 1）时结束，即 n / 2t ≤ 1， 解得 t ≥ log2n，所以最多 ⌈log2(n+1)⌉ 轮。

说法二（判定树高度）：每比较一次就下降一层，比较次数 = 结点层号 ≤ 树高 h = ⌈log2(n+1)⌉，因此最坏比较次数是 O(log n)。

10.3.8 折半查找的四个变体

折半查找真正的威力在于「二分」这个思想，而不是「找等于 key 的元素」这一件事。 下面四种变体在竞赛和工程中出现的频率远高于原版：

变体 1：lower_bound —— 第一个 ≥ x 的位置

二分时不提前返回：a[mid] < x 说明 mid 及其左边都不可能是答案，left = mid + 1； 否则 mid 本身可能就是答案，right = mid。循环到 left == right 为止。 这就是 C++ 的 std::lower_bound。

变体 2：upper_bound —— 第一个 > x 的位置

与 lower_bound 只差一个等号：把 a[mid] < x 改成 a[mid] <= x。

变体 3：旋转数组中的查找

数组原本递增，被从某处旋转（如 [4,5,6,7,0,1,2]）。此时数组整体无序， 但 mid 一定把区间分成「一半有序、一半可能无序」。判断哪一半有序，再看 target 是否落在 那一半的值域内，就能决定去哪边。复杂度仍是 O(log n)。这个题是面试高频。

变体 4：二分答案

这是二分思想的终极形态：当答案具有单调性（即「x 可行 ⟹ 所有 > x 也可行」）， 就可以不二分数组，而是二分答案本身： 写一个 check(x) 判定函数，然后在答案值域上二分。 经典例子：木棍切割（切出 k 段等长木棍的最大长度）、 「最小化最大值 / 最大化最小值」类问题、二分 + 图论判定。 第 13 讲会专门展开。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* ================= 变体 1：lower_bound =================
   返回第一个 >= x 的元素下标；若全部 < x，返回 n
   写法要点：循环条件是 left < right，mid 不需要 +1（左闭右开区间） */
int lowerBound(const vector<int>& a, int x) {
    int left = 0, right = (int)a.size();        // 区间 [left, right)
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (a[mid] < x) left = mid + 1;         // mid 及其左边全部 < x
        else            right = mid;            // mid 可能是答案，保留
    }
    return left;
}

/* ================= 变体 2：upper_bound =================
   返回第一个 > x 的元素下标。与 lower_bound 只差一个 "=" */
int upperBound(const vector<int>& a, int x) {
    int left = 0, right = (int)a.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (a[mid] <= x) left = mid + 1;
        else             right = mid;
    }
    return left;
}

/* ================= 变体 3：旋转数组中的查找 =================
   如 {4,5,6,7,0,1,2}：mid 两侧必有一侧是"升序"的，据此判断去哪边 */
int searchRotated(const vector<int>& a, int target) {
    int left = 0, right = (int)a.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (a[mid] == target) return mid;
        if (a[left] <= a[mid]) {                       // 左半段 [left, mid] 有序
            if (a[left] <= target && target < a[mid]) right = mid - 1;
            else                                      left  = mid + 1;
        } else {                                       // 右半段 [mid, right] 有序
            if (a[mid] < target && target <= a[right]) left  = mid + 1;
            else                                       right = mid - 1;
        }
    }
    return -1;
}

/* ================= 变体 4：二分答案 =================
   例题：有 n 根木棍长度 L[i]，要切出 k 段长度相等的木棍，求每段的最大长度（整数）
   单调性：若长度 x 可行，则所有 < x 的长度也可行 → 可以二分 x
   check(x)：每根木棍能切出 L[i]/x 段，总和 >= k 即可行 */
bool check(const vector<int>& L, int k, int x) {
    if (x <= 0) return false;
    long long cnt = 0;
    for (int len : L) cnt += len / x;
    return cnt >= k;
}
int maxPieceLength(const vector<int>& L, int k) {
    int lo = 1, hi = 0;
    for (int len : L) hi = max(hi, len);        // 答案上界：最长的那根
    int ans = 0;
    while (lo <= hi) {                          // 在"答案值域"上二分
        int mid = lo + (hi - lo) / 2;
        if (check(L, k, mid)) { ans = mid; lo = mid + 1; }   // 可行 → 试试更长
        else                    hi = mid - 1;                // 不可行 → 缩短
    }
    return ans;
}

int main() {
    vector<int> a = {1, 3, 3, 5, 5, 5, 7, 9};   // 有序，含重复

    cout << lowerBound(a, 5) << "\n";            // 3（第一个 5）
    cout << upperBound(a, 5) << "\n";            // 6（第一个 > 5）
    cout << upperBound(a, 5) - lowerBound(a, 5) << "\n";   // 3：5 出现 3 次
    cout << lowerBound(a, 8) << "\n";            // 7（值是 9 的位置）
    cout << lowerBound(a, 100) << "\n";          // 8 = n，表示"不存在 >= 100 的元素"

    /* 与标准库结果对照 */
    cout << (lower_bound(a.begin(), a.end(), 5) - a.begin()) << "\n";   // 3
    cout << (upper_bound(a.begin(), a.end(), 5) - a.begin()) << "\n";   // 6

    vector<int> r = {4, 5, 6, 7, 0, 1, 2};
    cout << searchRotated(r, 0) << "\n";         // 4
    cout << searchRotated(r, 3) << "\n";         // -1

    vector<int> L = {802, 743, 457, 539};
    cout << maxPieceLength(L, 11) << "\n";       // 200
    return 0;
}

10.4 插值查找：把 mid 按比例挪一挪

10.4.1 一句话本质

查英文词典时找 "zebra"，你会直接翻到最后几页，而不是从中间开始二分。 为什么？因为你知道单词表是按字母均匀分布的，"z" 一定在后面。 插值查找（interpolation search）就是把这个直觉写成公式： 既然数据大致均匀，mid 就不该取中点，而应该按 key 在值域中的比例来定位置。

拆开看这个式子很好理解：(key − a[low]) / (a[high] − a[low]) 是 「key 在数值轴上位于区间里的第几成」，乘上区间长度 (high − low) 就得到了「下标轴上该走多远」。 当 key 靠近 a[low] 时比例接近 0 → mid 靠近 low； 靠近 a[high] 时比例接近 1 → mid 靠近 high。

10.4.2 为什么均匀分布下能接近 O(log log n)

均匀分布时，a[i] 与下标 i 近似成线性关系， 插值公式算出的 mid 落点与 key 真实位置的偏差服从一个均值为 0 的分布， 标准差的量级是 O(√n)。 每轮把「位置误差」从 n 降到 √n，再降到 n1/4…… 要做多少次才能降到 1？解 n1/2t = 1 得 t = log2log2n，于是：

直观感受一下量级差：n = 109 时， log2n ≈ 30 次，而 log2log2n ≈ 5 次。 代价是：这个好结论几乎只在「数据严格均匀」时才成立， 而真实数据（用户 ID、时间戳、ZIP 码）几乎从不均匀。所以工业界很少直接用插值查找， 它更多作为一个「知道有这回事」的知识点，以及在某些特化场景（如按时间均匀采样的日志）里的优化。

10.4.3 实现要点：除零、越界与 key 超范围

插值查找的代码只有几行，但坑特别多，四个必须处理：

#include <iostream>
#include <vector>
using namespace std;

/* =====================================================================
   插值查找：适用于"关键字大致均匀分布"的有序表
   mid = low + (key − a[low]) / (a[high] − a[low]) × (high − low)
   返回下标，找不到返回 -1
   ===================================================================== */
int interpolationSearch(const vector<long long>& a, long long key, int* cmpCnt = nullptr) {
    int low = 0, high = (int)a.size() - 1, cnt = 0;

    while (low <= high) {
        /* ---- 坑 3：key 超出当前区间的值域，直接判定失败 ---- */
        if (key < a[low] || key > a[high]) { if (cmpCnt) *cmpCnt = cnt; return -1; }

        /* ---- 坑 1：所有值都相同会让分母为 0 ---- */
        if (a[high] == a[low]) {
            ++cnt;
            if (a[low] == key) { if (cmpCnt) *cmpCnt = cnt; return low; }
            if (cmpCnt) *cmpCnt = cnt;
            return -1;
        }

        /* ---- 坑 4：先乘后除 + long long，避免整数截断与溢出 ---- */
        long long pos = low + (key - a[low]) * (long long)(high - low) / (a[high] - a[low]);

        /* ---- 坑 2：clamp，防止浮点式的越界 ---- */
        if (pos < low)  pos = low;
        if (pos > high) pos = high;
        int mid = (int)pos;

        ++cnt;
        if (a[mid] == key) { if (cmpCnt) *cmpCnt = cnt; return mid; }
        else if (a[mid] < key) low  = mid + 1;
        else                   high = mid - 1;
    }
    if (cmpCnt) *cmpCnt = cnt;
    return -1;
}

int main() {
    /* ---------- 测试 1：均匀数据（等差），插值查找的主场 ---------- */
    vector<long long> uni;
    for (int i = 0; i < 11; ++i) uni.push_back(1 + 10LL * i);   // 1,11,...,101

    int c1 = 0, c2 = 0;
    cout << "均匀数据查 31 → 下标 " << interpolationSearch(uni, 31, &c1)
         << "，比较 " << c1 << " 次\n";                       // 3，1 次

    /* 折半查找对照 */
    {
        int lo = 0, hi = 10; c2 = 0;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2; ++c2;
            if (uni[mid] == 31) break;
            if (uni[mid] < 31) lo = mid + 1; else hi = mid - 1;
        }
        cout << "折半查找查 31 → 比较 " << c2 << " 次\n";          // 4 次
    }

    /* ---------- 测试 2：指数分布，插值查找的滑铁卢 ---------- */
    vector<long long> expo;
    for (int i = 0; i < 11; ++i) expo.push_back(1LL << i);      // 1,2,4,...,1024
    int c3 = 0;
    cout << "指数数据查 3（不存在）→ " << interpolationSearch(expo, 3, &c3)
         << "，比较 " << c3 << " 次\n";                       // -1，却要比较 2 次
    /* 注意：这里因为"key > a[high] 就返回"和 clamp，比较次数看起来不多，
       但请把 key 换成 513 这种"卡在中间"的值再试，你会看到 mid 每次只挪一格。 */

    int c4 = 0;
    cout << "指数数据查 513 → " << interpolationSearch(expo, 513, &c4)
         << "，比较 " << c4 << " 次\n";

    /* ---------- 测试 3：全相同元素（除零坑） ---------- */
    vector<long long> same(5, 7);
    int c5 = 0;
    cout << "全 7 的表查 7 → " << interpolationSearch(same, 7, &c5) << "，比较 " << c5 << " 次\n";
    cout << "全 7 的表查 9 → " << interpolationSearch(same, 9, &c5) << "\n";
    return 0;
}

下面动画把同一组数据上的插值查找与折半查找并排跑一遍，注意看两者的 mid 怎么走：

10.5 斐波那契查找：只用加减法的黄金分割

10.5.1 为什么用斐波那契数列划分

斐波那契查找（Fibonacci search）是折半查找的一个变体，它把「砍一半」换成 按黄金分割比 0.618 划分。两个理由：

• 数学上更优的分割点：斐波那契数列相邻两项之比 F[k−1]/F[k] 收敛到 1/φ ≈ 0.618。理论上可以证明，在最坏情况下黄金分割是「平均比较次数」意义下的最优划分比例 （0.618 与 0.5 的差别很小，所以提升有限）。
• 计算上更便宜：mid = low + F[k−1] − 1 只用加减法， 而折半查找要 (low + high) / 2（一次加法 + 一次除法或移位）， 插值查找更狠（乘除法各一次）。 在早期 CPU 上除法要几十个时钟周期；即使今天，在把除法做到很慢的嵌入式芯片上， 斐波那契查找仍有价值。

换来的代价是：需要预先算一张斐波那契表，还要把数组「补齐」到特定长度，实现更啰嗦。 所以工程里几乎没人用它——它是典型的「考试 / 教材知识点」。

10.5.2 算法步骤与「补齐」过程

完整流程分三步，第二步「补齐」是理解的关键：

1. 找 F[k]：找出满足 F[k] − 1 ≥ n 的最小斐波那契数 F[k]；
2. 补齐数组：把数组长度从 n 扩到 F[k] − 1， 多出来的位置全部填原数组的最后一个元素（因为有序，填最后一个不会破坏有序性）；
3. 迭代：令 mid = low + F[k−1] − 1，比较后按分支调整 low / high 与 k（下面详述）。

10.5.3 mid 公式的推导与 k 的调整规则

为什么是 mid = low + F[k−1] − 1？因为我们要让 mid 恰好把长度 F[k] − 1 的区间切成 (F[k−1] − 1) + 1 + (F[k−2] − 1)。 mid 自己是第 1 个，左边要放 F[k−1] − 1 个元素， 所以 mid 相对 low 的偏移是 F[k−1] − 1，即 mid = low + F[k−1] − 1。用 n = 11、k = 7 验算：mid = 0 + F[6] − 1 = 0 + 8 − 1 = 7， 左块下标 0~6 共 7 = F[6] − 1 个，右块下标 8~11 共 4 = F[5] − 1 个。完美。

三分支与 k 的调整：

10.5.4 完整 C++ 实现

#include <bits/stdc++.h>
using namespace std;

/* =====================================================================
   斐波那契查找（Fibonacci search）—— 竞赛写法：全局数组 + 自由函数
   1) 预处理斐波那契数列，找最小的 k 使 F[k] - 1 >= n
   2) 把数组补齐到 F[k] - 1，多出的位置填原数组最后一个元素
   3) mid = low + F[k-1] - 1；往左 k -= 1，往右 k -= 2（关键！不是 k -= 1）
   前提：有序 + 顺序存储。平均性能略优于折半查找，最坏同为 O(log n)。
   数组大小依据：MAXN = 1e5 + 5 够放 1e5 个元素；F[45] 已是 11 亿，MAXF 取 64 绰绰有余
   ===================================================================== */

const int MAXN = 100005;      // 主表容量（按题目 n <= 1e5 开）
const int MAXF = 64;          // 斐波那契表容量

int a[MAXN];                  // 待查找的有序表，元素在 a[0..n-1]
int F[MAXF];                  // F[0]=0, F[1]=1, F[2]=1, F[3]=2, F[4]=3, ...
int fsz = 0;                  // 斐波那契表实际长度

/* ---------- 预处理斐波那契数列，直到最后一项 >= maxN ---------- */
void buildFib(int maxN) {
    F[0] = 0; F[1] = 1; fsz = 2;
    while (F[fsz - 1] < maxN && fsz < MAXF - 1) {
        F[fsz] = F[fsz - 1] + F[fsz - 2];
        ++fsz;
    }
}

/* ---------- 斐波那契查找：返回下标，找不到返回 -1；cmpCnt 输出比较次数 ---------- */
int fibSearch(int n, int key, int *cmpCnt = nullptr) {
    if (cmpCnt) *cmpCnt = 0;
    if (n == 0) return -1;

    /* ---- 第 1 步：找最小的 k 使 F[k] - 1 >= n ---- */
    int k = 2;
    while (k < fsz && F[k] - 1 < n) ++k;
    if (k >= fsz || F[k] - 1 > MAXN) return -1;          // 斐波那契表 / 数组不够大

    /* ---- 第 2 步：补齐到 F[k] - 1，多出来的位置复制最后一个元素 ---- */
    static int t[MAXN];
    int len = F[k] - 1;
    for (int i = 0; i < n; ++i) t[i] = a[i];
    for (int i = n; i < len; ++i) t[i] = a[n - 1];       // 有序性不受影响

    int low = 0, high = n - 1, cnt = 0;                  // high 始终是"原数组"的右界
    while (low <= high) {
        int mid = low + F[k - 1] - 1;                    // 核心公式：左边恰好留 F[k-1]-1 个
        if (mid >= len) mid = len - 1;                   // 兜底，正常不会触发
        ++cnt;
        if (key < t[mid]) {
            high = mid - 1;
            k -= 1;                                      // 左块：长度 F[k-1]-1
        } else if (key > t[mid]) {
            low = mid + 1;
            k -= 2;                                      // 右块：长度 F[k-2]-1（关键！）
        } else {
            if (cmpCnt) *cmpCnt = cnt;
            return mid < n ? mid : n - 1;                // 落在补齐区 → 映射回最后一个元素
        }
        if (k < 1) break;                                // 防越界
    }
    if (cmpCnt) *cmpCnt = cnt;
    return -1;
}

int main() {
    buildFib(2000);
    printf("F = ");
    for (int i = 1; i <= 10; ++i) printf("%d ", F[i]);   // 1 1 2 3 5 8 13 21 34 55
    printf("\n");

    int init[11] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110};   // n = 11
    int n = 11;
    for (int i = 0; i < n; ++i) a[i] = init[i];

    int c = 0, pos = 0;
    pos = fibSearch(11, 10, &c);
    printf("查 10  → 下标 %d，比较 %d 次\n", pos, c);
    pos = fibSearch(11, 70, &c);
    printf("查 70  → 下标 %d，比较 %d 次\n", pos, c);
    pos = fibSearch(11, 110, &c);
    printf("查 110 → 下标 %d，比较 %d 次\n", pos, c);
    pos = fibSearch(11, 75, &c);
    printf("查 75  → 下标 %d，比较 %d 次\n", pos, c);
    pos = fibSearch(11, 5, &c);
    printf("查 5   → 下标 %d，比较 %d 次\n", pos, c);
    return 0;
}

10.5.5 三种查找方法的对比

10.6 分块查找：块间有序、块内无序

10.6.1 一句话本质与索引表

分块查找（block search）又叫索引顺序查找（indexed sequential search）， 它的本质是一句话：把表切成若干块，块与块之间有序，块内部无序； 先查索引表定位到块，再在块内顺序查找。

它要求把数据组织成两部分：

• 主表：n 个元素被均分成 b 块（最后一块可能不满），每块有 s 个元素（块长）；
• 索引表：b 个表项，第 i 项记录「第 i 块的最大关键字」以及「第 i 块的起始下标」。

「块间有序」的准确含义是：第 i 块中的所有关键字都小于第 i+1 块中的最小关键字。 注意它不要求块内有序——这正是分块查找区别于「归并」的地方， 也是它能兼顾「插入方便」的原因：往块内随便一塞即可（只要不破坏块间有序）。

10.6.2 ASL 推导：为什么最优块长是 √n

设表长 n，均分为 b 块，每块 s 个元素，则 n = b × s。 在「各元素等概率被查找」以及「key 落在各块的概率相等」的假设下，查找代价由两段组成：

• 索引查找：如果索引表用顺序查找，找到第 i 块平均要 (b+1)/2 次比较； 如果用折半查找，约 ⌈log2(b+1)⌉ 次。
• 块内查找：块内无序 → 只能用顺序查找，平均 (s+1)/2 次。

把 b = n/s 代入，得到一个关于 s 的函数，求最小值：

由均值不等式 n/s + s ≥ 2√n（等号在 n/s = s 即 s = √n 时成立），所以：

例如 n = 10000：顺序查找要 5000 次，折半要 14 次，分块只要 √10000 + 1 = 101 次。 它不如折半，但分块查找的插入删除比折半便宜得多（只需在块内找位置搬移局部元素）， 这就是它存在的价值。

如果把索引表也换成折半查找（索引表本身是有序的，完全可以）：

这时最优块长不再是 √n，而应让「索引层数」与「块内长度」平衡， 理论最优满足 s ≈ ln 2 · log2n，但考试一般不深究， 记住「顺序索引时 s = √n、ASL ≈ √n + 1」就够了。

10.6.3 C++ 实现：索引表 + 块内顺序 / 折半查找

#include <bits/stdc++.h>
using namespace std;

/* =====================================================================
   分块查找（索引顺序查找）—— 竞赛写法：全局数组 + 自由函数
   - 主表分成 b 块，每块 s 个元素；块间有序（后一块的最小值 > 前一块的最大值）
   - 块内无序 → 块内只能顺序查找；若块内也有序，可把 findInBlock 换成折半
   - 索引表存每块的最大关键字 idxMax[] 与起始下标 idxStart[]
   - 核心结论：ASL = ASL索引 + ASL块内；
     顺序查找索引时最优块长 s = √n，此时 ASL ≈ √n + 1（两段各 √n/2 与 s/2 相加取最小）
   返回 (块号, 块内偏移)，失败返回 (-1, -1)
   数组大小依据：MAXN = 1e5 + 5 放主表；MAXB = 1005 够放 √(1e5) ≈ 317 个块
   ===================================================================== */

const int MAXN = 100005;   // 主表容量
const int MAXB = 1005;     // 索引表（块数）容量

int dat[MAXN];             // 主表：各块首尾相接拼在一起
int idxMax[MAXB];          // 索引表：第 i 块的最大关键字
int idxStart[MAXB];        // 索引表：第 i 块在主表中的起始下标
int blen[MAXB];            // 第 i 块的实际长度
int bcnt = 0;              // 块数 b
int n = 0;                 // 主表元素个数 n

/* ---------- 建索引表：把 dat[0..n-1] 每 s 个切成一块 ---------- */
void buildBlocks(int s) {
    bcnt = 0;
    for (int st = 0; st < n; st += s) {
        int len = min(s, n - st);                 // 最后一块可能不满
        int mx = dat[st];
        for (int i = st + 1; i < st + len; ++i) mx = max(mx, dat[i]);
        idxStart[bcnt] = st;
        blen[bcnt] = len;
        idxMax[bcnt] = mx;                        // 索引项 = 该块最大关键字
        /* 块间有序的校验：第 i 块的最大值必须小于第 i+1 块的最小值 */
        if (bcnt > 0 && idxMax[bcnt] < idxMax[bcnt - 1])
            printf("警告：块 %d 破坏了块间有序！\n", bcnt);
        ++bcnt;
    }
}

/* ---------- ① 索引表用顺序查找：ASL_index = (b+1)/2 ---------- */
int locateSeq(int key) {
    for (int i = 0; i < bcnt; ++i)
        if (key <= idxMax[i]) return i;           // 第一个"能吃下"key 的块
    return -1;
}

/* ---------- ② 索引表用折半查找：ASL_index = ⌈log2(b+1)⌉ ---------- */
int locateBinary(int key) {
    int lo = 0, hi = bcnt - 1, ans = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (idxMax[mid] >= key) { ans = mid; hi = mid - 1; }   // 记录并继续往左找
        else lo = mid + 1;
    }
    return ans;
}

/* ---------- 块内顺序查找，返回"块内偏移"，找不到返回 -1 ---------- */
int findInBlock(int b, int key) {
    for (int i = idxStart[b]; i < idxStart[b] + blen[b]; ++i)
        if (dat[i] == key) return i - idxStart[b];
    return -1;
}

/* ---------- 两种索引方式的两段式查找：先定块，再块内找 ---------- */
pair<int, int> searchSeqIndex(int key) {          // ① 顺序索引版
    int b = locateSeq(key);
    if (b < 0) return make_pair(-1, -1);
    int off = findInBlock(b, key);
    return off < 0 ? make_pair(-1, -1) : make_pair(b, off);
}

pair<int, int> searchBinIndex(int key) {          // ② 折半索引版
    int b = locateBinary(key);
    if (b < 0) return make_pair(-1, -1);
    int off = findInBlock(b, key);
    return off < 0 ? make_pair(-1, -1) : make_pair(b, off);
}

void printIndex() {
    printf("索引表（块间有序）：\n");
    for (int i = 0; i < bcnt; ++i)
        printf("  块%d: maxKey=%-3d start=%-3d len=%d\n", i, idxMax[i], idxStart[i], blen[i]);
}

int main() {
    /* 块间有序、块内无序：n = 16, b = 4, s = 4 */
    int init[16] = {22, 12, 13,  8,        // 第 0 块，max = 22
                    33, 48, 25, 30,        // 第 1 块，max = 48
                    60, 86, 71, 55,        // 第 2 块，max = 86
                    99, 95, 88, 90};       // 第 3 块，max = 99
    n = 16;
    for (int i = 0; i < n; ++i) dat[i] = init[i];
    buildBlocks(4);
    printIndex();

    int keys[5] = {48, 8, 99, 50, 100};
    for (int i = 0; i < 5; ++i) {
        int key = keys[i];
        pair<int, int> r1 = searchSeqIndex(key);
        pair<int, int> r2 = searchBinIndex(key);
        printf("key=%-4d 顺序索引 → 块%d 内偏移%d    折半索引 → 块%d 内偏移%d\n",
               key, r1.first, r1.second, r2.first, r2.second);
    }

    /* 理论 ASL：n = 16, s = 4, b = 4
       ASL = (b+1)/2 + (s+1)/2 = 2.5 + 2.5 = 5，与最优块长 s = √n 时的 √n + 1 = 5 吻合 */
    printf("理论 ASL(顺序索引) = (4+1)/2 + (4+1)/2 = %.1f\n", (4 + 1) / 2.0 + (4 + 1) / 2.0);
    printf("理论 ASL(√n+1)     = √16 + 1 = %.1f\n", sqrt(16.0) + 1);
    return 0;
}

10.7 哈希表：用计算代替比较

10.7.1 一句话本质与核心术语

前面所有查找方法都建立在「比较」之上，所以有 O(log n) 的下界（基于比较的查找下界是 Ω(log n)）。哈希表（散列表，hash table）跳出了这个框： 它不去比较，而是用哈希函数把关键字直接算成一个存储地址，一步到位。

先把术语钉死，后面的所有讨论都建立在这些词上：

哈希函数 / 散列函数 H(key)

把关键字映射为存储位置的函数。它把关键字空间（可能极大，如所有 18 位身份证号）压缩到地址空间 [0, m−1]。

哈希地址 / 散列地址

H(key) 算出来的值，也就是数组下标。哈希表本身就是一个「以哈希地址为下标」的数组。

冲突 / 碰撞（collision）

key1 ≠ key2 但 H(key1) == H(key2)。这是必然会发生的——由鸽巢原理，只要关键字空间比地址空间大，就一定有两个不同关键字落到同一地址。

同义词（synonym）

发生冲突的那些关键字互称同义词。注意是「互相」的，是一个等价关系。

装填因子（load factor）α

α = 表中已存元素个数 n / 哈希表长度 m。它衡量表的「拥挤程度」，是决定哈希表性能的唯一核心参数。

10.7.2 六种哈希函数的构造方法

下面六种方法全部要会写公式、会举例子、会说优缺点。先看总表，再逐个展开。

① 直接定址法：H(k) = a·k + b

取关键字的某个线性函数作为哈希地址。a、b 是常数（a ≠ 0）。 最朴素的形态是 H(k) = k（即 a = 1, b = 0）， 例如「统计 1~120 岁的人口数」，直接开一个 cnt[121] 数组，年龄就是下标。

优点：绝对不会有冲突（一一映射），计算最快，查找就是数组随机访问。 缺点：要求关键字集合连续、紧凑；如果关键字是 {1, 1000000, 99999999} 这种， 数组就得开到一亿，空间爆炸。 适用：关键字基数小且连续分布——字符（ASCII 0~127）、月份、年龄段、身份证前 6 位的地区码。

② 除留余数法：H(k) = k mod p —— 最常用

这是工程与考试中出现频率最高的方法。它的思想是「取模把任意大的关键字折叠进 [0, p−1]」。 关键在 p 怎么选，这里有三个必须知道的结论：

• p 一般取不大于表长 m 的最大质数。 例如 m = 13 时取 p = 13；m = 16 时取 p = 13（不大于 16 的最大质数）； 再比如 m = 25 取 p = 23。这就是本章大量使用 m = 11、m = 13 作为表长的原因——它们本身就是质数。
• 为什么用质数？因为若 p 有小的因子 d， 那么所有「相差 d 的倍数」的关键字都会撞到一起。 最典型的是 p 取偶数：若 p = 2t， 那么 H(k) 只取决于 k 的最低 t 位， 高位全部被丢掉。而真实数据（学号、编号、内存地址）的低位常常高度规律 （比如都是 0、都是 00 结尾），结果就是灾难性的聚集。
• 为什么特意避开 2 的幂？编译器把 k % 2t 优化成 k & (2t−1)， 快是快，但只保留低位。Java 的 HashMap 就故意用 2 的幂做容量（为了用位运算加速）， 代价是必须额外做一次扰动：h ^= (h >>> 16) 把高位混进低位。 这正是「用质数」和「用 2 的幂 + 扰动」两条技术路线的分野。

③ 数字分析法：挑出「随机」的那几位

如果关键字是多位数（如学号 2023011307），而我们已经知道全体关键字， 就可以分析每一位的分布：把分布均匀的位抽出来组成地址，把取值集中、重复率高的位扔掉。

例：某班级 30 人的学号形如 2023 01 13 07（年级 + 学院 + 班级 + 序号）。 年级位全是 2023，学院位只有两种取值——这两段扔掉； 班级位和序号位变化丰富——取这两段拼成 1307，再对表长取模。

优点：计算几乎为零（只是取位拼接），针对特定数据能做得非常均匀。 缺点：完全依赖「事先知道全体关键字」，是静态方法；一旦新增的关键字破坏了原来均匀的那几位， 性能立刻崩掉。适用：数据仓库、统计报表这类一次性建表的场景。

④ 平方取中法：让每一位都参与运算

先算 k2，再取中间的若干位作为地址。 例：k = 4731，k2 = 22382361， 取中间 3 位（第 3~5 位）得 382。

为什么取中间位？因为一个数的平方，中间部分受所有输入位的影响—— 低位只受 k 的低位影响，高位只受高位影响，都不够「混合」。 取中间位相当于做了一次廉价的「雪崩」。 适用：关键字位数不多、分布未知，又不想做昂贵的除法。经典应用是 早期编译器符号表的哈希、以及某些随机数发生器（middle-square method）。

⑤ 折叠法：把长关键字「折叠」成短地址

把关键字按固定位数（比如 3 位）切成若干段，然后把各段相加，取和的后几位作为地址。 按叠加方式分两种：

• 移位折叠（shift folding）：各段对齐后直接相加。
• 分界折叠（folding at the boundaries）：奇数段（或偶数段）反向后再相加， 让不同段的不同位也参与进位，混合更充分。

例：k = 123456789，按 3 位分段得 123 | 456 | 789。 移位折叠：123 + 456 + 789 = 1368，取后 3 位 368； 分界折叠：把中间段反向得 123 | 654 | 789，123 + 654 + 789 = 1566， 取后 3 位 566。

适用：关键字位数远大于地址位数——超长身份证号、UUID、哈希串、IP 地址 + 端口。 优点：不需要除法，也不需要事先知道全体数据； 缺点：分段长度和叠加方式需要调参，否则某一段的规律会直接传递到地址里。

⑥ 随机数法：用伪随机函数打散

H(k) = random(k)，其中 random 是一个以 k 为种子的确定性伪随机函数 （同样的 k 必须给出同样的结果，否则找不到）。例如 H(k) = (k × 2654435761u) mod m （这就是著名的 Knuth 乘法散列，乘的是一个接近 232/φ 的奇数）。

适用：关键字长度参差不齐、分布完全未知，尤其适合对抗性场景—— 如果哈希函数是公开且确定的，攻击者可以精心构造一堆全部冲突的关键字， 把你的哈希表退化成链表，造成 DoS（这叫 hash flooding 攻击）。 解决办法就是每次程序启动随机换一个种子，让攻击者无法预测。 C++ 的 std::unordered_map 用 std::hash（确定性，会被卡）， 而 Python / Rust 的字典默认使用随机种子（Python 的 PYTHONHASHSEED 就是这个）。

#include <iostream>
#include <string>
#include <cstdint>
using namespace std;

/* =====================================================================
   六种哈希函数的构造方法，统一返回 [0, m-1] 的地址
   ===================================================================== */

/* ---------- ① 直接定址法：H(k) = a*k + b ---------- */
// 优点：绝无冲突，O(1)；缺点：要求关键字连续紧凑，否则空间爆炸
int hDirect(int key, int a = 3, int b = 7) { return a * key + b; }

/* ---------- ② 除留余数法：H(k) = k mod p，p 取 ≤ m 的最大质数 ---------- */
bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; (long long)i * i <= x; ++i)
        if (x % i == 0) return false;
    return true;
}
int largestPrimeLE(int m) {                 // 不大于 m 的最大质数
    for (int p = m; p >= 2; --p) if (isPrime(p)) return p;
    return 2;
}
int hMod(int key, int p) { return ((key % p) + p) % p; }   // 处理负数

/* ---------- ③ 数字分析法：抽取分布均匀的位 ---------- */
// 例：学号 2023 01 13 07，年级位与学院位是常量 → 只取"班级+序号"两位十进制
int hDigitAnalysis(int studentNo) {
    int cls = (studentNo / 100) % 100;      // 班级两位
    int seq = studentNo % 100;              // 序号两位
    return cls * 100 + seq;                 // 得到 0..9999 的地址
}

/* ---------- ④ 平方取中法：取 k*k 的中间若干位 ---------- */
int hMidSquare(int key, int digits = 3) {
    long long sq = (long long)key * key;
    long long mod = 1;
    for (int i = 0; i < digits; ++i) mod *= 10;
    /* 去掉低 digits 位后再取 digits 位 → 等价于取"中间" */
    return (int)((sq / mod) % mod);
}

/* ---------- ⑤ 折叠法：按 3 位分段相加 ---------- */
int hFoldShift(int key) {                    // 移位折叠
    int sum = 0;
    while (key > 0) { sum += key % 1000; key /= 1000; }
    return sum % 1000;
}
int hFoldBoundary(int key) {                 // 分界折叠：交替反向
    int seg[16], n = 0;
    while (key > 0) { seg[n++] = key % 1000; key /= 1000; }
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        if (i % 2 == 1) {                    // 奇数段反向
            int v = seg[i], rev = 0;
            while (v > 0) { rev = rev * 10 + v % 10; v /= 10; }
            sum += rev;
        } else sum += seg[i];
    }
    return sum % 1000;
}

/* ---------- ⑥ 随机数法（Knuth 乘法散列，确定性的伪随机） ---------- */
uint32_t hRandom(uint32_t key, uint32_t seed = 0x9E3779B9u) {
    uint32_t h = key * 2654435761u;          // 2654435761 ≈ 2^32 / φ
    h ^= h >> 16;
    h *= seed;                               // 随机种子，防对手构造
    h ^= h >> 13;
    return h;
}

int main() {
    cout << "① 直接定址 H(25) = " << hDirect(25) << "\n";                 // 82

    int p = largestPrimeLE(16);
    cout << "② 表长 16 → 取质数 p = " << p << "\n";                      // 13
    cout << "   H(41) = " << hMod(41, p) << "  H(53) = " << hMod(53, p)
         << "  H(30) = " << hMod(30, p) << "\n";                        // 2 1 4

    cout << "③ 数字分析 2023011307 → " << hDigitAnalysis(2023011307) << "\n";   // 1307

    cout << "④ 平方取中 4731 → " << hMidSquare(4731) << "\n";              // 22382361 → 382
    cout << "   平方取中 1234 → " << hMidSquare(1234) << "\n";              // 1522756 → 522

    cout << "⑤ 移位折叠 123456789 → " << hFoldShift(123456789) << "\n";    // 123+456+789=1368 → 368
    cout << "   分界折叠 123456789 → " << hFoldBoundary(123456789) << "\n"; // 123+654+789=1566 → 566

    cout << "⑥ 随机数法 H(1000) = " << (hRandom(1000) % 100) << "\n";
    cout << "   同一 key 结果稳定： " << (hRandom(1000) == hRandom(1000)) << "\n";   // 1
    return 0;
}

10.7.3 处理冲突（一）：开放定址法

开放定址法（open addressing）的核心思想：所有元素都直接存在哈希表数组里， 一旦 H(key) 被占了，就按照某个「探测序列」在表里另找一个空位。 地址公式统一写成：

不同的 di 就是不同的探测方法：

线性探测法与堆积现象

线性探测就是「这个位子被占了，就去下一个位子；还占着就再下一个」， 到表尾就绕回表头（mod m 自动完成回转）。

堆积（clustering，又称聚集 / 二次聚集）是它最致命的缺陷： 不同的关键字因为探测路径互相重叠，会连成一大片连续的占用区。 一旦形成连续块，任何哈希到这块内任意位置的关键字，都要一路探测到块尾， 于是块越滚越长、越长越慢，形成正反馈。

下面动画逐帧演示这 9 个关键字的每一次探测。注意插入 67 和 42 时那两条越接越长的探测链—— 42 一连失败了 7 次才找到空位，这正是「堆积」最直观的后果：

平方探测法：为什么表长要是 4j+3 的质数

平方探测（二次探测）的探测序列是 0, 1, −1, 4, −4, 9, −9, …， 即 di = ±i2。它不像线性探测那样只往一个方向挤， 而是左右跳着找，因此不会形成连续的堆积块，只是可能形成「同类关键字扎堆」的 二次聚集（secondary clustering）——因为探测序列只取决于起始地址 H(k)。

但它带来一个新问题：能不能保证探测到表里所有位置？答案取决于表长：

另外还有一个实用的「经验定理」：只要表长是质数且装填因子 α ≤ 0.5， 平方探测一定能插入成功（一定能找到空位）。 这就是为什么很多库把开放定址的阈值定得比 0.75 更低。

下面动画把同一串关键字分别用线性探测与平方探测插入，逐格对比探测路径：

再散列法与伪随机序列法

再散列法（双散列，double hashing）用第二个哈希函数决定探测步长： Hi = (H1(k) + i·H2(k)) mod m。 关键要求是 H2(k) 必须与 m 互质， 否则探测序列会在某个真子集里循环。 常用做法：H2(k) = p − (k mod p)，p 取小于 m 的质数。

它的好处是：不同的 key 有不同的步长，所以哪怕起始地址相同， 探测路径也会迅速岔开——这就同时消除了「一次聚集」和「二次聚集」， 是开放定址法里性能最好的一种，代价是每次探测要多算一个哈希函数。

伪随机序列法把 di 取成一个固定的伪随机序列 （如 d = {1, 5, 3, 9, 2, …}）。因为序列是确定的， 所以插入和查找能用同一条路径，逻辑上是自洽的。 它的优点是「看起来毫无规律」，对手很难构造出全部冲突的输入； 缺点是丧失局部性，每次探测都可能跳到很远的 cache line，实际跑起来不一定快。

删除操作：必须使用墓碑标记

墓碑的代价是：长期运行后表里会积累大量墓碑，导致查找路径变长、真实负载升高。 工程上的解决办法是定期重建（rehash）：扫一遍表把所有有效元素重新插入一个新表， 顺便把墓碑全部清掉、把表扩容或缩容。

开放定址法完整 C++ 实现（线性探测 + 平方探测）

#include <bits/stdc++.h>
using namespace std;

/* =====================================================================
   开放定址 —— 线性探测法（linear probing）。竞赛写法：全局数组 + 自由函数
   H_i = ( H(key) + i ) mod m ，i = 0,1,2,...（冲突就一个一个往后数）
   槽位三态：EMPTY 从未用过 / OCCUPIED 有元素 / DELETED 墓碑
   删除必须打墓碑（tombstone）！直接置空会截断别人的探测链。
   缺点：堆积现象（一次聚集 primary clustering）—— 被占的槽会连成一片，
         这片越长越容易"吸住"后面的冲突，α 一高 ASL 就急剧上升
         （成功 ≈ ½(1 + 1/(1-α))，失败 ≈ ½(1 + 1/(1-α)²)），所以实践上要求 α ≤ 0.75。
   表长 m 取质数：本段用 m = 11 方便和正文的 ASL 手推对齐；
   竞赛里开大表常写成 const int M = 100003;（1e5 级别的质数）。
   ===================================================================== */

const int M = 11;                    // 表长 m，取质数（11 是质数）
const int EMPTY = 0, OCCUPIED = 1, DELETED = 2;

int h[M];                            // 槽位里存的关键字
int st[M];                           // 每个槽位的状态：EMPTY / OCCUPIED / DELETED
int cnt = 0;                         // 有效元素个数 n，装填因子 α = cnt / M
int tomb = 0;                        // 墓碑个数（墓碑会让查找路径变长）
bool verbose = false;                // 打开后打印每一次探测的过程

/* ---------- 哈希函数：除留余数法，顺便把负数掰成正的 ---------- */
int hashOf(int k) { return ((k % M) + M) % M; }

double loadFactor() { return (double)cnt / M; }

/* ---------- 插入：返回最终落点下标；-1 表示探测一圈都没有空位 ---------- */
int insertKey(int k) {
    int hh = hashOf(k);
    for (int i = 0; i < M; ++i) {
        int pos = (hh + i) % M;                        // 线性探测：d_i = i
        if (verbose)
            printf("    探测 i=%d → pos %d%s\n", i, pos,
                   st[pos] == OCCUPIED ? "（占用，冲突）"
                 : st[pos] == DELETED  ? "（墓碑，可复用）" : "（空，放入）");
        if (st[pos] == OCCUPIED && h[pos] == k) return pos;    // 已存在，不重复插
        if (st[pos] != OCCUPIED) {                     // EMPTY 或 DELETED 都能放
            if (st[pos] == DELETED) --tomb;            // 顺手清掉一个墓碑
            h[pos] = k; st[pos] = OCCUPIED; ++cnt;
            return pos;
        }
    }
    return -1;                                         // 表满
}

/* ---------- 查找：返回下标，找不到返回 -1；cmpCnt 输出比较次数 ---------- */
int findKey(int k, int *cmpCnt = nullptr) {
    int hh = hashOf(k), c = 0;
    for (int i = 0; i < M; ++i) {
        int pos = (hh + i) % M;
        ++c;                                           // 访问一个槽位 = 一次比较
        if (st[pos] == EMPTY) {                        // 真空位 → 探测链断了，肯定没有
            if (cmpCnt) *cmpCnt = c;
            return -1;
        }
        if (st[pos] == OCCUPIED && h[pos] == k) {
            if (cmpCnt) *cmpCnt = c;
            return pos;
        }
        /* DELETED 既不算匹配也不算终止，继续往下探 —— 这就是墓碑的作用 */
    }
    if (cmpCnt) *cmpCnt = c;
    return -1;
}

/* ---------- 删除：打墓碑，绝不置 EMPTY ---------- */
bool eraseKey(int k) {
    int pos = findKey(k);
    if (pos < 0) return false;
    st[pos] = DELETED;                                 // 关键的一行！
    ++tomb; --cnt;
    return true;
}

void dumpTable(const char *title) {
    printf("%s（n=%d，α=%.2f，墓碑=%d）\n  ", title, cnt, loadFactor(), tomb);
    for (int i = 0; i < M; ++i) {
        if (st[i] == OCCUPIED)      printf("[%d]%d ", i, h[i]);
        else if (st[i] == DELETED)  printf("[%d]墓碑 ", i);
        else                        printf("[%d]空 ", i);
    }
    printf("\n");
}

int main() {
    int keys[9] = {22, 41, 53, 46, 30, 13, 1, 67, 42};

    verbose = true;
    for (int i = 0; i < 9; ++i) {
        printf("插入 %d（H=%d）：\n", keys[i], keys[i] % M);
        insertKey(keys[i]);
    }
    verbose = false;

    /* 实测最终表：0:22 1:1 2:46 3:13 4:67 5:42 6:空 7:空 8:41 9:53 10:30
       42 插入时探测链为 9✗10✗0✗1✗2✗3✗4✗5✓，共比较 8 次（同一约定下即查找它的成功比较次数）
       各 key 的成功比较次数：22:1  41:1  53:1  46:1  30:3  13:2  1:1  67:4  42:8
       成功 ASL 的分母是 n（表中元素个数），所以 ASL_success = 22/9 ≈ 2.44 */
    dumpTable("最终表：");

    int c = 0, total = 0, n = 0;
    for (int i = 0; i < 9; ++i)
        if (findKey(keys[i], &c) >= 0) { total += c; ++n; }
    printf("ASL_success = %d/%d = %.2f\n", total, n, (double)total / n);

    /* ---------- 演示墓碑的必要性 ---------- */
    printf("\n---- 删除 53（9 号位）----\n");
    eraseKey(53);
    dumpTable("删除后：");                             // 9 号位变成墓碑
    int p = findKey(30, &c);                           // 30 住在 10 号位，必须穿过墓碑才找得到
    printf("查找 30 → 下标 %d，比较 %d 次\n", p, c);
    printf("（如果删除时把 9 号位置成 EMPTY，这里会返回 -1，30 就「消失」了）\n");

    /* ---------- 删除后重算成功 ASL：22:1 41:1 46:1 30:3 13:2 1:1 67:4 42:8 = 21/8 ≈ 2.62 ---------- */
    total = 0; n = 0;
    for (int i = 0; i < 9; ++i) {
        if (keys[i] == 53) continue;                   // 53 已被删除
        if (findKey(keys[i], &c) >= 0) { total += c; ++n; }
    }
    printf("删除 53 后 ASL_success = %d/%d = %.2f\n", total, n, (double)total / n);

    /* ---------- 统计不成功 ASL：分母是 m，约定「从每个哈希地址出发探到 EMPTY 为止」 ---------- */
    int failTotal = 0;
    for (int start = 0; start < M; ++start) {
        int i = 0;
        while (true) {
            int pos = (start + i) % M;
            ++i;
            if (st[pos] == EMPTY) break;               // 墓碑不算停
            if (i > M) break;
        }
        failTotal += i;
    }
    printf("ASL_fail = %d/%d = %.2f\n", failTotal, M, (double)failTotal / M);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

/* =====================================================================
   开放定址 —— 平方探测法（quadratic probing）。竞赛写法：全局数组 + 自由函数
   探测序列：d = 0, +1, -1, +4, -4, +9, -9, ...
   地址：pos = ( H(key) + d ) mod m
   重要结论：m 取 4j+3 形式的质数（7,11,19,23,31,43...）时，
             前 m 个探测位置恰好覆盖全表，保证一定能插入；
             若 m 是 4j+1 型质数（13,29...）则只能覆盖一半位置。
   优点：跳跃式探测打散了堆积，不会出现线性探测那样越长越"吸冲突"的一次聚集；
         但起点相同的 key 仍走同一条探测序列，这叫二次聚集（secondary clustering）。
   删除同样必须打墓碑。
   ===================================================================== */

const int MAXM = 100005;     // 表长上限（竞赛里表长常取 1e5 级别的质数）
const int EMPTY = 0, OCCUPIED = 1, DELETED = 2;

int m = 11;                  // 当前表长 m（要求是 4j+3 型质数）
int h[MAXM];                 // 槽位里存的关键字
int st[MAXM];                // 槽位状态
int cnt = 0;                 // 有效元素个数 n
bool verbose = false;        // 打开后打印每一次探测

/* ---------- 重置成一张长度为 size 的空表 ---------- */
void clearTable(int size) {
    m = size; cnt = 0;
    for (int i = 0; i < m; ++i) { h[i] = 0; st[i] = EMPTY; }
}

int hashOf(int k) { return ((k % m) + m) % m; }

/* ---------- 探测序列的第 i 项增量（i 从 0 开始）：0, +1, -1, +4, -4, ... ---------- */
int delta(int i) {
    if (i == 0) return 0;
    int k = (i + 1) / 2;                 // 1,1,2,2,3,3,...
    int sq = k * k;
    return (i % 2 == 1) ? sq : -sq;      // 奇数次取正，偶数次取负
}

/* ---------- 插入：返回落点下标；-1 表示表满 ---------- */
int insertKey(int k) {
    int hh = hashOf(k);
    for (int i = 0; i < m; ++i) {
        int pos = ((hh + delta(i)) % m + m) % m;
        if (verbose)
            printf("    i=%d d=%d → pos %d%s\n", i, delta(i), pos,
                   st[pos] == OCCUPIED ? "（冲突）" : "（可放）");
        if (st[pos] == OCCUPIED && h[pos] == k) return pos;    // 已存在
        if (st[pos] != OCCUPIED) {                     // EMPTY 或 DELETED 都能放
            h[pos] = k; st[pos] = OCCUPIED; ++cnt;
            return pos;
        }
    }
    return -1;                                         // 表满
}

/* ---------- 查找：返回下标，找不到返回 -1；cmpCnt 输出比较次数 ---------- */
int findKey(int k, int *cmpCnt = nullptr) {
    int hh = hashOf(k), c = 0;
    for (int i = 0; i < m; ++i) {
        int pos = ((hh + delta(i)) % m + m) % m;
        ++c;
        if (st[pos] == EMPTY) { if (cmpCnt) *cmpCnt = c; return -1; }
        if (st[pos] == OCCUPIED && h[pos] == k) { if (cmpCnt) *cmpCnt = c; return pos; }
        /* DELETED 继续往下探，这就是墓碑 */
    }
    if (cmpCnt) *cmpCnt = c;
    return -1;
}

/* ---------- 删除：同样必须打墓碑 ---------- */
bool eraseKey(int k) {
    int pos = findKey(k);
    if (pos < 0) return false;
    st[pos] = DELETED;
    --cnt;
    return true;
}

/* ---------- 验证：前 m 个探测位置是否恰好覆盖 0..m-1（只与 m 有关，不需要真的建表） ---------- */
bool probeCoversAll(int mm) {
    bool seen[MAXM] = {false};
    for (int i = 0; i < mm; ++i) {
        int pos = ((0 + delta(i)) % mm + mm) % mm;
        seen[pos] = true;
    }
    for (int i = 0; i < mm; ++i) if (!seen[i]) return false;
    return true;
}

bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; (long long)i * i <= x; ++i) if (x % i == 0) return false;
    return true;
}

void dumpTable(const char *title) {
    printf("%s（n=%d）\n  ", title, cnt);
    for (int i = 0; i < m; ++i) {
        if (st[i] == OCCUPIED)      printf("[%d]%d ", i, h[i]);
        else if (st[i] == DELETED)  printf("[%d]墓碑 ", i);
        else                        printf("[%d]空 ", i);
    }
    printf("\n");
}

int main() {
    /* ---- 结论验证：m = 4j+3 的质数能覆盖全表，其它不行 ---- */
    int ms[8] = {7, 11, 12, 13, 19, 23, 29, 31};
    for (int i = 0; i < 8; ++i) {
        int mm = ms[i];
        printf("m=%-3d（4j+3? %s，质数? %s）探测序列覆盖全表? %s\n",
               mm, (mm % 4 == 3) ? "是" : "否", isPrime(mm) ? "是" : "否",
               probeCoversAll(mm) ? "能" : "不能");
    }
    /* 预期：7/11/19/23/31 能；12（非质数）、13（≡1 mod 4）、29（≡1 mod 4）不能 */

    /* ---- 同一串关键字，和线性探测对比（m 必须取 4j+3 型质数） ---- */
    printf("\n平方探测插入 22,41,53,46,30,13,1,67,42（m=11）：\n");
    clearTable(11);
    int keys[9] = {22, 41, 53, 46, 30, 13, 1, 67, 42};
    verbose = true;
    for (int i = 0; i < 9; ++i) {
        printf("  插入 %d（H=%d）\n", keys[i], keys[i] % m);
        insertKey(keys[i]);
    }
    verbose = false;
    dumpTable("结果：");

    int c = 0, total = 0;
    for (int i = 0; i < 9; ++i) { findKey(keys[i], &c); total += c; }
    printf("ASL_success = %d/9 = %.2f\n", total, total / 9.0);
    return 0;
}

10.7.4 开放定址法的 ASL 手推（408 高频大题）

这是哈希表部分最必须动手练的题型。规则固定，只要按表格一步步来就不会错。 我们用本章反复出现的那组数据：表长 m = 11，哈希函数 H(k) = k mod 11， 线性探测法，依次插入 22, 41, 53, 46, 30, 13, 1, 67, 42。

第一步：逐个插入，记录每个关键字的探测过程与最终位置。

第二步：画出最终的表（这是计算失败 ASL 的依据）。

第三步：算查找成功的 ASL。等概率时每个关键字的查找概率是 1/9：

第四步：算查找不成功的 ASL。这里是关键：失败时我们从每一个哈希地址 （下标 0 到 10，共 m = 11 种情形）出发做探测，一直探到第一个空槽为止。 因为空槽代表「探测链断了，后面不可能有」，所以比较次数 = 从起点走到空槽所经过的位置数 （包括最后那个空槽本身，因为我们访问了它并做了判定）。

10.7.5 处理冲突（二）：链地址法（拉链法）

链地址法（separate chaining，又称拉链法）的思想完全不同： 哈希表只存「桶」（bucket）的头指针，所有哈希到同一地址的关键字串成一条链表。 这样冲突不再需要「另找位置」，而是「挂在同一个桶下面」。

动画演示同样的插入过程，并且包含一次「查找穿过长链」与一次「查找失败」：

链地址法的 ASL 手推

用图 10-9 的同一组数据（m = 11，头插法，插入顺序 99, 1, 23, 14, 55, 68, 11, 37, 46）：

链地址法的 C++ 实现

#include <bits/stdc++.h>
using namespace std;

/* =====================================================================
   链地址法（拉链法）—— 竞赛写法：struct 描述结点 + 全局桶数组 + 自由函数
   - 桶数组 + 每个桶一条单链表（指针域 nxt）
   - 插入 O(1)（头插）；查找 = 定位桶 + 遍历链
   - 删除不需要墓碑，直接摘链；装填因子 α = n / m 可以大于 1
   数组大小依据：M = 11 取质数；竞赛里桶数常取 1e5 级别的质数
   ===================================================================== */

const int M = 11;              // 桶数 m，取质数

struct Node {                  // 链结点：数据域 + 指针域
    int val;
    Node *nxt;
};

Node *head[M];                 // 桶数组：head[i] 是第 i 条链的表头指针
int n = 0;                     // 元素个数 n；α = n / M
int headInsert = 1;            // 1 = 头插（O(1)），0 = 尾插（O(链长)）

int hashOf(int k) { return ((k % M) + M) % M; }
double loadFactor() { return (double)n / M; }

/* ---------- 插入：同一关键字只留一个；头插 O(1)，尾插 O(链长) ---------- */
bool insertKey(int k) {
    int hh = hashOf(k);
    for (Node *p = head[hh]; p; p = p->nxt)
        if (p->val == k) return false;            // 不允许重复
    Node *p = new Node{k, nullptr};               // 竞赛里不回收内存，程序结束即归还系统
    if (headInsert) {                             // 头插
        p->nxt = head[hh];
        head[hh] = p;
    } else {                                      // 尾插
        if (!head[hh]) head[hh] = p;
        else {
            Node *q = head[hh];
            while (q->nxt) q = q->nxt;
            q->nxt = p;
        }
    }
    ++n;
    return true;
}

/* ---------- 查找：成功返回 true；cmpCnt 输出比较次数（空桶时是 0） ---------- */
bool findKey(int k, int *cmpCnt = nullptr) {
    int c = 0;
    for (Node *p = head[hashOf(k)]; p; p = p->nxt) {
        ++c;
        if (p->val == k) { if (cmpCnt) *cmpCnt = c; return true; }
    }
    if (cmpCnt) *cmpCnt = c;                      // 空桶时 c = 0，这是链地址法失败 ASL 的特点
    return false;
}

/* ---------- 删除：直接摘链，无需墓碑 ---------- */
bool eraseKey(int k) {
    int hh = hashOf(k);
    Node *p = head[hh], *pre = nullptr;
    while (p && p->val != k) { pre = p; p = p->nxt; }
    if (!p) return false;
    if (pre) pre->nxt = p->nxt;                   // 摘链
    else head[hh] = p->nxt;                       // 删的是表头
    --n;
    return true;
}

/* ---------- 统计两种 ASL ---------- */
/* 成功 ASL：每个元素在链上的"名次"之和 / n（分母 n）
   失败 ASL：把每条链走完的比较次数之和 / m（分母 m，空桶记 0 次比较） */
void statASL() {
    int succTotal = 0;
    for (int i = 0; i < M; ++i) {
        int rank = 0;
        for (Node *p = head[i]; p; p = p->nxt) { ++rank; succTotal += rank; }
    }
    int failTotal = 0;
    for (int i = 0; i < M; ++i)
        for (Node *p = head[i]; p; p = p->nxt) ++failTotal;
    printf("n=%d, m=%d, α=%.3f\n", n, M, loadFactor());
    printf("ASL_success = %d/%d = %.3f\n", succTotal, n, n ? (double)succTotal / n : 0.0);
    printf("ASL_fail    = %d/%d = %.3f\n", failTotal, M, (double)failTotal / M);
}

void dumpTable() {
    for (int i = 0; i < M; ++i) {
        if (!head[i]) { printf("桶%d: 空\n", i); continue; }
        printf("桶%d: ", i);
        for (Node *p = head[i]; p; p = p->nxt) printf("%d → ", p->val);
        printf("∧\n");
    }
}

int main() {
    headInsert = 1;                               // m = 11，头插
    int keys[9] = {99, 1, 23, 14, 55, 68, 11, 37, 46};
    for (int i = 0; i < 9; ++i) insertKey(keys[i]);
    dumpTable();
    statASL();
    /* 预期输出（m = 11，头插）：
       各关键字哈希：99→0, 1→1, 23→1, 14→3, 55→0, 68→2, 11→0, 37→4, 46→2
       桶0: 11,55,99（头插，最后插的在最前）  桶1: 23,1
       桶2: 46,68                            桶3: 14   桶4: 37
       ASL_success = (1+2+3 + 1+2 + 1+2 + 1 + 1) / 9 = 14/9 ≈ 1.556
       ASL_fail    = (3+2+2+1+1+0+0+0+0+0+0) / 11    = 9/11 ≈ 0.818 */

    int c = 0;
    findKey(99, &c);
    printf("查找 99 → 比较 %d 次（在桶 0 的链尾）\n", c);
    findKey(100, &c);
    printf("查找 100 → 失败，比较 %d 次（桶 1 只有 2 个结点）\n", c);

    eraseKey(99);
    printf("删除 99 后：\n");
    dumpTable();
    statASL();
    return 0;
}

10.7.6 处理冲突（三）：再哈希法与公共溢出区

再哈希法（多哈希函数法）

思想：预先准备一组哈希函数 H1, H2, …, Hk。 用 H1(key) 算地址；如果冲突，就换 H2(key)； 再冲突就换 H3(key)……直到找到空位。

与双散列的区别：双散列是「一个起始地址 + 由 H2 决定的步长」 （地址形成一个等差数列）；再哈希法是「换一个完全独立的哈希函数重算地址」， 两者在聚集特性上略有差异，但都属于「用多个函数打散」的同一思路。

建立公共溢出区

思想：把哈希表拆成两部分——基本表和溢出表。 所有 H(key) 不冲突的元素放进基本表； 一旦发生冲突，不管是谁，统统塞进公共溢出区（通常是顺序表）。

查找时：先按 H(key) 查基本表，若基本表该位置上的关键字与 key 相等 → 成功； 否则（要么位置为空，要么被别的关键字占了）就去溢出区顺序查找。

优点：实现非常简单，基本表里「一个萝卜一个坑」， 不需要探测、不需要墓碑、删除也简单（在溢出区做删除即可）。 缺点：一旦冲突元素变多，溢出区就退化成顺序表，查找代价 O(溢出元素个数)， 性能急剧下降。所以它只适合冲突很少的场景——比如哈希函数设计得极好、 或者数据量远小于表长（α 很小）。它在教材里主要作为「第四种方法」出现，工程中少见。

#include <bits/stdc++.h>
using namespace std;

/* =====================================================================
   方法三：再哈希法（准备一组哈希函数，冲突就换下一个）
   方法四：建立公共溢出区（基本表 + 溢出表）
   两套全局数组 + 自由函数放在一个文件里对照着看
   数组大小依据：表长都按 1e5 级别开（MAX 常量），实际演示只用到 11 个槽
   ===================================================================== */

/* ------------------------- 方法三：再哈希法 ------------------------- */
const int RMAX = 100005;      // 再哈希法的表容量
int rm = 11, rn = 0;          // 表长 m、元素个数 n
int rt[RMAX];                 // 槽位里存的关键字
bool rused[RMAX];             // 该槽位是否被占用
int funcUsed[8];              // 统计每个哈希函数被用了多少次

/* 一组互相独立的哈希函数：冲突了就换下一个重算地址 */
int hashByIdx(int idx, int k) {
    switch (idx) {
        case 0: return ((k % rm) + rm) % rm;                                       // 除留余数
        case 1: return (int)((((long long)k * 2654435761LL / 256) % rm + rm) % rm); // 乘法散列
        case 2: return (int)((((long long)k * k / 16) % rm + rm) % rm);             // 平方取中
        case 3: return ((k / 7 + k % 7) % rm + rm) % rm;
        default: return (int)((((long long)k * (idx * 2 + 1) + idx * 13) % rm + rm) % rm);
    }
}

bool rhInsert(int k, bool verbose = false) {
    for (int f = 0; f < 8; ++f) {
        int pos = hashByIdx(f, k);
        ++funcUsed[f];
        if (verbose)
            printf("    H%d(%d) = %d%s\n", f + 1, k, pos,
                   rused[pos] ? "（冲突，换下一个函数）" : "（空，放入）");
        if (!rused[pos]) { rt[pos] = k; rused[pos] = true; ++rn; return true; }
        if (rt[pos] == k) return true;            // 已经存过
    }
    return false;                                 // 8 个函数都撞了（极小概率）
}

int rhFind(int k, int *cmpCnt = nullptr) {
    int c = 0;
    for (int f = 0; f < 8; ++f) {
        int pos = hashByIdx(f, k);
        ++c;
        if (rused[pos] && rt[pos] == k) { if (cmpCnt) *cmpCnt = c; return pos; }
        if (!rused[pos]) break;                   // 该函数算出的位置是空的 → 说明没存进来过
    }
    if (cmpCnt) *cmpCnt = c;
    return -1;
}

bool rhErase(int k) {
    int pos = rhFind(k);
    if (pos < 0) return false;
    rused[pos] = false; --rn;
    return true;
}

/* ------------------------- 方法四：公共溢出区 ------------------------- */
const int OMAX = 100005;      // 基本表容量
int om = 11, on = 0;          // 基本表表长 m、元素个数 n
int obase[OMAX];              // 基本表：一个萝卜一个坑
bool oused[OMAX];             // 基本表槽位是否被占用
int ovf[OMAX];                // 公共溢出区（顺序表），存所有冲突的元素
int ovfCnt = 0;               // 溢出区元素个数

int ovHash(int k) { return ((k % om) + om) % om; }

void ovInsert(int k) {
    int pos = ovHash(k);
    if (!oused[pos]) { obase[pos] = k; oused[pos] = true; }   // 基本表还空着
    else if (obase[pos] == k) return;                         // 已存在
    else { ovf[ovfCnt++] = k; }                               // 冲突 → 统统进溢出区
    ++on;
}

int ovFind(int k, int *cmpCnt = nullptr) {
    int c = 0, pos = ovHash(k);
    ++c;
    if (oused[pos] && obase[pos] == k) { if (cmpCnt) *cmpCnt = c; return pos; }
    /* 基本表没有 → 去溢出区顺序查找（冲突一多就退化成顺序表，这是它的缺点） */
    for (int i = 0; i < ovfCnt; ++i) {
        ++c;
        if (ovf[i] == k) { if (cmpCnt) *cmpCnt = c; return om + i; }   // 用 m+i 表示溢出区下标
    }
    if (cmpCnt) *cmpCnt = c;
    return -1;
}

bool ovErase(int k) {
    int pos = ovHash(k);
    if (oused[pos] && obase[pos] == k) { oused[pos] = false; --on; return true; }
    for (int i = 0; i < ovfCnt; ++i)
        if (ovf[i] == k) {                        // 溢出区删除：后面的元素往前搬
            for (int j = i; j + 1 < ovfCnt; ++j) ovf[j] = ovf[j + 1];
            --ovfCnt; --on;
            return true;
        }
    return false;
}

void ovDump() {
    printf("  基本表: ");
    for (int i = 0; i < om; ++i) {
        if (oused[i]) printf("[%d]%d ", i, obase[i]);
        else printf("[%d]空 ", i);
    }
    printf("\n  溢出区: ");
    if (!ovfCnt) printf("(空)");
    for (int i = 0; i < ovfCnt; ++i) printf("%d ", ovf[i]);
    printf("\n");
}

int main() {
    int keys[9] = {22, 41, 53, 46, 30, 13, 1, 67, 42};

    printf("======== 方法三：再哈希法 ========\n");
    for (int i = 0; i < 9; ++i) {
        printf("  插入 %d：\n", keys[i]);
        rhInsert(keys[i], true);
    }
    printf("  各哈希函数被调用次数：");
    for (int i = 0; i < 5; ++i) printf("H%d=%d ", i + 1, funcUsed[i]);
    printf("\n");
    int c = 0, pos = 0;
    pos = rhFind(42, &c);
    printf("  查找 42 → %s，比较 %d 次\n", pos >= 0 ? "成功" : "失败", c);

    printf("\n======== 方法四：公共溢出区 ========\n");
    for (int i = 0; i < 9; ++i) ovInsert(keys[i]);
    ovDump();                                     // 冲突的几个会落到溢出区
    pos = ovFind(42, &c);
    printf("  查找 42 → %s，比较 %d 次（基本表 1 次 + 溢出区若干次）\n",
           pos >= 0 ? "成功" : "失败", c);
    pos = ovFind(999, &c);
    printf("  查找 999 → %s，比较 %d 次\n", pos >= 0 ? "成功" : "失败", c);
    ovErase(42);
    printf("  删除 42 后：\n");
    ovDump();
    return 0;
}

10.7.7 四种冲突处理方法的综合对比

10.7.8 装填因子 α：哈希表唯一的性能旋钮

装填因子 α = n / m（已存元素数 / 表长），它是决定哈希表平均查找长度的一阶因素， 而且注意一个反直觉的结论：

理论上的近似公式（了解即可，考试一般不要求推导）：

从这些式子能读出三件事，这比记公式更重要：

1. 开放定址法必须保证 α < 1，因为公式里都有 1/(1−α)： 当 α → 1 时分母趋近于 0，ASL 爆炸。而且 α = 1 意味着表全满， 插入直接失败——哈希表必须永远留有空槽，这不是效率问题，是正确性问题。
2. 线性探测对 α 最敏感（分母是平方），所以生产环境普遍把阈值设在 α ≤ 0.75：超过就扩容（rehash）到大约 2 倍。 Java HashMap 的默认阈值就是 0.75，这是性能与内存的经典折中。
3. 链地址法允许 α > 1，因为链表可以无限延长，公式 1 + α/2 里没有分母。 但它也不是免费的：α = 4 时平均要遍历 3 个结点，指针追逐的 cache 代价很高。

10.8 工程视角：哈希在真实系统里怎么用

10.8.1 C++ 的 unordered_map 是怎么实现的

std::unordered_map 与 std::unordered_set 是 C++11 引入的哈希容器， 标准对实现的约束只有一条：平均 O(1)、最坏 O(n)，并规定「桶（bucket）」这个接口。 具体实现由各家标准库自由发挥：

• libstdc++（GCC）：一条全局单链表把所有结点串起来， 桶数组里存的是「指向桶内第一个结点的指针」，桶内结点通过额外的指针相连。 好处是迭代器稳定、rehash 时不用搬动结点。
• libc++（Clang）：与 libstdc++ 思路类似，也是桶数组 + 链表。
• MSVC STL：桶数组 + 每个桶一条双向链表。

无论哪家，都有几个必须知道的接口与行为：

#include <bits/stdc++.h>
using namespace std;

/* =====================================================================
   std::unordered_map 的底层行为观察 + 自定义类型的哈希（这一段保留 STL 用法）
   竞赛写法要点：自定义 key 时不再特化 std::hash，而是给容器传第三个参数 ——
   一个重载了 operator() 的哈希仿函数，既不用写模板，也不污染 std 命名空间。
   ===================================================================== */

struct Point {                 // 自定义类型做 key：必须提供 == （容器靠它判等）
    int x, y;
    bool operator==(const Point &o) const { return x == o.x && y == o.y; }
};

/* 哈希仿函数：把两个 int 混合成一个 size_t，避免 x+y 这种会撞车的组合 */
struct PointHash {
    size_t operator()(const Point &p) const {
        size_t h1 = hash<int>()(p.x);
        size_t h2 = hash<int>()(p.y);
        /* 0x9e3779b9... 是黄金分割常数，配合移位异或能把两个分量彻底打散 */
        return h1 ^ (h2 + 0x9e3779b97f4a7c15ULL + (h1 << 6) + (h1 >> 2));
    }
};

/* 一个"慢哈希"，用来观察哈希质量对性能的影响 */
struct SlowHash {
    size_t operator()(int k) const {
        size_t h = k;
        for (int i = 0; i < 200; ++i) h = h * 1000003u + 7;   // 故意做很多无用功
        return h;
    }
};

int main() {
    /* ---------- 1. 观察桶数与装填因子 ---------- */
    unordered_map<int, string> mp;
    cout << "初始：bucket_count=" << mp.bucket_count()
         << " load_factor=" << mp.load_factor()
         << " max_load_factor=" << mp.max_load_factor() << "\n";

    for (int i = 0; i < 1000; ++i) mp[i] = "v" + to_string(i);
    cout << "插入 1000 个后：bucket_count=" << mp.bucket_count()
         << " load_factor=" << mp.load_factor() << "\n";
    /* 观察：bucket_count 是质数序列（libstdc++）或 2 的幂，load_factor 被压在 max_load_factor 以下 */

    /* ---------- 2. reserve 预分配，避免多次 rehash ---------- */
    unordered_map<int, int> a, b;
    auto t0 = chrono::steady_clock::now();
    for (int i = 0; i < 200000; ++i) a[i] = i;              // 不预留
    auto t1 = chrono::steady_clock::now();
    b.reserve(200000);                                      // 预留
    for (int i = 0; i < 200000; ++i) b[i] = i;
    auto t2 = chrono::steady_clock::now();
    cout << "不预留: " << chrono::duration_cast<chrono::milliseconds>(t1 - t0).count() << " ms\n";
    cout << " 预留 : " << chrono::duration_cast<chrono::milliseconds>(t2 - t1).count() << " ms\n";
    cout << "a.bucket_count=" << a.bucket_count() << "  b.bucket_count=" << b.bucket_count() << "\n";

    /* ---------- 3. 自定义类型的哈希：把 PointHash 作为第三个参数传进去 ---------- */
    unordered_map<Point, int, PointHash> grid;
    grid[{1, 2}] = 10;
    grid[{3, 4}] = 20;
    cout << "grid[{1,2}] = " << grid[{1, 2}] << "\n";            // 10
    cout << "grid.count({9,9}) = " << grid.count({9, 9}) << "\n"; // 0

    /* ---------- 4. 哈希函数质量直接影响性能 ---------- */
    unordered_map<int, int> fast;                           // 默认 hash<int>：就是个恒等映射
    unordered_map<int, int, SlowHash> slow;                 // 每次哈希都算 200 次乘法
    auto t3 = chrono::steady_clock::now();
    for (int i = 0; i < 100000; ++i) fast[i] = i;
    auto t4 = chrono::steady_clock::now();
    for (int i = 0; i < 100000; ++i) slow[i] = i;
    auto t5 = chrono::steady_clock::now();
    cout << "默认 hash<int>: " << chrono::duration_cast<chrono::milliseconds>(t4 - t3).count() << " ms\n";
    cout << "SlowHash     : " << chrono::duration_cast<chrono::milliseconds>(t5 - t4).count() << " ms\n";
    /* 结论：哈希函数本身的计算量会被放大到每一次插入/查找上，别写"聪明但慢"的哈希 */

    /* ---------- 5. 查看某个关键字落在哪个桶 ---------- */
    unordered_map<int, int> m3;
    m3.max_load_factor(0.7f);              // 更低的 α → 更快的查找、更多的内存
    m3.reserve(100);
    for (int i = 0; i < 100; ++i) m3[i] = i;
    cout << "bucket_count=" << m3.bucket_count()
         << " load_factor=" << m3.load_factor() << "\n";
    for (int k = 0; k < 5; ++k)
        cout << "key " << k << " → bucket " << m3.bucket(k) << "\n";
    return 0;
}

10.8.2 竞赛中防哈希被卡

这是竞赛选手必须掌握的保命技巧。背景是这样： std::unordered_map 的哈希函数（std::hash<int>）通常是「恒等映射」 （hash(x) = x）加上标准库自己的桶取模。 而桶数在很多实现里是质数序列或 2 的幂，都是公开可知的。

于是出题人可以故意构造一组全部同余的关键字（比如所有 k ≡ 0 (mod p)）， 让它们全部落进同一个桶，哈希表退化成链表，O(1) 变 O(n)， 你的程序 TLE。这个技巧叫 hash flooding / 卡哈希。

解决方案只有一招：自己写一个带随机种子的哈希函数，让攻击者无法预测落点。

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <chrono>
#include <random>
using namespace std;

/* =====================================================================
   防卡哈希（anti-hash-test）模板
   原理：用一个程序启动时才确定的随机种子，把关键字彻底打散。
        出题人无法预知种子 → 无法构造出全部冲突的数据。
   用法：
        unordered_map<int, int, custom_hash> mp;
        unordered_set<long long, custom_hash_ll> st;
   ===================================================================== */

/* ---------- 通用版：适用于 int / long long 等整数类型 ---------- */
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        /* splitmix64：雪崩性极好的整数混合函数，被 splitmix64 / 各大赛事模板广泛使用 */
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
    static uint64_t& seed() {
        /* 只在第一次调用时取一次随机数（用高精度时钟，无需 <random> 也很随机） */
        static uint64_t s = chrono::steady_clock::now().time_since_epoch().count();
        return s;
    }
    size_t operator()(uint64_t x) const {
        return splitmix64(x + seed());
    }
};

/* ---------- 字符串版：把字符串折成一个整数再混合 ---------- */
struct custom_hash_str {
    size_t operator()(const string& s) const {
        uint64_t h = 1469598103934665603ULL;          // FNV 偏移基准
        for (unsigned char c : s) {
            h ^= c;
            h *= 1099511628211ULL;                    // FNV 质数
        }
        return custom_hash::splitmix64(h + custom_hash::seed());
    }
};

/* ---------- 极简版：一个随机偏移 + 取反，够用且短 ---------- */
struct simple_random_hash {
    static uint64_t rnd() {
        static uint64_t r = chrono::steady_clock::now().time_since_epoch().count();
        return r;
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = rnd();
        x += FIXED_RANDOM;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
};

/* ---------- 反例：一个"看起来聪明其实会被卡"的哈希 ---------- */
struct bad_hash {
    size_t operator()(uint64_t x) const { return x % 1000000007ULL; }   // 固定模数 → 完全可预测
};

int main() {
    /* ---------- 1. 基本用法 ---------- */
    unordered_map<long long, int, custom_hash> mp;
    mp[1234567890123LL] = 1;
    cout << "mp[1234567890123] = " << mp[1234567890123LL] << "\n";

    unordered_set<string, custom_hash_str> st;
    st.insert("hello"); st.insert("world");
    cout << "st.count(\"hello\") = " << st.count("hello") << "\n";

    /* ---------- 2. 演示"卡哈希"攻击：构造全部同余的数据 ---------- */
    const int N = 30000;

    /* 2.1 用坏的哈希：所有 key 都是 P 的倍数 → 全落一个桶 */
    {
        unordered_map<long long, int, bad_hash> victim;
        const long long P = 1000000007LL;                  // 与 bad_hash 的模数一致
        auto t0 = chrono::steady_clock::now();
        for (int i = 0; i < N; ++i) victim[(long long)i * P] = i;
        long long sum = 0;
        for (int i = 0; i < N; ++i) sum += victim[(long long)i * P];
        auto t1 = chrono::steady_clock::now();
        cout << "固定模数哈希，同余数据 " << N << " 个："
             << chrono::duration_cast<chrono::milliseconds>(t1 - t0).count() << " ms\n";
        cout << "（全部落进同一个桶，退化成链表 → 明显变慢）\n";
    }

    /* 2.2 用 custom_hash：同样的数据被彻底打散 */
    {
        unordered_map<long long, int, custom_hash> safe;
        const long long P = 1000000007LL;
        auto t0 = chrono::steady_clock::now();
        for (int i = 0; i < N; ++i) safe[(long long)i * P] = i;
        long long sum = 0;
        for (int i = 0; i < N; ++i) sum += safe[(long long)i * P];
        auto t1 = chrono::steady_clock::now();
        cout << "随机化哈希，同余数据 " << N << " 个："
             << chrono::duration_cast<chrono::milliseconds>(t1 - t0).count() << " ms\n";
        cout << "（被 splitmix64 打散到各个桶）\n";
    }

    /* ---------- 3. 用随机种子重新运行本程序，可以看到时间基本不变 ---------- */
    cout << "\n提示：把本程序编译后多跑几次，第 2.2 项的时间应该稳定；\n"
         << "      而如果把 custom_hash 换成固定种子的版本，攻击者就能复现并卡掉它。\n";
    return 0;
}

10.8.3 字符串哈希及其应用

字符串哈希（string hashing，也叫滚动哈希 rolling hash）是把「字符串」映射为「整数」的技术， 它让「判断两个子串是否相等」从 O(len) 降到 O(1)。 核心是把字符串看作一个 base 进制的大整数：

配合前缀哈希 pre[i] 与幂次表 pw[i]，任意子串 s[l..r] 的哈希是：

两种常见的模数策略：

• 自然溢出：用 unsigned long long，让它自动对 264 取模。 代码最短、最快，但可以被构造出碰撞（Thue–Morse 序列是经典杀器）， 有的出题人会专门卡这个。
• 双模数：用两个大质数（109+7 与 109+9， 或 998244353）各算一遍，用 pair 表示。 碰撞概率降到约 1/(M1M2)，实际比赛中几乎不可能被卡。

与第 05 讲 KMP 的联系：字符串哈希和 KMP 都在解决「子串匹配」， 但路子完全不同——KMP 用「最长相等前后缀」做确定性的线性匹配， 哈希用概率性的相等判定换取「任意子串 O(1) 比较」的灵活性。 两者的选择标准：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

/* =====================================================================
   字符串哈希：自然溢出版 + 双模数版
   用途：O(1) 判断任意两个子串是否相等、求最长重复子串、回文判定等
   ===================================================================== */

/* ---------------- 版本一：自然溢出（unsigned long long 自动 mod 2^64） ---------------- */
struct HashULL {
    static const unsigned long long B = 131;          // 进制，通常取 131 或 13331
    vector<unsigned long long> pre, pw;

    explicit HashULL(const string& s) {
        int n = (int)s.size();
        pre.assign(n + 1, 0);
        pw.assign(n + 1, 1);
        for (int i = 0; i < n; ++i) {
            pre[i + 1] = pre[i] * B + (unsigned char)s[i];
            pw[i + 1]  = pw[i] * B;
        }
    }
    /* 子串 s[l..r] 的哈希，0 基，闭区间 */
    unsigned long long get(int l, int r) const {
        return pre[r + 1] - pre[l] * pw[r - l + 1];
    }
};

/* ---------------- 版本二：双模数（更安全） ---------------- */
struct HashDouble {
    static const long long M1 = 1000000007LL;
    static const long long M2 = 1000000009LL;
    static const long long B  = 131;
    vector<long long> p1, p2, w1, w2;

    explicit HashDouble(const string& s) {
        int n = (int)s.size();
        p1.assign(n + 1, 0); p2.assign(n + 1, 0);
        w1.assign(n + 1, 1); w2.assign(n + 1, 1);
        for (int i = 0; i < n; ++i) {
            p1[i + 1] = (p1[i] * B + (unsigned char)s[i]) % M1;
            p2[i + 1] = (p2[i] * B + (unsigned char)s[i]) % M2;
            w1[i + 1] = (w1[i] * B) % M1;
            w2[i + 1] = (w2[i] * B) % M2;
        }
    }
    pair<long long, long long> get(int l, int r) const {
        long long h1 = ((p1[r + 1] - p1[l] * w1[r - l + 1]) % M1 + M1) % M1;
        long long h2 = ((p2[r + 1] - p2[l] * w2[r - l + 1]) % M2 + M2) % M2;
        return {h1, h2};
    }
};

/* ---------------- 应用：哈希版模式匹配（对比第 05 讲的 KMP） ---------------- */
int matchByHash(const string& S, const string& P) {
    int n = (int)S.size(), m = (int)P.size();
    if (m == 0) return 0;
    if (m > n) return -1;
    HashDouble hs(S), hp(P);
    auto target = hp.get(0, m - 1);
    for (int i = 0; i + m <= n; ++i)
        if (hs.get(i, i + m - 1) == target) return i;      // O(1) 比较！
    return -1;
}

/* ---------------- 应用：最长重复子串（二分长度 + 哈希判重） ---------------- */
int longestRepeatedSubstring(const string& s) {
    int n = (int)s.size();
    HashULL h(s);
    auto ok = [&](int len) -> bool {
        if (len == 0) return true;
        vector<unsigned long long> v;
        for (int i = 0; i + len <= n; ++i) v.push_back(h.get(i, i + len - 1));
        sort(v.begin(), v.end());
        for (int i = 1; i < (int)v.size(); ++i) if (v[i] == v[i - 1]) return true;
        return false;
    };
    int lo = 1, hi = n - 1, ans = 0;
    while (lo <= hi) {                                     // 二分长度
        int mid = lo + (hi - lo) / 2;
        if (ok(mid)) { ans = mid; lo = mid + 1; } else hi = mid - 1;
    }
    return ans;
}

int main() {
    string S = "ABABABCABABABCABA", P = "ABABCABA";
    cout << "哈希匹配：" << matchByHash(S, P) << "（KMP 的结果也是 2）\n";

    HashDouble hd("abcabc");
    cout << "子串 [0,2] 与 [3,5] 相等? "
         << (hd.get(0, 2) == hd.get(3, 5)) << "\n";            // 1

    cout << "最长重复子串长度 = " << longestRepeatedSubstring("abcabcbb") << "\n";   // 3（"abc"）
    cout << "最长重复子串长度 = " << longestRepeatedSubstring("abcdefg")  << "\n";   // 0
    return 0;
}

10.8.4 查找方法总览：一张表选型

10.8.5 冲突处理在真实实现里怎么选：为什么拉链法是主流

10.7 里我们把四种冲突处理方法摆在一起做过对比，那是教科书视角； 现在换一副眼镜，看的是工程视角——主流语言的标准库和数据库到底选了谁，为什么。

拉链法赢在哪两条？

1. 负载因子 α 可以大于 1。回忆 10.7.8 的公式：链地址法的成功 ASL 是 1 + α/2，式子里没有分母，所以 α = 2 甚至 α = 4 都还能跑， 只是平均要顺着链找 2～3 个结点。 开放定址就绝对不行——它的公式里全是 1/(1−α)， α = 1 意味着表全满，插入直接失败，这不是性能问题，是正确性问题： 开放定址法必须永远留有空槽。
2. 删除简单，不需要墓碑。链地址法删除一个元素，就是把结点从链上摘下来、 delete 掉，O(1)（双向链表）或 O(链长)， 删完表的状态和「这个元素从没来过」完全一样。 开放定址法不行：直接把它占的槽置空会截断探测链， 让它后面的同义词全部找不到（图 10-10 画的就是这个事故）， 所以必须留一个墓碑（tombstone）占着位置。 墓碑的代价是双重的：它仍然占着槽（α 只涨不跌）， 而且查找时必须继续往后探，不能被墓碑骗停。 墓碑攒多了，表就「假满」了——内存里有空槽，性能却像满了， 唯一的解法是原地重建（rehash），又是一次 O(n)。

那开放定址靠什么活下来？靠两个字：缓存。

• 缓存友好（cache-friendly）。开放定址的探测全部发生在同一个连续数组内， 线性探测的第 1、2、3 次探测大概率落在同一个 64 字节缓存行里， 一次内存访问能顺带把后面几个槽也拉进 L1。 拉链法则相反：每跳一个结点都是一次指针追逐（pointer chasing）， 可能跨越整个堆内存，每次都是一次缓存未命中——这就是「同样 O(1)， 实测差 3～10 倍」的根源。
• 无指针开销、无单独分配。拉链法每个元素都要额外存一个（或两个）next 指针， 而且每个结点都是一次 new——对 int → int 这种小元素， 指针本身比数据还大（数据 8 字节 + 指针 8 字节 + 分配器对齐与元数据， 实打实的开销常常是 2～3 倍）。开放定址把这笔钱全省了， 这也是 flat_hash_map 里「flat（扁平）」两个字的由来。

读这张表只需要看三行。α = 0.75 时，线性探测一次不成功查找平均要探 8.5 个槽，链地址法只要 1.38 个结点——还能忍。 α = 0.90 时，线性探测的失败代价跳到 50.5——一次查找要摸 50 个槽， 已经在崩溃边缘。而 α = 0.99 时失败代价是 5000.5： 一个 m = 100 的表，一次「查不到」平均要扫 50 遍全表。 注意线性探测成功 ASL 在 α = 0.99 时也涨到了 50.5—— 这时候哈希表已经没有资格叫哈希表了，它退化成了一条 O(n) 的链表， 还得额外付出哈希计算的钱。

顺带回答一个常见追问：Java 8 之后为什么还要把长链「树化」？ 因为纯链表在极端情况下（哈希函数差，或者有人恶意构造）会退化到 O(n)。 所以 JDK 8 起规定：单条链长度 ≥ 8 且桶数组长度 ≥ 64 时， 把这条链转成红黑树，把最坏情况从 O(n) 拉回 O(log n)。 这是「拉链法 + 平衡树」的混合结构，也是对哈希碰撞攻击最直接的一种防御—— 就算你全塞进一个桶，我也只花 O(log n)。

10.8.6 扩容（rehash）：为什么是翻倍，以及 O(n) 的长尾延迟

拉链法和开放定址法都躲不开同一件事：α 涨到阈值就得扩容。 扩容做的事很朴素——申请一个更大的桶数组，然后把所有元素重新算一遍落点搬过去。 两件事值得掰开讲：为什么一次扩到两倍，以及这一次 O(n) 的代价藏在哪里。

工程上的四种应对，从便宜到复杂：

1. 预留（reserve）—— 最便宜也最有效。如果能预知规模，就在插入前一次性 reserve(n)，让扩容次数从 log n 次变成 0 次。 代价是多占内存（要按最终规模分配），而且预判错了照样要扩。 竞赛里这条是硬规矩：unordered_map 不写 reserve 经常就是 TLE 与 AC 的差别。
2. 分批扩容（渐进式 rehash，incremental rehashing）—— Redis 的做法。 Redis 的字典在扩容时同时保留两张哈希表（ht[0] 旧表、 ht[1] 新表），但不一次性搬完：每次增删改查都顺手把 ht[0] 里的一个桶（连同它的链表）整体搬到 ht[1]， 查找时两张表都查（先查 ht[0] 再查 ht[1]），新增的元素只往 ht[1] 里放。 等 ht[0] 搬空，再释放它、把 ht[1] 改名成 ht[0]。 这样一来，单次操作的额外代价被摊薄成常数，任何一次请求都不会出现长尖刺。 代价是：扩容期间内存要同时装下两张表（峰值接近 2 倍）， 而且每条操作路径都要写「两张表都要看」的分支，代码复杂度显著上升。
3. 后台线程搬迁。Go 的 map 在触发扩容后会由一个后台 goroutine 逐步把旧桶搬到新桶（同时配合写屏障保证正确性）。 代价是语言运行时复杂度飙升，而且并发读写 map 本身仍然不安全。
4. 提前预热。在线服务启动时先用一批假数据把哈希表「喂」到目标容量， 让扩容发生在上线之前。代价是启动变慢、需要维护预热数据。

10.8.7 std::unordered_map 的真实结构与防卡哈希

现在把镜头对准 C++ 里最常用的那个容器。std::unordered_map 与 std::unordered_set 是 C++11 引入的哈希容器， 标准对实现的约束只有一条：平均 O(1)、最坏 O(n)，并规定「桶（bucket）」这个接口。 具体实现由各家标准库自由发挥：

加了随机种子之后，攻击者无法预知落点，构造不出「全部同桶」的数据集， 攻击就从「必然成功」变成「期望不成功」。完整的可编译模板（ custom_hash / custom_hash_str，含攻击演示对比） 见下面的代码块——它就是竞赛选手的保命工具。

10.8.8 数据库索引为什么主要用 B+ 树而不是哈希

这是「哈希这么快，为什么数据库不用它当索引」这个问题的答案。 一句话：哈希只支持等值查询，而真实的查询语句里大部分不是等值查询。

哈希函数的定义决定了它是一台只能回答「是 / 否」的判等机器： 它把键打散到桶里，打散之后原有的顺序信息被彻底销毁了。 一个键的哈希值是 0x8f3a… ，这完全不告诉你「它比 42 大还是小」。 所以下面这几类查询，哈希索引一个都做不了（只能全表扫描）：

• 范围查询：WHERE id BETWEEN 100 AND 200、 WHERE created_at > '2024-01-01'。 这是索引最常见的用途（分页、时间窗口、区间统计），哈希索引直接失效。
• 排序：ORDER BY id、ORDER BY name LIMIT 10。 B+ 树的叶子结点本身就是按顺序串起来的链表， 顺着叶子链一扫就是有序输出；哈希表里的元素在物理上毫无顺序， 要排序只能把所有命中行拉出来再排一次。
• 最左前缀匹配：联合索引 (a, b, c) 上， B+ 树可以用 WHERE a = 1、WHERE a = 1 AND b > 2 这种「只用前几个列」的查询；哈希索引要求把索引的全部列都写全 才能算出哈希值，少一列就用不上。
• 分组与去重：GROUP BY、DISTINCT 也需要有序扫描， B+ 树的顺序性又赢一次。

所以数据库默认选 B+ 树（这本该是第 07 讲树结构的延伸话题，这里只做工程收口）： 它是一棵多路平衡树，一个结点装几百个键， 树高在 3～4 层就能覆盖上亿行数据；更关键的是它的 叶子结点连成有序链表，把「等值查找 O(log n)」「范围扫描」「排序」 「最左前缀」四件事一次性全包了。 哈希在等值查询上确实更快（一次哈希 vs 三次磁盘 I/O）， 但它只会这一件事——为一个能力付出一整棵树的代价，数据库不干。

10.8.9 布隆过滤器：用一个位数组换掉 99% 的无效查询

前面几节讲的都是「怎么把元素存进哈希表」。布隆过滤器（Bloom Filter）反过来—— 它不存元素，只存「这个元素来过」的痕迹，用极小的空间换一个「大概率能判断」的能力。 它是哈希在工程里最漂亮的一次「降维使用」。

这套规则推出布隆过滤器最重要的两条性质：

• 没有假阴性（no false negative）。插入过的元素，它的 k 个位置一定都被置成了 1， 所以查询必然返回 true。这条性质是逻辑保证，不是概率—— 代码里 1000 个元素全部命中、假阴性 0 个，就是这个道理。
• 有假阳性（false positive）。一个没插入过的元素， 它的 k 个位置可能恰好被别的元素们一起置成了 1， 于是被误判为「存在」。这不是 bug，是设计的一部分—— 位是被所有元素共享的，撞车不可避免，只能用 m 和 k 把概率压下去。

空间到底省到什么程度？看下面这段程序的真实输出： 按 1% 的目标误判率，存 1000 个元素只需要 m = 9586 bit ≈ 1.17 KB，k = 7 个哈希函数； 实测 10000 个未插入元素中误判 96 个， 实测假阳性率 0.96%，与理论值 1.00% 吻合。 把规模放大到 800 万个元素：m = 76680468 bit ≈ 9.14 MB 就够了—— 而如果老老实实用 64 位整数存这 800 万个元素，光数据本身就是 800 万 × 8 B = 61 MB。也就是说， 布隆过滤器用大约 1/6.7 的空间，就买到了「过滤掉 99% 无效查询」的能力—— 代价是那 0.96% 的假阳性，以及彻底放弃「取出元素」和「删除元素」。

// bloom_filter.cpp —— 布隆过滤器完整实现：验证「无假阴性」并实测假阳性率
// 编译： g++ -std=c++17 -O2 -o bloom_filter bloom_filter.cpp
// 运行： ./bloom_filter
#include <bits/stdc++.h>
using namespace std;

/* =====================================================================
   布隆过滤器 = 一个位数组 + k 个哈希函数
        add(x)  ：把 k 个哈希位置全部置 1
        query(x)：k 个位置全是 1 → 返回 true（"可能存在"）
                  只要有一个是 0 → 返回 false（"一定不存在"）
   关键性质：无假阴性（插入过的必然返回 true），但有假阳性。
   ===================================================================== */
struct BloomFilter {
    vector<unsigned char> bit;   // 位数组：每个字节装 8 个 bit
    size_t m;                    // 位数组长度（bit 数）
    int    k;                    // 哈希函数个数

    /* 由「预期元素个数 n」和「可容忍的误判率 p」反推 m 与 k：
       m = -n·ln(p) / (ln2)^2        k = (m/n)·ln2              */
    BloomFilter(size_t n, double p) {
        double ln2 = log(2.0);
        m = (size_t)ceil(-(double)n * log(p) / (ln2 * ln2));
        k = (int)max(1.0, round(((double)m / (double)n) * ln2));
        bit.assign((m + 7) / 8, 0);
    }

    /* ---------- 两个相互独立的 64 位字符串哈希函数 ---------- */

    /* 1 号：FNV-1a 64 位（offset basis 与 prime 用标准值） */
    static uint64_t fnv1a(const string& s) {
        uint64_t h = 1469598103934665603ULL;
        for (unsigned char c : s) {
            h ^= (uint64_t)c;
            h *= 1099511628211ULL;
        }
        return h;
    }

    /* 2 号：FNV-1a 变体（换一组质数）再叠 splitmix64 混合，落点与 1 号无关 */
    static uint64_t fnv1b(const string& s) {
        uint64_t h = 14695981039346656037ULL;
        for (unsigned char c : s) {
            h ^= (uint64_t)c;
            h *= 1099511628211ULL + 2;
            h ^= h >> 29;
        }
        h += 0x9e3779b97f4a7c15ULL;              // splitmix64 的雪崩混合
        h = (h ^ (h >> 30)) * 0xbf58476d1ce4e5b9ULL;
        h = (h ^ (h >> 27)) * 0x94d049bb133111ebULL;
        return h ^ (h >> 31);
    }

    /* ---------- 置位与查位 ---------- */
    void setBit(size_t pos)       { bit[pos >> 3] |= (unsigned char)(1u << (pos & 7)); }
    bool getBit(size_t pos) const { return (bit[pos >> 3] >> (pos & 7)) & 1u; }

    /* ---------- 核心接口 ---------- */
    void add(const string& s) {
        uint64_t h1 = fnv1a(s), h2 = fnv1b(s);
        for (int i = 0; i < k; ++i) {
            /* 双哈希技巧：h1 + i·h2 等价于又造出 k 个"独立"哈希函数 */
            setBit((size_t)((h1 + (uint64_t)i * h2) % m));
        }
    }

    bool query(const string& s) const {
        uint64_t h1 = fnv1a(s), h2 = fnv1b(s);
        for (int i = 0; i < k; ++i) {
            /* 有一个位置是 0 → 必定没插入过（这条是逻辑保证，不是概率） */
            if (!getBit((size_t)((h1 + (uint64_t)i * h2) % m))) return false;
        }
        return true;   // k 个位置全 1 → 可能插入过（也可能是被别人"蹭"亮的）
    }

    double bits()   const { return (double)m; }
    double bytes()  const { return (double)((m + 7) / 8); }
    int    hashes() const { return k; }
    /* 插入 n 个元素后的理论误判率 (1 - e^(-kn/m))^k 的等价形式 */
    double theoryFpr(size_t n) const {
        double alpha = (double)k * (double)n / (double)m;   // 位数组被填满的比例
        return pow(1.0 - exp(-alpha), (double)k);
    }
};

int main() {
    const size_t N_ADD = 1000;      // 插入 1000 个元素
    const size_t N_QRY = 10000;     // 再查 10000 个未插入的元素
    const double P     = 0.01;      // 目标误判率 1%

    BloomFilter bf(N_ADD, P);
    printf("位数组 m = %zu bit = %.2f KB，哈希函数 k = %d\n",
           (size_t)bf.bits(), bf.bytes() / 1024.0, bf.hashes());
    printf("目标误判率 p = %.2f%%\n\n", P * 100);

    /* ---------- 1. 插入 1000 个，验证「无假阴性」 ---------- */
    for (size_t i = 0; i < N_ADD; ++i) bf.add("item-" + to_string(i));

    size_t hit = 0;
    for (size_t i = 0; i < N_ADD; ++i) if (bf.query("item-" + to_string(i))) ++hit;
    printf("已插入 %zu 个元素，查询命中 %zu 个 —— 假阴性 %zu 个\n", N_ADD, hit, N_ADD - hit);

    /* ---------- 2. 查询 10000 个未插入的元素，实测假阳性 ---------- */
    size_t fp = 0;
    for (size_t i = 0; i < N_QRY; ++i) if (bf.query("other-" + to_string(i))) ++fp;
    printf("查询 %zu 个未插入元素，误判为「存在」%zu 个 —— 实测假阳性率 %.2f%%\n",
           N_QRY, fp, 100.0 * (double)fp / (double)N_QRY);

    /* ---------- 3. 与理论值对照 ---------- */
    printf("理论假阳性率 (1-e^{-kn/m})^k = %.2f%%\n", bf.theoryFpr(N_ADD) * 100.0);

    /* ---------- 4. 空间对照：表示 800 万个元素要多少空间 ---------- */
    BloomFilter big(8000000, 0.01);
    printf("\n对照：按 1%% 误判率，表示 800 万个元素需要 m = %zu bit = %.2f MB\n",
           (size_t)big.bits(), big.bytes() / 1024.0 / 1024.0);
    printf("      而 800 万个 64 位整数本身就要 %.0f MB —— 省了约 %.1f 倍\n",
           8000000.0 * 8 / 1024 / 1024, (8000000.0 * 8) / big.bytes());
    return 0;
}

真实系统里它站在哪四个位置？

1. 缓存穿透防护（最经典）。查询流程是「先查 Redis，没有就查数据库」。 但如果有恶意请求反复查询根本不存在的 key，Redis 每次都 miss， 请求就全部穿透到数据库——这就是缓存穿透。 解法：把数据库里所有存在的 key 预先塞进一个布隆过滤器， 请求进来先过一遍——布隆过滤器说「不存在」，就直接返回空，一次数据库都不查。 那 1% 的假阳性会漏到数据库，但 99% 的恶意流量被挡在门外， 而代价只是几十 MB 内存。
2. 爬虫 URL 去重。爬虫要判断「这个 URL 是不是已经抓过」。 真实的 URL 库动辄上亿条，用哈希集合存要几十 GB； 用布隆过滤器，上亿条 URL 只要几百 MB。 假阳性在这里恰好是「安全的错误」：把没抓过的 URL 误判成抓过， 最多漏掉几个页面，不会让爬虫出错或重复入库—— 这正是布隆过滤器最适合的「错一边也无所谓」的语义。
3. BigTable / LevelDB / RocksDB 的 SSTable 查询。 这些 LSM-Tree 存储引擎把数据按层组织成一个个 SSTable 文件。 如果每次查找都要逐个文件去磁盘上二分，I/O 会爆掉。 所以每个 SSTable 都附一个布隆过滤器，记录这个文件里有哪些 key； 查询时先用内存里的布隆过滤器筛一遍， 说「没有」的文件直接跳过，一次磁盘 I/O 都不产生。 这是布隆过滤器在存储引擎里最核心的用途——用内存换 I/O。
4. 比特币 SPV 轻节点。手机钱包不想下载几百 GB 的完整区块链， 只想要「和我有关的交易」。于是它把自己所有地址放进一个布隆过滤器 发给全节点，全节点用它过滤区块里的交易，只把可能相关的交易回传。 假阳性在这里反而是一种隐私保护：全节点无法准确知道你关心哪些地址， 因为过滤器里总会混进一些无关的「疑似地址」。

10.8.10 一致性哈希：分布式缓存扩缩容时，怎么只搬 1/N 的数据

前面讲的都是一台机器内的哈希。现在把哈希表放大成一个集群： N 台缓存服务器（Redis Cluster、Memcached）， 要决定「键 k 该存到哪台机器上」。最直觉的写法是取模：

单机时代这个式子没毛病，但到了集群里它有一个致命缺陷： N 一变，几乎所有键的归属都要重算。

迁移量为什么是 1/N？加进第 N+1 个结点时，它在环上随机落一个位置， 只会从某一个原有结点手里「抢走」一段弧。 平均而言这段弧占整个环的 1/(N+1)， 所以只有约 1/(N+1) 的键需要迁移，其余 N/(N+1) 原封不动。 回到 N = 4 → 5 的例子：普通取模要搬 80%， 一致性哈希只搬 20%（约 2 万个键）——迁移量降到了 1/4。 下面图 10-12 把这个对比画了出来，左边是环上的迁移范围，右边是两种策略的迁移量直方图。

10.8.11 工程选型对比表：五个结构，五个真实维度

把本节讲的东西压成一张表。这张表不比 ASL（那是 10.7 的事）， 比的是工程师真正关心的现实维度：典型用途、空间开销、能不能删、能不能范围查、 谁在用。背着这张表去面试，比背公式有用。

最后补一句选型心法：先问「查询长什么样」，再问「数据有多大」，最后才问「要多快」。 查询里有范围或排序 → 直接排除哈希，去找树（第 07 讲的 B 树 / B+ 树）； 查询全是等值且数据能进内存 → 哈希； 只需要回答「在不在」且数据量巨大 → 布隆过滤器； 数据分散在多台机器上 → 一致性哈希负责路由。 结构选错，代码再漂亮也救不回来。

10.9 本章小结、易错点与自测

10.9.1 必须记住的十二件事

10.9.2 易错点清单

10.9.3 自测题（6 题，答案折叠）

#include <chrono>
#include <cstdint>
#include <unordered_map>
#include <unordered_set>

/* 竞赛防卡哈希：直接复制粘贴即可 */
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
    static uint64_t& seed() {
        static uint64_t s = std::chrono::steady_clock::now().time_since_epoch().count();
        return s;                                   // 每次运行都不同的随机种子
    }
    size_t operator()(uint64_t x) const { return splitmix64(x + seed()); }
};

// 用法：
//   std::unordered_map<long long, int, custom_hash> mp;
//   std::unordered_set<long long, custom_hash> st;
//   mp.reserve(1 << 20);      // 顺手预分配，避免中途 rehash

10.9.4 配套编程练习