哈希表手写实现：闭散列与开散列、冲突处理与扩容

学数据结构一步步走到这里，你大概已经习惯了"数组、链表、树"这些按顺序或者按层次查找的结构。今天要聊的哈希表，思路完全不一样——它不讲任何"顺序"，追求的是"一次定位"。你会看到一种魔法般的体验：不管数据塞进去多少，查找一个值都几乎只花常数时间。这也是 unordered_map、unordered_set 这些 C++ 标准库容器背后的实现原理。

先剧透一下我们今天的路线图：先从"什么是哈希"讲起，接着亲手实现两种风格的哈希表——闭散列（开放定址法）和开散列（链地址法，也叫哈希桶），中间会穿插字符串怎么哈希、什么时候该扩容这些实战里躲不过去的问题。每一段概念讲完，我立刻给你能编译运行的代码让你验证，而不是只停留在理论上讲。你需要的知识前置其实很少：会写数组、看得懂 for 循环、知道时间复杂度（就是衡量"代码要跑多少步"的那个概念，O(1) 表示常数步、跟数据量无关）就够了，剩下的坑我在讲的时候都给你点出来。

我先给你一句总的"地图话"，把它刻在脑子里，学完这一篇你就永远不会忘：哈希的所有工作，可以浓缩成三件套——一个把 key 变成下标的哈希函数、一张用来存东西的数组、一个处理"撞车"的冲突方案。 后面每讲一个概念，你都可以回头问自己：它属于这三件套里的哪一块？这样学，零散的知识点就会串成一张网，不会学了就散。

什么是哈希（散列）

哈希（hash），中文也翻译成散列，是一种组织数据、快速查找数据的方式。从"散列"两个字你也能品出它的味道——让数据散乱地、随机地排列。它希望达到的效果是：不用像顺序表那样挨个遍历，也不用像二分那样反复折半，而是通过一个函数，直接从关键字 key 算出它该存的位置，存的时候往那儿放，找的时候直接去那儿拿。

用大白话说，哈希干的事就一句话：建立关键字和存储位置的映射关系。

你可以理解为每个 key 都长着一张"脸"，这个"脸"（哈希函数算出来的值）告诉计算机：我就住在这张"脸"对应的那个格子里。查找时我们不再面向全体数据，而是直奔目标。这个"从 key 算出位置"的动作，就是哈希函数（hash function）。在理想情况下，查找的时间复杂度是 O(1)——无论表里有多少数据，都只要算一次、看一眼。

"哈希"这个名字到底怎么来的

你可能会好奇：一个好好的查表方法，为什么要叫"哈希"这种怪名字？这是音译。英文 hash 的原意是"剁碎""搅碎"——你看厨师把肉剁成碎末那种动作，就叫 hash（哈希）。为什么哈希表会叫这个名字？因为它干的事情跟"剁肉"很像：一个本来看起来毫无规律的大块数据（一个字符串、一个很大的整数），被哈希函数"剁"成一小块（一个 0 到 M-1 之间的下标），就像把大块的肉剁成了碎末。剁碎之后，几万个大大小小的数据，全都被"搅匀"地散落到哈希表的各个格子里。哈希函数还有一个更专业的名字叫散列函数，意思一模一样：把数据"散"开，"列"成一个个位置。所以"哈希""散列""哈希化"这些说法，指的是同一件事，只是中文翻译的角度不同。

顺便一提，hash 在计算机里还有一层更细的含义：有时它特指数据指纹（也叫摘要）。比如一个超大文件，你算一个固定长度的数字出来代表它，那个数字也叫"这个文件的 hash"。Git 里每个提交的版本号（一串 40 位的十六进制数）就是那一次提交内容的一个 hash。这里我们不深究这层含义，你只要知道哈希这个词有多层用法，避免以后看到迷糊。

为什么能达到 O(1)：关键在于"一次定位"

你以前学的查找为什么慢？我们对比一下：

• 顺序查找：数组里有没有 20？从头到尾挨个比一遍。运气好第一个就中，运气差最后一个才中。平均要走 N/2 步——数据越多，步数越多，这就是 O(N)。
• 二分查找：虽然快很多，但前提是数组必须有序，而且每查一次还要跟中间值比比大小，决定往左还是往右。总共约 log₂N 步，这就是 O(log N)。
• 哈希查找：不需要任何比较。用 key 直接算出下标，一把就把格子打开——无论表里有多少数据（哪怕有一亿个），都是"算一下、看一眼"两步。这就是 O(1)。

哈希能如此之快，根本原因是它把"查找"这个需要逐一看的问题，预计算成了"这一个数据应该在哪"的问题。就像图书馆管理员不靠一本一本翻书找你借的书，而是先在索引卡片上查到索书号，再走到那个书架、那个格子，直接抽出来给你。这里的"索引卡片 + 索书号"，就是哈希函数；"那个书架格子"，就是哈希表里的某个位置。如果管理员每次都要从一楼挨个书架走到顶楼找你那本书，那就是顺序查找；哈希要做的，是"一步跳到正确的格子"。

前置：计算机里的"位置"本质是数组下标

这里立刻会引出一个前置问题：计算机里的"位置"本质上是数组的下标，因为你只能用下标去访问内存。所以你可以把哈希表想象成一个数组，哈希函数负责把 key 映射成一个合法的数组下标，然后元素就存在那个下标对应的格子里。整个哈希的世界，都建立在"用 key 算出下标"这件事上。

为什么必须是"数组下标"？因为数组是唯一支持"常数时间随机访问"的数据结构——只要你给出下标 i，CPU 就能用 基地址 + i × 元素大小 这一个加法运算算出那个元素的内存地址，再访存一次就拿到数据，整个过程跟数组有多长无关。链表做不到（你得从头走到第 i 个），树也做不到（你得沿着路径下传）。所以哈希表的内核，永远是一张数组（C++ 里通常用一个 vector 来当这张数组）。

为了让你直观体会"哈希思想本身就能解决实际算法题"，我给你两个马上就能验证的例子。第一个是用数组打标记去重，第二个是统计每个字母在字符串里出现了几次。第一个例子不依赖哈希函数，数组足够大，直接用 key 当下标；第二个正是后面要讲的"直接定址法"。你先跑一遍，感受"算一下、看一眼"到底是什么体验：

#include <iostream>
using namespace std;
 
// 例 1：判断数组里是否有重复元素（哈希思想：用值当下标做标记）
bool hasDuplicate(int a[], int n)
{
    // 假设所有值都在 [0, 99]，就开 100 个格子的标记数组
    bool marked[100] = {false};
    for (int i = 0; i < n; ++i)
    {
        int val = a[i];
        if (marked[val])       // 这个值已经被标记过了，说明出现过
            return true;
        marked[val] = true;    // 第一次见到，打上标记
    }
    return false;
}
 
int main()
{
    int a1[] = {3, 5, 7, 5, 9};     // 5 出现两次
    int a2[] = {1, 2, 3, 4, 8};     // 全部不同
    cout << "a1 有重复? " << (hasDuplicate(a1, 5) ? "有" : "无") << endl;
    cout << "a2 有重复? " << (hasDuplicate(a2, 5) ? "有" : "无") << endl;
    return 0;
}

看到没有，marked[val] 这一下就是"一步定位"——我没有去跟之前的所有数比大小，而是直接用这个数本身当"门牌号"去看那个格子有没有人。这就是哈希里最核心的直觉。当然你会说：bool marked[100] 写死大小太蠢，万一值跑到 100 之外就越界了。对！这就是我马上要讲的：直接定址法能直接用 value 当下标的前提是"值的范围又小又集中"，这正是它第一个要解决的矛盾——下标和数据的值域之间的拉扯。我们下面正式进入哈希函数，把这件事讲透。

哈希函数：直接定址法

第一种最朴素的哈希函数叫直接定址法。它的思路简单到不需要哈希函数这个概念——当关键字的范围比较集中（比如都在 [0, 99] 这样一个小区间里）时，我们开一个恰好能装下这个范围的数组，把 key 的值直接当成它的存储下标。

要知道它为什么可行，先分清楚两种"位置"：

• 绝对位置：key 的值本身就是一个合法下标（比如数字 0~99，直接当数组下标用）。
• 相对位置：key 减去一个基准值得到下标（比如字符 'a' 的 ASCII 码是 97，就用 ch - 'a' 得到 0）。

无论绝对还是相对，本质都是用 key 的数值直接算出下标，中间不做任何"压缩"或"变换"。这就是"直接定址"四个字的含义——key 和下标基本是一一对应、直奔而去的。

举个例子。假如现在有一组关键字，正好是 [a, z] 这 26 个小写字母，那我们开一个 26 个元素的数组，让每个字母用它的 ASCII 码减去 'a' 的 ASCII 码作为下标。所谓 ASCII 码，就是计算机给每个字符分配的一个整数编号，比如 'a' 是 97，'b' 是 98，以此类推。这样 'a' 存到下标 0，'b' 存到下标 1……于是 count[ch - 'a'] 就是这个字母出现的次数。

这个"字符值减去基准字符得到下标"的手法，你在很多地方都见过，只是当时没意识到它就是哈希。力扣 387 题《字符串中的第一个唯一字符》用的就是这个思路：

#include <iostream>
#include <string>
using namespace std;
 
class Solution {
public:
    int firstUniqChar(string s) {
        // 每个字母的 ascii 码减去 'a' 的 ascii 码，得到 0~25 的下标
        int count[26] = {0};
 
        // 第一遍：统计每个字母出现的次数
        for (auto ch : s)
        {
            count[ch - 'a']++;   // 比如 'b' - 'a' = 1，就往下标 1 加 1
        }
 
        // 第二遍：按顺序找第一个只出现一次的字母
        for (size_t i = 0; i < s.size(); ++i)
        {
            if (count[s[i] - 'a'] == 1)  // 次数为 1，说明这个字母只出现一次
                return i;
        }
        return -1;   // 全部遍历完都没有，返回 -1 表示找不到
    }
};

看到没有，这里 ch - 'a' 就是哈希函数，ASCII 码就是这个例子里"关键字的整数值"。因为字符的编码是连续递增的，直接定址才能让"字符 → 下标"做到一一对应，查找就是 O(1)。

这里摆着题目隐含的一个前提，也正是一个典型的坑：ch - 'a' 只有对 'a'~'z' 才落在 [0, 25]，如果字符串里混进了大写字母或数字字符，count[ch - 'a'] 就会越界，程序会进入未定义行为（UB，Undefined Behavior，指这种行为 C++ 标准不保证任何结果，可能崩、可能内存被踩坏、可能结果莫名错误）。 如果你自己的代码里不能保证这一点，就得先判断范围，或者把 ASCII 所有可打印字符（大概到 127）都囊括进来的数组大小（比如 128）。再给你一句总结："能直接当下标"是直接定址的甜蜜，也是它的边界——你敢越界，它就不跟你客气。

和计数排序的血缘关系

直接定址法你其实早就见过，最典型的就是计数排序（Counting Sort）：对一批取值范围集中（比如都在 [0, 99]）的整数，开一个 100 大小的计数数组 count，先统计每个值出现几次，再根据"比它小的数的个数"确定它的最终位置。它的第一步"count[a[i]]++"，本质就是直接定址法在做哈希：key 直接映射到 count 的下标。所以你可以记住一句话：计数排序就是"直接定址的哈希 + 回填排名"。 哈希不只是用来查的，它武装了排序也武装了去重，是一个通用思想。

直接定址法的局限一眼就能看出来：它要求关键字的范围又小又集中。如果数据范围从 0 到 9999，但真正的数据只有 N 个（比如 100 个），你要为了这 100 个数开一个一万个格子的数组——绝大多数格子空着，内存白用，这就是浪费。数据范围再大一点，甚至内存根本装不下。所以直接定址法只适用于关键字范围很小、很集中的场景，一旦范围分散，就需要更聪明的做法了。

这里还能再往前推一步：当值的范围大到"存不下"时，有些人会用一个简化版——位图（bitmap）。还是那句话，哈希的世界里，你可以用 1 bit 来表示"某个数出现过没有"，省内存省到极致。但那属于更底层的优化，我们这里点到为止。对绝大多数情况，你要解决的正是这个矛盾：key 的取值浩瀚无边，而你要把它压缩进可怜的几个格子里。 于是就有了下一个主角——除留余数法。

哈希函数：除留余数法

既然不能总把 key 直接当下标，那就换个思路：压缩。这就是除法散列法，也常叫除留余数法——这个名字直白得可爱，就是把 key 除以表的大小 M，用余数当存储下标，即：

h(key) = key % M

这样一来，无论 key 范围多大，模出来的余数总落在 [0, M) 这个合法下标区间内。它把一个"无限大的世界"压缩进了"M 个格子"。一句话，除留余数法用取模运算，强行把 key 映射到合法下标区间里。

先澄清一个概念：对"哈希函数"来说，h(key) = key % M 的这个 M 越大，映射就越分散；而"表的大小"也常用 M 表示。在这篇文章里，除非特别说明，M 就代表哈希表的大小（也就是数组格子的总数），h(key) 的取值落在 [0, M) 之间。这是课件和代码里的统一约定，你记牢它。

#include <iostream>
using namespace std;
 
int main()
{
    size_t tableSize = 11;   // 假设哈希表大小 M = 11
    int a[] = {19, 30, 5, 36, 13, 20};
 
    // 用 key % M 算出每个值应该放的位置
    for (int key : a)
    {
        size_t idx = key % tableSize;   // 除留余数法
        cout << "key=" << key
             << " -> 位置 " << idx << endl;
    }
    return 0;
}

用这组数据算一下：19 % 11 = 8，30 % 11 = 8，5 % 11 = 5……你先记着这几个结果，后面讲冲突会用到。这里已经埋下一个伏笔：19 和 30 的余数都是 8，这俩会抢同一个位置，这就是马上要讲的"冲突"。

坑一：负数取模，结果可能是负的

这是 C++ 取模运算里最经典的陷阱之一。数学上，(-20) / 11，我们习惯的余数取法是"商向负无穷取整，余数为非负"，于是 -20 % 11 在数学里等于 2（因为 -20 = 11 × (-2) + 2）。但 C++（以及 C）规定了不同的规则：商向 0 取整，余数的符号和被除数相同。于是 -20 % 11 在 C++ 里等于 -9（因为 -20 = 11 × (-1) + (-9)）。看，结果变成负数了。如果哈希函数算出一个负数，用它当数组下标，直接就越界崩溃了。所以凡是你的 key 可能是负数，取模前得先 "转正"。标准做法是加上 M 再取模（一次通常就够了，因为 -M < 负数 < 0 时，+M 就能回到 [0,M)）：

#include <iostream>
using namespace std;
 
int main()
{
    size_t M = 11;
    int key = -20;
 
    int bad = key % (int)M;               // 错误示范：得到 -9，负数下标！越界
    size_t good = ((key % (int)M) + (int)M) % M;  // 正确：先 +M 再 %，得到 2
 
    cout << "bad  = " << bad  << "  (负数！不能当下标)" << endl;
    cout << "good = " << good << "  (落在了 [0,M))" << endl;
    return 0;
}

这个坑在我们下面的实现里不显眼，是因为演示用的都是正整数；但一旦你让哈希表接 base 用户输入（键盘输入可能有负数），它就立刻冒出来。记住：哈希函数的目标是把 key 映射进 [0, M)，任何能让结果为负的写法都要先修正。

坑二：表大小 M 别取 2 的幂、10 的幂这类"规律"的数

这里有个非常实际的坑：用除留余数法时，表的大小 M 最好不要是 2 的幂、10 的幂这类"规律"的数。为什么？因为如果 M = 16（也就是 2 的 4 次方），那么 key % 16 本质上是保留 key 二进制的后 4 位——后 4 位相同的数，取模结果就一模一样，必定冲突。比如 63 和 31，二进制后 8 位分别是 00111111 和 00011111，它俩的 % 16 都是 15，八竿子打不着的两个数就撞上了。同理，如果 M 是 10 的幂，比如 100，那 key % 100 保留的是十进制的后两位，112 和 12312 取模都是 12，也撞了。

为什么 x % 2ⁿ 恰好等于"后 n 位"？因为二进制的位权"低位"对应小幂次：一个数除以 16，商是它"去掉低 4 位后的高部分"，余数正是它的低 4 位；同理对 10 进制，除以 100 的余数就是十进制的低两位。这说明：当 M 是 2/10 的幂时，我们等于扔掉了 key 的高位信息，只用了低位，而很多真实数据的低位恰恰分布很不均匀（比如一票 ID 都带相同的尾号）。你想想：如果数据全是偶数（key 的二进制最低位恒为 0），用 M = 16 取模，就永远碰不到奇数的目标下标，表的一半格子直接"被跳过"，冲突全挤在另一半里——这也是"为什么序数/编号类 key 选 2 的幂当表大小是灾难"的典型原因。

所以教材上的建议是：M 尽量取一个不太接近 2 的整数次幂的质数（素数）。老生常谈一句：质数即素数（只能被 1 和它本身整除的自然数），比如 53、97、193 都是质数。为什么质数好？因为在很多常见数据形态下，质数能让 key % M 尽可能"打乱"规律，减少因子带来的周期性碰撞。比如我们下面代码里用的质数表，就是把"接近 2 倍、同时又是质数"的大小一个个列出来，扩容时直接取用。这也是 SGI 版 STL 哈希表（unordered_* 的鼻祖之一）采取的做法。

需要说明的是，实践里也是八仙过海。比如 Java 的 HashMap 就敢用 2 的幂做表大小，因为这样取模可以退化成位运算（x & (M-1)），比真正做除法取模更快。但人家不是傻乎乎直接取后 n 位，而是先做一轮key ^ (key >> 16)（把高位的信息"混"到低位）再取低位，尽量让关键字的每一位都参与计算，好让结果分布更均匀。这里只想告诉你："M 取质数"是绝大多数教科书的理论标准，但实践要灵活，抓住"让冲突尽量少"这个本质，不能死读书。

表大小 M 到底怎么选：一份可直接抄的质数表

既然 M 要质数、又要"接近 2 倍递增"（这样扩容后空间不至于猛翻导致稀疏浪费、也不至于只涨一点点导致频繁扩容），工程上用一份预置质数表是最省心的做法：扩容时直接用 lower_bound 在质数表里找"第一个不小于目标值"的质数。lower_bound 是 <algorithm> 里对已排序区间做"二分查找"的函数，返回第一个不小于给定值的元素位置——它是二分查找的推广，前面说二分需要有序，这里正好用到。这份质数表就是 SGI STL 里的 __stl_prime_list，我把它原样抄给你（最后一个值已超过 32 位 unsigned，需加上 UL 后缀表示 unsigned long，否则可能编译告警）：

#include <algorithm>
#include <cstddef>
#include <iostream>
using namespace std;
 
// 找到 >= n 的、接近 2 倍递增的质数（SGI STL 质数表）
inline size_t nextPrime(size_t n)
{
    static const size_t primeList[] = {
        53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
        49157, 98317, 196613, 393241, 786433, 1572869, 3145739,
        6291469, 12582917, 25165843, 50331653, 100663319,
        201326611, 402653189, 805306457, 1610612741, 3221225473UL,
        4294967291UL
    };
    const size_t* first = primeList;
    const size_t* last  = primeList + sizeof(primeList) / sizeof(primeList[0]);
    const size_t* pos   = lower_bound(first, last, n); // 在有序质数表里二分找 >= n 的
    return pos == last ? *(last - 1) : *pos;           // 若 n 比表里最大的还大，退化取最大质数
}
 
int main()
{
    cout << "大于等于 0  的质数: " << nextPrime(0)   << endl;  // 53
    cout << "大于等于 54 的质数: " << nextPrime(54)  << endl;  // 97
    cout << "大于等于 200 的质数: " << nextPrime(200) << endl; // 389
    cout << "大于等于 400 的质数: " << nextPrime(400) << endl; // 769
    return 0;
}

为什么开头要 nextPrime(0)？因为表初始也要给一个质数大小，用 0 就取到表里第一个质数 53（53 符合"质数且避开 2/10 幂"，对演示足够）。这份质数表在后面闭散列和哈希桶代码里都会复用，我先放在这里，你只需要关心"我们用质数表来生成表大小"这件事，二分那行可以直接当成工具用，不必纠结。

三个"了解即可"的哈希函数（拓宽视野，不要求实现）

《算法导论》在讲哈希函数时，还给了几个我们在纯手写时不用的方案。它们不改变你写代码的方式，但能让你读源码/面试时不掉链子，我逐个讲清楚它是什么、解决了什么、有什么坑。

乘法散列法

乘法散列法对表的大小 M 没有任何要求（不像除留余数法要挑质数），思路分成两步：

1. 用 key 乘上一个界于 0 和 1 之间的常数 A，然后取出乘积的小数部分；
2. 再用 M 乘上这个小数部分，并向下取整。

写成公式（floor 表示向下取整，即取不超过该数的最大整数；%1.0 是"取小数部分"的花哨写法）：

h(key) = floor( M × ( (A × key) % 1.0 ) ),   A ∈ (0, 1)

关键就在 A 的取值。 著名计算机科学家 Knuth（克努特，就是写《计算机程序设计艺术》那位）认为 A 取黄金分割比最理想：

A = (√5 − 1) / 2 = 0.6180339887...

为什么是黄金分割？因为"乘法散列"是依赖 A × key 的小数部分的均匀性，而黄金分割的连分数性质使得它在很多 key 形态下都能给出均匀且"无周期"的小数分布——这是一个经过数学论证的"好常数"。课上不要求你证明，记住结论即可。

举个例子验证：设 M = 1024，key = 1234，A = 0.6180339887。则 A × key = 762.653942056，小数部分为 0.653942056；M × 0.653942056 = 669.63666，向下取整得 h = 669。也就是说 key=1234 映射到下标 669。注意到 key % 1024 远没有这么"散"（毕竟 1234 和某个低 10 位相同的数会长城打架），乘法散列靠"取小数部分"把高低位的分布都揉进来了。下面这段代码你可以自己改 key 试试，感受它"对 M 无要求" :

#include <cmath>
#include <cstddef>
#include <iostream>
using namespace std;
 
double A = (sqrt(5.0) - 1.0) / 2.0;   // 黄金分割比 (~0.618)
 
size_t multiplicativeHash(size_t key, size_t M)
{
    double frac = A * key;                // 第一步：A * key
    frac -= floor(frac);                  // 取出小数部分（A*key % 1.0）
    return (size_t)floor(M * frac);       // 第二步：M * 小数部分，向下取整
}
 
int main()
{
    cout << "key=1234, M=1024 -> " << multiplicativeHash(1234, 1024) << endl; // 669
    cout << "key=2345, M=1024 -> " << multiplicativeHash(2345, 1024) << endl;
    cout << "key=3456, M=1024 -> " << multiplicativeHash(3456, 1024) << endl;
    cout << "key=1234, M=53  -> " << multiplicativeHash(1234, 53) << endl;
    return 0;
}

注意两个细节：sqrt/floor 需要 <cmath>；结果落在 [0, M) 自然是 size_t 非负。它的坑在于：要算一次浮点乘法和取整，比整数取模慢，而且浮点舍入在不同关键字上可能诱发微小不一致，工程里并不常用，属于"理论了解"的范畴。

全域散列法

这是为了防"恶意攻击"而生的。设想一个场景：哈希函数是公开且完全确定的。那么攻击者完全可以把程序摸透，故意构造一批 key，让它们全部命中间一个位置——比如针对 h(key) = key % M，直接塞 M、2M、3M、4M……这些取模全是 0 的 key，哈希表立刻退化成一条超级长的链表，查找从 O(1) 变成 O(N)。这叫做针对哈希表的拒绝服务攻击（DoS，Denial of Service，让系统因被拖慢而瘫痪）。现实中，某些网站上曾经真的出现过利用"哈希碰撞攻击"把服务器拖垮的案例，所以这不是杞人忧天。

破解思路是"见招拆招"：让哈希函数带随机性，攻击者就没办法预先构造必坏的输入。 这就是全域散列（Universal Hashing）。做法是在初始化哈希表时，从一族哈希函数里随机选一个出来，之后固定用它。常用的随机一族是这个样子：

h_{a,b}(key) = ( (a × key + b) % P ) % M

其中 P 选一个足够大的质数，a 从 [1, P-1] 里随机取，b 从 [0, P-1] 里随机取。(a,b) 有多少种组合，这族函数就有多少个——总共 P × (P-1) 个。因为每次建表随机挑一个，攻击者没法事先知道你会抽到哪个，也构造不出"无论如何都必坏"的输入。课件给的例子：P = 17, M = 6, a = 3, b = 4，则对 key = 8：

h(8) = ((3 × 8 + 4) % 17) % 6 = (28 % 17) % 6 = 11 % 6 = 5

一个极其重要的坑：一旦初始化时挑定了一组 (a, b)，后面所有增删查都必须用同一组 (a, b)。 如果你每次操作都重新随机一个哈希函数，那么插入时用的是函数 A 算的位置，查找时却用函数 B 算位置——两个位置大概率不同，你永远都找不到自己刚插进去的数据。这就像你给每本书编了个新的藏格编号，但转过头又用另一套编号去找书，当然找不到。所以"随机一次、固定使用"是全域散列的铁律。下面这段代码演示了整个流程：

#include <iostream>
#include <random>
using namespace std;
 
// 用 (a,b) 参数化的全域散列函数
struct UniversalHash
{
    size_t a, b, P, M;          // a∈[1,P-1], b∈[0,P-1]，P是大质数
    size_t operator()(size_t key) const
    {
        return ((a * key + b) % P) % M;
    }
};
 
int main()
{
    const size_t P = 1000000007;   // 足够大的质数
    const size_t M = 11;           // 哈希表大小
 
    // 建表时随机挑一组 (a,b)，之后固定使用
    mt19937 rng(random_device{}());
    size_t a = uniform_int_distribution<size_t>(1, P - 1)(rng);
    size_t b = uniform_int_distribution<size_t>(0, P - 1)(rng);
 
    UniversalHash h{a, b, P, M};
    cout << "这次抽到的哈希函数 a=" << a
         << ", b=" << b << endl;
    cout << "key=123  -> " << h(123) << endl;
    cout << "key=456  -> " << h(456) << endl;
    cout << "key=123  -> " << h(123) << "  (永远固定用它，结果一致)" << endl;
    return 0;
}

mt19937 是 C++11 提供的高质量伪随机数引擎，random_device 用来给它播种，uniform_int_distribution 是生成某区间内"均匀分布"整数的工具——如果你没见过随机数这堆东西，先记住"一次随机、固定使用"这条规则即可，把 random 三行当工具用，这并不影响我们哈希学习的主题本身。全域散列在工程里确实有应用（比如某些语言的字符串哈希实现、数据库防止碰撞攻击的选项），它代表的思想比代码本身更重要：给确定性加入随机性，是防针对攻击的通用武器。

其他教科书方法（只需混个脸熟）

《殷人昆 数据结构》和严蔚敏的《数据结构（C 语言版）》等教材还列了一些给"特定场景"用的方法，我列个清单一笔带过，你在面试时听说过名字、能一句话说明白即可：

这些方法的共同点都是**"把 key 的信息打散、尽量均匀地压进下标区间"**——抓住这一条，无论它们多花哨都不会跑偏。

哈希冲突

前面 19 和 30 撞车的现象，正式名字叫哈希冲突，也叫哈希碰撞（collision）。定义很直白：两个不同的 key，被哈希函数算到了同一个位置，这就是冲突。

你可能会天真地想：那就找一个"完美"的哈希函数，让所有 key 永远不冲突呗。很遗憾，这在理论上是几乎不可能的。假设你有 N 个 key 要映射进 M 个格子里（通常 M >= N），当 N 大到一定程度，"鸽子笼原理"就发威了——M 个格子塞 N 只鸽子，总有格子要挤两个。更何况真实数据往往是未知的、不均匀的，比如你恰好碰上一批"生日"都相同的 key，无论哈希函数设计得多优雅，冲突都无法根除。

让我把"为什么冲突躲不掉"再用数学帮你钉死：如果 key 的取值空间比 M 大（或者说 N > M），鸽子笼原理直接断言必有冲突；就算 N ≤ M，只要 key 的分布不是"恰好每个 key 落在不同格"，冲突依然可能发生——而数据本身往往是"扎堆"的（比如全偶数、全某结尾的 ID）。所以结论是：不是"我们没设计好",而是哈希从结构上讲无法保证无冲突，除非你对全部数据都已知且预先精确排布——那叫完美哈希（perfect hashing），是在"数据固定不变、可离线设计"的极少数场景（比如关键字集的静态字典）才可能做到的，不是通用解法。

你可以用一个生活化的实验来体会"看起来不该撞，却偏偏会撞"：生日悖论。一个房间里只要 23 个人，就有超过 50% 的概率出现"至少两个人同一天生日"。你直觉觉得 23 个人撞生日的概率应该很小，但实际算出来已经过半了——因为"有碰撞"这件事要考虑的是两两配对，(23×22)/2 有 253 对呢。哈希冲突的概率增长方式是类似的：随着填入的数据变多，碰撞概率比线性增长得还猛。下面这段代码让你自己感受一下：

#include <iostream>
#include <iomanip>
using namespace std;
 
// 计算 n 个不同的 key 均匀散列到 M 个格子时，"至少发生一次冲突"的概率
double collisionProb(int n, int M)
{
    double pNoCollide = 1.0;              // 先假设"完全没冲突"的概率为 1
    for (int i = 0; i < n; ++i)
        pNoCollide *= (double)(M - i) / M; // 一个一个塞，每塞一个没撞的概率累乘
    return 1.0 - pNoCollide;               // 有冲突 = 1 - 没冲突
}
 
int main()
{
    cout << "M=100 的哈希表填 n 个数据，至少一次冲突的概率：" << endl;
    for (int n = 5; n <= 50; n += 5)
    {
        cout << "  n=" << setw(2) << n << " -> "
             << fixed << setprecision(3) << collisionProb(n, 100)
             << endl;   // 你会看到它涨得非常快
    }
    return 0;
}

运行后你会发现：才填到 20 个（表 100 个格子，只用了两成），冲突概率已经逼近 90%。这就是为什么工程上绝不指望"哈希函数完美"，而是既要设计好哈希函数减少冲突，又要设计解决冲突的方案来兜底。

所以正确的心态是：冲突不可避免，我们能做两件事——设计优秀的哈希函数减少冲突，以及设计解决冲突的方案兜底。解决冲突的主流方案有两种，正好对应我下面两大章：

• 开放定址法（闭散列）：所有数据都塞在哈希表自己的格子里，冲突了就在表里找下一个空位。
• 链地址法（开散列 / 哈希桶）：表里每个格子放一个链表，冲突了就把所有撞车的数据串成一串链表挂在该格子下面。

这两条路线你会看到，实践里链地址法（哈希桶）明显更主流，因为开放定址法用的始终是别人占着的表内空间，格子和格子之间"你挤我、我挤你"，互相影响，这是它结构上的先天弱点。我们后面会亲身体会到这个差异。

负载因子：什么时候该扩容

在讲两种方案之前，必须先搞懂一个关键指标——负载因子（load factor，有些地方翻译成载荷因子、装载因子）。它的定义就一行公式：

负载因子 α = N / M

其中 N 是已经存进表里的数据个数，M 是表的总大小（格子数）。你一听就明白它的含义：表被"装满"的程度。

负载因子高低的权衡是这样的：负载因子越大，空间利用率越高（格子不浪费），但冲突概率也随之升高，查找变慢；负载因子越小，冲突越少查找快，但大量格子空闲，浪费内存。这个"装多省空间但慢、装少浪费但快"的拉扯，就是设计哈希表时第一个要权衡的点。

负载因子和"平均探测次数"到底什么关系

"负载因子太大会变慢"到底有多慢？这背后其实有精确的定量结论。对线性探测的开放定址表（在负载因子为 α 时）：

• 一次成功查找的平均探测次数约为：(1 + 1/(1-α)) / 2
• 一次不成功查找（要确认 key 不存在）的平均探测次数约为：(1 + 1/(1-α)²) / 2

你代入算一下就懂了：α = 0.5 时，成功查找平均约 1.5 次、不成功约 2.5 次，很舒服；但 α = 0.9 时，成功查找平均约 5.5 次，不成功查找暴涨到约 50.5 次！这就是为什么"表快满的时候查一个不存在的 key 会特别慢"。这些公式不用背，你只要抓住直觉：越接近满，探测次数不是线性涨，而是像坐过山车一样暴涨。 这也是开放定址表不约而同把负载阈值定在 0.7 附近（留出余裕）、链地址表敢到 1.0 再扩容（每格一条链，不容易"爆炸"）的根本理由。

负载因子还派生出两个截然不同的硬性约束，区分度非常高：

• 开放定址法：因为所有数据都住在表里，负载因子必须小于 1——一旦等于 1 表就满了，冲突的数据彻底无处安放。这是物理上的硬限制。
• 链地址法：数据挂在链表的桶里，表本身只是装指针，所以负载因子可以大于 1。STL 的 unordered_* 一般把最大负载因子控制在 1，大约 1 就触发扩容。

一句话记忆：负载因子是"该不该扩容"的扳机。我们实现的时候，就盯着这个比值，到了阈值就触发放大——这正是后面代码里那句判断要干的事。

扩容的代价与均摊分析：为什么偶尔"重来一次"也能接受

扩容（rehash）意味着要把旧表里的数据全部重新计算位置，搬进更大的新表（因为表大小变了，key % 新M 的结果几乎全变了，不能只把格子复制过来）。这是一次 O(N) 的搬家。你可能会问：那岂不是每扩一次容就要慢一次？

这就是均摊分析（amortized analysis）的用武之地。它回答的是另一个问题：如果没有一次性，而是把 N 次插入的总代价摊到每次插入头上，平均每次多少？ 我们以"翻倍扩容"为例推演：假设表从 M 开始不停翻倍，第 1 次插入可能触发规模 M 的搬运、第 2 次触发规模 2M、第 3 次触发规模 4M……总共翻倍 log N 次，搬家的总数据量大约是 M + 2M + 4M + ...，这是一个等比数列，它的和只比最大那一项大常数倍（等比求和是首项×(公比ᵏ−1)/(公比−1)，公比 2 时和约等于最大项的 2 倍）。也就是说，N 次插入的总代价是 O(N)，摊到每次就是 O(1)——即"哈希表的插入平均 O(1)"。多项式"偶尔贵一次，但平均下来很便宜"，和你每月房租固定、偶尔家电大修一次类似的道理。

这个均摊结论非常重要，它保证了我们手写的哈希表在"不断扩容 + 不断插入"的整体流程里，平均每一个数据仍然只花常数时间。你不用担心"扩容把性能拖垮"，只要扩容系数不是 1（比如翻 2 倍或按质数表翻约 2 倍），均摊就是 O(1)。下面这段是均摊扩容的手工演示——你看它会把"扩容瞬间的花费"摊平到每一次插入上：

#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    // 模拟哈希表"M 个格子、存 N 个数据"扩容时的总搬运工作量
    size_t M = 1;
    long long totalWork = 0;
    for (int round = 0; round < 10; ++round)  // 连扩 10 次容
    {
        totalWork += M;        // 这次扩容要搬运的旧数据量
        M *= 2;                // 表翻倍
    }
    // 最终表大小 M，累计搬运 totalWork
    cout << "最终表大小: " << M << endl;
    cout << "累计搬运总量(约2倍M): " << totalWork << "  (~" << 2 * M << ")" << endl;
    // 结论：总搬运量只比最终表大小大常数倍 => 均摊到每次插入是 O(1)
    return 0;
}

最后留一个易混淆点：上面的"均摊 O(1)"针对的是"不断插入+扩容"的整体。而"查找一个不存在的 key 的最坏情况"，在开放定址表里可能探测很多次——那是另一码事（取决于负载因子和堆积）。一个说的是"平均总代价"，一个说的是"单次最坏"，不要混为一谈。想看最坏，就要想堆积；想看平均，才用均摊。

字符串的哈希：BKDR

哈希函数要对 key 取模，可 key 的类型经常不是整数——最常见的例子就是字符串 "hello"。但取模是整数运算，字符串没法直接 %。所以这里有个绕不开的处理：把非整数类型的 key，想方设法转换成一个整数，这个"把 key 变整数"的活儿，在 C++ 里适合用仿函数（其实就是一个定义了 operator() 的对象，可以让对象"像一个函数一样被调用"）来完成。仿函数的好处是它能作为模板参数传给 HashTable<K, V, Hash>，让用户想怎么哈希就怎么哈希，这就是"策略注入"——Hash 这个模板参数像一个可替换的"插槽"，默认用 HashFunc<K>，遇到 string 就自动用特化版。

最朴素的字符串转整数办法是把所有字符的 ASCII 码加起来。但这里有个明显的坑："abcd" 和 "bcad" 的和完全一样，因为它们只是排了个序，字符种类和数量没变，这样两个不同的字符串就产生了同样的整数值，白白制造冲突。更糟的是"ab" 和 "ba"、以及任何"相同字符不同顺序"的组合全都撞在一起，这种哈希对"含相同字母的单词族"几乎完全失效（比如单词、字母重排词），毫无区分度。

更好的方案就是 BKDR 哈希，思路一句话：用一个质数，边遍历边累乘，让字符在字符串里的"位置信息"也被保留下来。具体是每次用上一次的结果乘以一个质数（比如 31、131 这类效果较好），再加上当前字符的编码。因为你乘了质数，字符串里字符的顺序会显著影响最终结果，"abcd" 和 "bcad" 就算出不同的整数了。

为什么"累乘一个质数"就能保留位置信息

我们从数学上拆解一下。BKDR 的公式是（从第一个字符开始）：

hash = 0
hash = hash × seed + ch[0]
hash = hash × seed + ch[1]
...

展开到最后，对于一个长度为 k 的字符串 c[0] c[1] ... c[k-1]，你得到的其实是：

hash = c[0]·seed^(k-1) + c[1]·seed^(k-2) + ... + c[k-2]·seed + c[k-1]

这不就是一个 k 位、以 seed 为底的多项式求值吗？ 每个字符都乘上了"由它的位置决定"的 seed 的若干次方，所以位置不同、乘的权不同、贡献不同——"abcd" 和 "bcad" 必然得到不同的值（因为每一位的系数因位置而异）。这就把"顺序"这个关键信息牢牢编码进了最终整数里。而朴素的"直接求和"等价于所有字符的系数都是 1，顺序信息被彻底丢弃，各种排列全都撞车——这就是它失败的数学根源。

那为什么 seed 要选质数（31、131 这类）？两个原因：

1. 减少"乘法裂缝"的巧合冲突：如果 seed 与字符编码有共同的因子，就可能出现某些低位组合"巧合相等"。选质数，尤其是和 2、和常用字符编码（通常低 7 位是 ASCII）互质的奇数，能显著减少这种系统性碰撞。
2. 经验值：31、131、929 等是实践中验证过"分布较均匀"的乘数——它们被大量实验和第三方哈希实现反复验证过，31 是 Java String.hashCode() 用过的（Java 里字符串哈希就是 s[0]*31^(n-1) + ... + s[n-1]，跟 BKDR 是同一族思想），131 是很多国产教材爱用的。它们都是质数，且不是 2/10 的幂，配合取模时不容易引发规律性冲突。

下面这段代码，请你亲眼对比"求和 vs BKDR"在撞"重排词"时的表现差异：

#include <iostream>
#include <string>
using namespace std;
 
// 朴素求和：相同字母的重排，算出来完全一样（大量冲突）
size_t sumHash(const string& s)
{
    size_t h = 0;
    for (auto ch : s) h += (size_t)ch;
    return h;
}
 
// BKDR：位置不同乘的权不同，重排词也能区分开
size_t bkdrHash(const string& s, size_t seed = 131)
{
    size_t h = 0;
    for (auto ch : s) { h = h * seed + (size_t)ch; }
    return h;
}
 
int main()
{
    string w1 = "abcd", w2 = "bcad";   // 同一批字母，只是重排
    cout << "sum  : \"abcd\"=" << sumHash(w1) << ", \"bcad\"=" << sumHash(w2)
         << "  -> " << (sumHash(w1) == sumHash(w2) ? "冲突！" : "不同") << endl;
    cout << "BKDR : \"abcd\"=" << bkdrHash(w1) << ", \"bcad\"=" << bkdrHash(w2)
         << "  -> " << (bkdrHash(w1) == bkdrHash(w2) ? "冲突" : "不同!") << endl;
    return 0;
}

现在把它落成"可当哈希函数用"的仿函数。注意我给 string 做了模板特化（专门为某一种类型写一份不同的实现），这样后面两种哈希表都能共用它：

#include <iostream>
#include <string>
using namespace std;
 
// 通用哈希函数：把 key 转成可以取模的整数（默认按整型处理）
template<class K>
struct HashFunc
{
    size_t operator()(const K& key)   // 仿函数，让对象能 "像函数一样调用"
    {
        return (size_t)key;           // 默认是整型 key，直接强转成 size_t
    }
};
 
// 对 string 做特化：专门处理字符串
template<>
struct HashFunc<string>
{
    size_t operator()(const string& key)
    {
        size_t hash = 0;
        for (auto ch : key)   // 逐个字符处理
        {
            hash *= 131;      // BKDR：先乘以一个质数 131
            hash += ch;       // 再加上当前字符的编码
        }
        return hash;          // 返回转换出的整数
    }
};
 
int main()
{
    HashFunc<string> hash;                 // 构造一个字符串哈希仿函数对象
    size_t idx1 = hash("hello") % 11;      // 转成整数后再取模
    size_t idx2 = hash("world") % 11;
    cout << "\"hello\" 的位置: " << idx1 << endl;
    cout << "\"world\" 的位置: " << idx2 << endl;
    return 0;
}

关于"字符串哈希的坑"再补两句

第一，size_t 是大整数，字符串哈希的中间结果很容易溢出——但这未必是坏事。反过来看，无符号整数（size_t）溢出是按模 2^64（用 unsigned long long 时）回绕的，也就是说溢出本身等价于"自动取了一次模 2^64"，结果依然是确定性的，BKDR 依然可用。所以我们不需要刻意防溢出。真正要防的是下面两点。

第二，标准库 unordered_map<string,...> 到底用什么哈希？ 它用的是 std::hash<std::string>。注意，C++ 标准并没有规定 std::hash<string> 的具体算法（标准只说"每个标准库容器/类型都提供以 hash<> 特化的哈希器，且对相等的字符串返回相等的哈希值"），实现细节完全交给各标准库厂商。据大众实现：libstdc++（g++ 用的）对 string 走的是类 MurmurHash 的思路，libc++（clang++ 用的）走的接近 FNV-1a 一族——都是比 BKDR 更"现代专业"的字符串散列。也就是说，BKDR 是我们手写学习用、好懂又有区分度的方案；真实 STL 用的是另一套已优化的方案，两者目的相同（把字符串均匀摊开）。这句话帮你看清"学习的 BKDR"与"工程里的 std::hash"不是同一个东西，避免误读源码。

第三，哈希大整数时 key 可能超过 size_t 范围或为负数。对 int 型 key 我们用 (size_t)key 强转：负数强转成无符号数后，其位模式不变（比如 -1 转成 size_t 是 0xFFFFFFFF...），取模会落在表里某处，保证了非负、合法，这正是在 C++ 里"把可能有负的整数 key 变成合法下标"的标准做法。它牺牲的是"负数和它表象"的语义，但没有 UB、安全性有保障——这正是 (size_t)key 这里強转的意义所在。

字符串做 key 这事太常见，所以特化它完全值得。你以后用 unordered_map<string,...> 时，看到的正是"类型 → 整数 → 取模 → 定位"这条流水线。

闭散列：线性探测

现在开始上第一道硬菜——开放定址法（闭散列）。它的中心思想前面提过：所有元素都放在哈希表自己的格子里，当 key 算出的位置已经被占了，就按照某种规则在表里找一个没被占的空位放进去。因为数据只存在表里、不外溢，所以叫"闭散列"，也正因为如此，它的负载因子必须严格小于 1。

开放定址法里"找空位"的规则有很多种，最常见也最简单的就是线性探测。规则一句话：从冲突的位置开始，依次向后（下标加 1、加 2、加 3……）一个格子一个格子地找，直到找到一个空格；走到表尾就绕回表头继续找。用公式表示：

hashi = (hash0 + i) % M，  i = 1, 2, 3, ...

这里的 hash0 = key % M 是起始位置，i 是第几次探测。因为负载因子小于 1，表里肯定有空位，所以最多探测 M-1 次必然能找到地方放。

那为什么"走到表尾要绕回表头"（也就是那句 "% M"）？因为哈希表是一块逻辑上首尾相接的环形区域：你想像把数组的最后一个格子的下一个格子"接到"第一个格子，这样就永远不会因为"走到头"而停下，而是一直绕圈找。C++ 里实现绕圈非常便宜——不必真的把数组做成环，只要下标加一后再 % M 一下，就让"越界的 11"自动回到 0。所以前面公式里每个探测位置都带 % M，正是为了这个"环形取模"。

我们拿课件里的例子 {19, 30, 5, 36, 13, 20, 21, 12}，映射到 M = 11 的表里验证一下。先算初始位置：19→8、30→8、5→5、36→3、13→2、20→9、21→10、12→1。插 19 占下标 8；插 30 时发现 8 已经被 19 占了，于是向后探测，8→9 空，所以 30 放到 9；接着插 5 放 5，36 放 3，13 放 2，20 一算是 9，但 9 已经被 30 占了，再向后到 10，空，20 放 10；21 算得 10 也被占，向后到 11%11=0，空，放 0；12 算得 1 空，放 1。

等等，这里插到最后已经出现"20 明明该去 9，却因为 9 被 30 占了去了 10；21 明明该去 10，却又被 20 占了去了 0"——后面的数据被迫越走越远。这就是教科书说的"入坑连锁反应"：一个新来的数据，可能会把原来属于别处的空位也一起占了，导致后面的数据又得继续往后探。这个现象就是下一节要讲的堆积（群集）。你现在先用眼睛把这张表画出来：0:21 1:12 2:13 3:36 5:5 8:19 9:30 10:20，中间还空着 4、6、7 三个格子。注意，冲突并没有让任何数据"迷路"——只要它们初始位置相同或逼近，沿着 '加1取模' 一路向后，一定还能在某个空位安置，这就是线性探测"一定能放下"的保证（前提是负载因子 < 1）。

理解了线性探测的手工推演，我们把它落成代码，同时把哈希表的骨架搭起来。闭散列的每个格子自带一个状态（EMPTY 空 / EXIST 有数据 / DELETE 删除），这个状态字段是后面的关键，我先把它放进去：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
// ===== 通用哈希函数 + 字符串特化（定义在命名空间外，两种表共用）=====
template<class K>
struct HashFunc
{
    size_t operator()(const K& key) { return (size_t)key; }
};
template<>
struct HashFunc<string>
{
    size_t operator()(const string& key)
    {
        size_t hash = 0;
        for (auto ch : key) { hash *= 131; hash += ch; }  // BKDR
        return hash;
    }
};

注意我这里的 HashFunc 只带一个模板参数 K，并给 string 做了模板特化。下面这份可直接编译运行的完整闭散列实现会直接用 HashFunc<K> 作为默认哈希函数：

namespace open_address   // 闭散列：开放定址法
{
    // 每个格子的状态标识
    enum State
    {
        EMPTY,    // 空格子
        EXIST,    // 已存数据
        DELETE    // 曾被删除（墓碑）
    };
 
    // 一个存储单元 = 键值对 + 状态
    template<class K, class V>
    struct HashData
    {
        pair<K, V> _kv;       // 键值对
        State _state = EMPTY; // 默认是空的
    };
 
    template<class K, class V, class Hash = HashFunc<K>>
    class HashTable
    {
        // 取得一个"接近2倍、且是质数"的表大小（来自质数表）
        static size_t nextPrime(size_t n)
        {
            static const size_t primeList[] = {
                53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
                49157, 98317, 196613, 393241, 786433, 1572869, 3145739,
                6291469, 12582917, 25165843, 50331653, 100663319,
                201326611, 402653189, 805306457, 1610612741, 3221225473UL,
                4294967291UL
            };
            const size_t* first = primeList;
            const size_t* last = primeList + sizeof(primeList) / sizeof(primeList[0]);
            const size_t* pos = lower_bound(first, last, n);  // 找第一个 >= n 的质数
            return pos == last ? *(last - 1) : *pos;          // 越界就取最大质数
        }
 
    public:
        HashTable()
        {
            _tables.resize(nextPrime(0));   // 初始给一个质数大小
        }
 
        // 插入
        bool Insert(const pair<K, V>& kv)
        {
            if (Find(kv.first))       // 如果 key 已存在，不再插入
                return false;
 
            // 负载因子 = N/M，用 *10 再比较，避免浮点误差
            if (_n * 10 / _tables.size() >= 7)   // 达到 0.7 就扩容
            {
                rehash();
            }
 
            Hash hash;
            size_t hash0 = hash(kv.first) % _tables.size(); // 起始位置
            size_t hashi = hash0;                           // 当前探测位
            size_t i = 1;
            while (_tables[hashi]._state == EXIST)          // 被占就继续探测
            {
                hashi = (hash0 + i) % _tables.size();       // 线性探测
                ++i;                                        // 下一次距离 +1
            }
            _tables[hashi]._kv = kv;        // 放入空格
            _tables[hashi]._state = EXIST;  // 标记为已存
            ++_n;
            return true;
        }
 
        // 查找
        HashData<K, V>* Find(const K& key)
        {
            Hash hash;
            size_t hash0 = hash(key) % _tables.size();
            size_t hashi = hash0;
            size_t i = 1;
            // 遇到 EMPTY 就停：空位置说明后面不会有该 key
            while (_tables[hashi]._state != EMPTY)
            {
                if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
                    return &_tables[hashi];   // 命中，返回地址
                hashi = (hash0 + i) % _tables.size();
                ++i;
            }
            return nullptr;   // 一直探测到空位都没找到
        }
 
        // 删除：不是真把数据抹掉，而是打上 DELETE 标记
        bool Erase(const K& key)
        {
            HashData<K, V>* ret = Find(key);
            if (ret == nullptr)
                return false;
            ret->_state = DELETE;   // 标记删除（墓碑）
            --_n;
            return true;
        }
 
        // 扩容：造一个新表，把旧表里真实存在的数据全部重新插入
        void rehash()
        {
            HashTable<K, V, Hash> newHT;
            newHT._tables.resize(nextPrime(_tables.size() + 1));
            for (size_t i = 0; i < _tables.size(); ++i)
            {
                if (_tables[i]._state == EXIST)   // 只搬真实存在的
                    newHT.Insert(_tables[i]._kv);
            }
            _tables.swap(newHT._tables);   // 交换后旧表自动析构
        }
 
        // 打印当前表（用来观察布局；教学辅助，工程表不需要）
        void Print() const
        {
            for (size_t i = 0; i < _tables.size(); ++i)
            {
                cout << "[" << i << "] ";
                if (_tables[i]._state == EXIST)
                    cout << _tables[i]._kv.first;
                else if (_tables[i]._state == DELETE)
                    cout << "#(墓碑)";
                else
                    cout << "(空)";
                cout << endl;
            }
        }
 
    private:
        vector<HashData<K, V>> _tables;   // 哈希表本体
        size_t _n = 0;                    // 已存数据个数 => N
    };
}
 
// 测试闭散列
int main()
{
    open_address::HashTable<int, int> ht;
    int a[] = {19, 30, 5, 36, 13, 20, 21, 12, 24, 96};
    for (auto e : a)
        ht.Insert(make_pair(e, e));   // key 和 value 先都用 e 演示
 
    cout << "=== 插入后，表布局（看 13 和 30 冲突后往后挪到哪）===" << endl;
    ht.Print();
 
    cout << (ht.Find(20) ? "[闭散列]查找20: 找到" : "[闭散列]查找20: 未找到") << endl;
    ht.Erase(20);
    cout << "[闭散列]删除20后，表布局（20 变墓碑）" << endl;
    ht.Print();
    cout << (ht.Find(20) ? "[闭散列]删除20后再查: 找到" : "[闭散列]删除20后再查: 未找到") << endl;
    return 0;
}

我给闭散列补了一个 Print()（教学辅助，真实哈希表不会有打印功能），让你肉眼看见"数据冲突后到底怎么占位子、删除后格子长什么样"——学哈希最好学得"看得见"。看懂后可以把 Print() 当作教学的临时工具：如果你自己动手练，删掉它也没有影响。

到这里值得把线性探测的插入、查找、删除三个动作的探测规则对一遍，因为它们三个的"停"不一样，是闭散列最容易写错的地方：

• 插入：从 hash0 开始，一格一格往后走，遇到 EXIST 就继续走，直到遇到 EMPTY 或 DELETE（这两个都能放）就放进去，标记 EXIST。注意：插入要穿过的只是 EXIST，DELETE 空位直接能用。
• 查找：从 hash0 开始，一格一格往后走，遇到 EXIST 就比对 key 是否相等，相等命中、不等继续；遇到 DELETE 也要继续走（因为 DELETE 只是墓碑，后面的数据可能还在这条"探测链"上）；一旦遇到 EMPTY 就立刻停（后面的探测链断在这里了，key 肯定不存在）。
• 删除：先 Find 找到这个数据对应的格子，然后把它的状态改成 DELETE（不改值、不清格子）。

这套"三个动作三种停法"的规则，本质都是同一个道理：删除的数据不能真把它抹成一个 EMPTY，否则探测链断裂，会把排在这条链后面的数据"藏"起来再也找不着。这件事我在下一节专门展开。

线性探测的坑：堆积（群集）

上面这段代码能跑，但你其实已经踩进来了一个隐蔽的坑，值得单独拎出来讲透——堆积，也叫群集。

想象一下：假设 hash0、hash1、hash2 三个位置已经被数据连续占满了。现在有 4 个不同的 key，它们的初始位置恰好是 hash0、hash1、hash2、hash3。结果如何？因为 hash0~hash2 都被占了，前三个 key 全都要挨个往后挪，最后一起挤到 hash3 去争抢。位置连续被占，新来的数据就只能在已占区域的边界"堆"上一层新的占位，区域越来越大，冲突和探测次数也越来越多。

这就是教材里说的群集 / 堆积：初始位置相近或相同的数据，在线性探测下会连锁占位，形成一片"拥堵区"。它让探测的平均次数随负载因子上升而快速恶化——负载因子接近 1 时，可能探测很多次才能命中或确认不存在。所以线性探测代码虽然简单好写、好实现，但它的固有缺陷就是容易堆积、性能不稳。正因为表内格子互相影响是开放定址法的通病，实践中纯线性探测用得并不多。

这里有一层自找的闷亏要给你点破：堆积还有个"很有意思也很坑"的别名，叫"一次聚类"（primary clustering）。它之所以叫"一次"，是因为它源于不同 key 共享同一个初始 hash0 就被砸成一串——于是是"碰撞一次、连锁一串"。你记住这个概念，是为了跟后面的二次聚类区分：我们接下来要讲线性探测的改进——二次探测，正是为了把这种"大家盯着同一个起点、然后连锁往后堆"的毛病拆开。

这里还要顺带把前面那个隐藏的"状态字段"为什么必须有讲清楚，它是另一个典型的坑：查找的时候，遇到 EMPTY 就必须停下来，因为空格后面不可能再有这个 key 了。但如果没有 DELETE 这种"墓碑"标记，删除就会出错：比如把 20 之前的 30 真的从表里抹掉后，20 前面变成空的，查找 20 时撞上 EMPTY 会误判"20 不存在"。所以删除 30 不能真删，只能改成 DELETE 标记。查找遇到 DELETE 时不返回，继续往后探测，这样排在 30 之后的 20 就能被找到。这就是那个状态枚举存在的全部意义。

用一张"时间线"把"墓碑"的必要性讲透

我们再走一遍"为什么 30 不能真删"，用更具体的一幕：假设表里先后插入 19（下 8）、30（8 冲突→9）、20（9 冲突→10）。此时表：下标 8=19、9=30、10=20。现在如果你像删普通数组元素那样把 20 前面的 30 直接清空，那么表变成：8=19、9=(空)、10=20。下一次查找 20：hash0 = 20 % 11 = 9，一看 9 是空，按照"遇到 EMPTY 就停"的规则，立即判定"20 不存在"——但 20 明明还在 10！ 它被"藏"在了一个断链的探测序列里，永远找不到了。

而用墓碑就没事：删除 30 时把 9 标记成 DELETE（而不是清空），查找 20 走到 9 发现它是 DELETE，规则是"继续向后探测"，于是走到 10 命中 20。DELETE 这个"墓碑"就是堵住探测链"断裂空窗"的保险丝——它自己占着位置、不参与计数（删了 --_n），但让探测链不断。

这也顺带说明了为什么查找循环的判断条件是 _state != EMPTY（遇到 DELETE 继续），而插入循环是 _state == EXIST（遇到 DELETE 停）。两处对 DELETE 的处理恰好相反、又各自正确——一个为"不断链"，一个为"复用墓碑位"。写代码时别把这两处搞反，那是闭散列最阴间的 bug 源。

闭散列：二次探测

线性探测是"每次都挪一步"，速度太慢又容易堆积，能不能跳着找？能——这就是二次探测。它的思想是：冲突后不再线性地 +1、+2、+3，而是按距离的平方跳：第一次差 1²，第二次差 2²（也就是 +4）……并且左右来回探测。公式是：

hashi = (hash0 ± i²) % M，  i = 1, 2, 3, ...

用"跳跃式"的步长，就能避开线性探测那种扎堆往一个方向挤压的毛病，使不同初始位置的探测序列错开，一定程度缓解堆积。看个手工例子更能体会：课件里的 {19, 30, 52, 63, 11, 22}，在 M = 11 的表里：19→8、30→8、52→8、63→8 四个都撞在 8。线性探测会排成一串；而二次探测则会按 8+1=9、8+4=12%11=1、8+9=17%11=6 这样分散跳开，占用位置更分散。

为什么"平方跳"就能缓解堆积

二次探测的探测位置是 hash0 + 1², hash0 + 2², hash0 + 3², ...（对 M 取模），也就是偏移量取 1, 4, 9, 16, ...。它破堆积的关键在于：两个初始位置只是"差 1"的 key，它们的探测序列会被平方偏移迅速拉开。设想 hash0 和 hash0+1 两个起点：

• 线性探测：hash0 去探 hash0+1，hash0+1 本身是起点……两者序列高度重合，很快就互相"占坑"，形成一坨挤在一堆。
• 二次探测：hash0 走到 hash0+1、hash0+4、hash0+9、hash0+16…… hash0+1 那一组则到 hash0+2、hash0+5、hash0+10……两者的探测位置在平方偏移下错开得飞快，不再像线性那样挤成一团。

所以二次探测缓解的是"一次堆积"（大家挤在一个起点、连锁成串）。但注意，它的改进不是免费的——它会留下一个新的、相对较轻的"二次堆积"（secondary clustering），即"初始位置相同"的 key 依然共享同一条探测序列。不过总的来说它比线性好得多了。

二次探测的一个数学局限：它可能探不完全表

这里藏着一个严谨的数学点，值得讲清楚，免得你理解有偏差。对二次探测，i² mod M（i = 1,2,3,...）"能取多少个不同的值"取决于 M：

• 如果 M 是一个质数，那么 i² mod M 在前 (M-1)/2 个 i 上取到的值两两不同（因为 i 和 M-i 的平方相等，所以超过一半就开始重复）。也就是说二次探测最多能探到约一半的位置，剩下的格子它"够不着"。
• 这意味着，即使表还有空位（负载因子 > 0.5 时），二次探测也可能在一个"够不着的空隙"里绕圈，导致插入失败。

所以二次探测要稳妥运行，通常要求负载因子严格小于 0.5，并让 M 取质数——这样才能保证它总能探测到足够多的格子。这一点和线性探测（最多探测 M-1 次必成功，只要求负载因子 < 1）不同。这也是为什么二次探测虽然好，但负载门槛更苛刻、实际手写也更少。

不过在我们下面这份演示"探测序列"的代码里，你只需要看到"偏移量按平方走，且我们用 (hash0 + i*i) % M 求余数、必要时处理负数，就能把它落在合法区间"这个工程动作：

#include <iostream>
using namespace std;
 
int main()
{
    size_t M = 11;
    size_t hash0 = 8;   // 假设起始位置是 8，它冲突了
    for (size_t i = 1; i <= 5; ++i)
    {
        // 往右探测：hash0 + i*i
        size_t right = (hash0 + i * i) % M;        // 右移，直接在 [0,M) 里
        cout << "i=" << i << " 往右探到 " << right;
        cout << "   偏移=" << i * i << endl;
    }
    cout << "注意: 这些探测点是 8,9,1,6,2,... 跳跃分布的,不再挤成一串" << endl;
    return 0;
}

二次探测的另一个坑：往左探测出现负下标，必须先加 M 修正

上面代码只展示了往右（hash0 + i²）。但二次探测公式里有 ±，也就是还会往左探 hash0 - i²。这里埋着一个 C++ 的经典地雷——负数取模。我们前面在除留余数法那里讲过 C++ 的 % 对负数可能给负结果，这里再具体到二次探测：当 i 稍大一点，i² 可能比 hash0 还大，hash0 - i² 就是负数，你再 % M 还是负的，直接拿它当下标必然越界崩溃。

C++ 里负数 % 的结果可以是负的，不像数学上约定取非负余数。所以在执行 % 之前，要先把负值"加 M 拉回非负区间"：

#include <iostream>
using namespace std;
 
int main()
{
    size_t M = 11;
    size_t hash0 = 8;   // 假设起始位置是 8，它冲突了
    for (size_t i = 1; i <= 3; ++i)
    {
        // 往左探测：hash0 - i*i
        long long left = (long long)hash0 - (long long)(i * i);  // 可能变成负数
        if (left < 0)
            left += M;                    // 关键：负数先加 M 修正
        size_t hashi = left % M;          // 再取模，得到合法下标
        cout << "i=" << i << " 往左探到 " << hashi << endl;
    }
    return 0;
}

注意这里为什么用 long long 而不用 size_t 做减法：size_t 是无符号类型，你写 size_t a = 0; size_t b = a - 9;，那个 a - 9 不会变成 -9，而是无符号回绕成一个巨大的正数！所以要先提升成有符号的 long long，让 hash0 - i*i 能真正算出负数，才能用 if (left < 0) left += M 去修正。这是二次探测最典型的"无符号地雷"，回答了一切"为什么我的下标有时会变成天文数字"的疑问。

C++ 标准库的 unordered_map 并非用二次探测，而是用更稳的链地址法。二次探测这里你只要理解它"通过跳跃减轻堆积"的思路即可，实际开发很少再手写它。我们把重点放在真正的"正主"——链地址法上。

双重散列（了解，三种开放定址探测序列里的第三种）

既然线性和二次都讲完了，干脆把开放定址法课件里的第三种——双重散列/双重探测也讲了，这样三种方案你一把抓齐。它的思路是用两个不同的哈希函数：

h1(key)  = key % M                 // 第一个函数：算出初始位置 hash0
hc(key,i) = (h1(key) + i × h2(key)) % M   // 冲突后，用第二个函数算"每一跳的偏移量"

对比一下就清楚了：

• 线性探测的每一跳偏移量固定为 1；
• 二次探测的每一跳偏移量是固定的函数 i²（对所有 key 都一样）；
• 双重散列每一跳的偏移量 h2(key) 是跟 key 相关的——不同 key 就算起点相同，它们的"步长"也不同。这从根本上消除了"初始位置相同的 key 共享同一条探测链"的堆积，是三种开放定址法里分布最均匀的，也是《算法导论》推荐的开散列首选理论方案。

但双重散列有个硬性要求：h2(key) 必须和 M 互质（最大公约数为 1）。为什么？因为如果 h2(key) 和 M 的公因数大于 1（比如最大公约数 p > 1），那么从起点 hash0 出发，每次加 h2(key)，其实只能访问到 M/p 个格子（数学上关于"模 M 的等差序列"的结论：步长与 M 的最大公约数决定能到达的位置数）。举个课件里的例子：取 M = 12、初始位置 1、偏移量为 3（gcd(12,3)=3，互质失败），你只能访问 {1, 4, 7, 10} 这四个位置，表有 12 格却只探到 4 格——空位明明还有，你却永远够不着，插入就失败了。

所以工程上用双重散列，通常让 M 取质数，并让 h2(key) 用下面两种简单取值保证互质：

• 若 M 是 2 的整数幂：h2(key) 从 [0, M-1] 里任选一个奇数；
• 若 M 是质数：取 h2(key) = key % (M-1) + 1（因为结果落在 [1, M-1]，且和质数 M 必然互质）。

下面这段是双重散列探测序列的演示（M 取质数 11、h2 = key % 10 + 1），你跑一下会看到"同样起点、不同 key 步长不同"，这正是它最优雅的地方：

#include <iostream>
using namespace std;
 
size_t h1(size_t key, size_t M) { return key % M; }
size_t h2(size_t key, size_t M) { return key % (M - 1) + 1; }  // 保证与质数 M 互质
 
int main()
{
    size_t M = 11;
    size_t keyA = 8, keyB = 19;   // 让两者 hash0 尽量不同感受步长差异（演示以 key 为视角）
 
    cout << "key=19: h2 =" << h2(19, M) << endl;   // 步长与 key 相关
    cout << "key=41: h2 =" << h2(41, M) << endl;
    cout << "key=63: h2 =" << h2(63, M) << endl;
 
    // 展示同一 hash0 下，不同 key 步长不同 => 探测链错开，不堆积
    size_t hash0 = 8;
    for (size_t i = 1; i <= 3; ++i)
        cout << "hash0=8, key=19, 第" << i << "跳: "
             << (hash0 + i * h2(19, M)) % M << endl;
    for (size_t i = 1; i <= 3; ++i)
        cout << "hash0=8, key=30, 第" << i << "跳: "
             << (hash0 + i * h2(30, M)) % M << endl;
    return 0;
}

一句话总结开放定址法的三种探测：线性看一步、二次看平方、双重看 key——越往后越"个性化"，也就越不容易堆积。 我们把三种都摆在桌面上，但回到现实，手写开放定址通常只选线性（简单），工程容器大多直接选链地址法（稳定）。那块"正主"就在下一节。

哈希桶：链地址法（开散列）

终于讲到实践中的主角了。链地址法，也叫拉链法或是更形象的名字——哈希桶。它的思路和开放定址法完全不同：数据不再直接住在哈希表里，表里的每个格子只放一个指针（链表头）。没有数据映射到这个位置时，指针为空；一旦有数据映射过来，就把这些冲突的数据串成一个链表，挂在对应的格子下面。

你可以很形象地理解为：数组的每个格子上"倒挂着一串钥匙"，每串钥匙就是一群初始位置相同的 key。因为数据被"外挂"到链表里而不是挤占别人的格子，所以链地址法天然不怕冲突，负载因子可以大于 1——哪怕表里 90% 的格子都挂着好几个数据，也能工作。

为什么桶方案比开放定址更"干净"：三点本质

用一个对比表把两种方案放在一起看，你会立刻明白为什么工程再怎么也不选开放定址：

最要命的是**"互相影响"**：开放定址里一个数据冲突，会挤占别处的位置，让那"别处"的数据又去挤更远处……牵一发动全身；而哈希桶每个冲突数据都挂在自己的链上，其他桶完全不受牵连。这是桶方案在结构上"干净"的根本原因。这也是为什么 std::unordered_map / std::unordered_set 的内部结构就是哈希桶，而不是开放定址。

代码上，哈希桶的结点自带一个 _next 指针，形成单向链表：

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
// ===== 通用哈希函数：默认按整型处理；string 特化用 BKDR（本块自带，可独立编译）=====
template<class K>
struct HashFunc
{
    size_t operator()(const K& key) { return (size_t)key; }
};
template<>
struct HashFunc<string>
{
    size_t operator()(const string& key)
    {
        size_t hash = 0;
        for (auto ch : key) { hash *= 131; hash += ch; }  // BKDR
        return hash;
    }
};
 
namespace hash_bucket   // 开散列：链地址法（哈希桶）
{
    // 桶里的链表结点
    template<class K, class V>
    struct HashNode
    {
        pair<K, V> _kv;          // 键值对
        HashNode<K, V>* _next;   // 指向下一个冲突结点
        HashNode(const pair<K, V>& kv)   // 构造时初始化
            : _kv(kv), _next(nullptr)
        {}
    };
 
    template<class K, class V, class Hash = HashFunc<K>>
    class HashTable
    {
        typedef HashNode<K, V> Node;
 
        static size_t nextPrime(size_t n)
        {
            static const size_t primeList[] = {
                53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
                49157, 98317, 196613, 393241, 786433, 1572869, 3145739,
                6291469, 12582917, 25165843, 50331653, 100663319,
                201326611, 402653189, 805306457, 1610612741, 3221225473UL,
                4294967291UL
            };
            const size_t* first = primeList;
            const size_t* last = primeList + sizeof(primeList) / sizeof(primeList[0]);
            const size_t* pos = lower_bound(first, last, n);
            return pos == last ? *(last - 1) : *pos;
        }
 
    public:
        HashTable()
        {
            _tables.resize(nextPrime(0), nullptr);  // 每个桶初始都是空指针
        }
 
        ~HashTable()
        {
            // 依次释放每个桶里的链表结点，避免内存泄漏
            for (size_t i = 0; i < _tables.size(); ++i)
            {
                Node* cur = _tables[i];
                while (cur)
                {
                    Node* next = cur->_next;   // 先记录下一个
                    delete cur;                // 释放当前
                    cur = next;
                }
                _tables[i] = nullptr;
            }
        }
 
        // 插入（头插）
        bool Insert(const pair<K, V>& kv)
        {
            Hash hash;
            size_t hashi = hash(kv.first) % _tables.size();  // 算桶号
 
            // 负载因子达到1就扩容（STL 的 unordered_* 基本也控制在这个阈值）
            if (_n == _tables.size())
            {
                rehash();
                hashi = hash(kv.first) % _tables.size();  // 扩容后要重新算位置
            }
 
            // 头插到对应桶
            Node* newnode = new Node(kv);   // 新建结点
            newnode->_next = _tables[hashi]; // 新结点的后继指向原桶头
            _tables[hashi] = newnode;        // 新结点成为新的桶头
            ++_n;
            return true;
        }
 
        // 扩容：把旧表的结点"移动"到新表，而不是新建再抛弃
        void rehash()
        {
            Hash hash;
            vector<Node*> newtables(nextPrime(_tables.size() + 1), nullptr);
            for (size_t i = 0; i < _tables.size(); ++i)
            {
                Node* cur = _tables[i];
                while (cur)
                {
                    Node* next = cur->_next;                       // 先存后继，防止断链
                    size_t hashi = hash(cur->_kv.first) % newtables.size(); // 新桶号
                    cur->_next = newtables[hashi]; // 头插到新表对应桶
                    newtables[hashi] = cur;        // 更新新桶头
                    cur = next;                    // 处理链上的下一个
                }
                _tables[i] = nullptr;              // 旧桶置空
            }
            _tables.swap(newtables);               // 交换，旧表析构
        }
 
        // 查找
        Node* Find(const K& key)
        {
            Hash hash;
            size_t hashi = hash(key) % _tables.size();  // 先定位桶
            Node* cur = _tables[hashi];
            while (cur)             // 沿着链表往下找
            {
                if (cur->_kv.first == key)
                    return cur;     // 命中
                cur = cur->_next;
            }
            return nullptr;         // 整条链都没有
        }
 
        // 删除
        bool Erase(const K& key)
        {
            Hash hash;
            size_t hashi = hash(key) % _tables.size();
            Node* prev = nullptr;          // 记录前一个结点
            Node* cur = _tables[hashi];
            while (cur)
            {
                if (cur->_kv.first == key)
                {
                    if (prev == nullptr)          // 删的是桶头
                        _tables[hashi] = cur->_next;
                    else                          // 删的是中间结点：让前一个绕过它
                        prev->_next = cur->_next;
                    delete cur;   // 释放结点，避免泄漏
                    --_n;
                    return true;
                }
                prev = cur;         // 向后移动前驱与当前
                cur = cur->_next;
            }
            return false;           // 链上不存在
        }
 
        // 打印：观察每个桶挂了哪些结点（教学辅助）
        void Print() const
        {
            for (size_t i = 0; i < _tables.size(); ++i)
            {
                cout << "桶" << i << ":";
                for (Node* cur = _tables[i]; cur; cur = cur->_next)
                    cout << " " << cur->_kv.first;
                cout << endl;
            }
        }
 
    private:
        vector<Node*> _tables;   // 指针数组：每个元素是一个桶的头指针
        size_t _n = 0;           // 数据个数 => N
    };
}
 
// 测试哈希桶
int main()
{
    hash_bucket::HashTable<int, int> ht;
    int a[] = {19, 30, 5, 36, 13, 20, 21, 12, 24, 96};
    for (auto e : a)
        ht.Insert(make_pair(e, e));
 
    cout << "=== 插入后各桶分布（冲突的全挂在同一串上）===" << endl;
    ht.Print();
 
    cout << (ht.Find(30) ? "[哈希桶]查找30: 找到" : "[哈希桶]查找30: 未找到") << endl;
    ht.Erase(30);
    cout << "[哈希桶]删除30后，桶内变化" << endl;
    ht.Print();
    cout << (ht.Find(30) ? "[哈希桶]删除30后查: 找到" : "[哈希桶]删除30后查: 未找到") << endl;
    return 0;
}

对比一下就会发现，哈希桶的插入用的是头插——新结点直接挂到桶的最前面，因为"往链表头插"时间复杂度是 O(1)，比尾插省事（尾插你还要先从头走到尾找到最后一个结点，那就是 O(链长)）。而且插入前我特意没去 Find 判重（你也可以加上，就看你的语义需不需要去重）。删除则是典型的单链表删除操作：必须用 prev 记住前驱，才能把目标结点从链上摘下来，否则会断链——这是链表操作里最经典、也最容易出错的一步，务必盯紧。

为什么删除必须用 prev 记住前驱

_next 是单向的，它只告诉你"下一个是谁"，而不知道"上一个是谁"。所以当你找到要删的 cur 时，想要"让上一个结点跨过 cur 指向 cur 的下一个"，就必须靠自己一路用 prev 记下"谁是指向 cur 的那个结点"。这就是单链表删除的标准套路：

• 删桶头（prev == nullptr）：桶头指针直接指向 cur->_next；
• 删中间/尾部（prev != nullptr）：prev->_next = cur->_next，把前驱的后继改到 cur 的后继。

代码里有个很容易写反的顺序：你必须先 next = cur->_next（或先用 prev 把链断开）再 delete cur。如果先 delete cur 再碰 cur->_next，那就是在已经释放（解放后）的内存上访问，属于悬垂指针访问 + 释放后使用（use-after-free），是 C++ 里后果最严重的错误之一（可能崩、可能内存错乱、行为不定）。我演示代码里删除和 rehash 都严格遵守了"先记 next / 先断链，再释放/搬走"的顺序，请你在阅读和动手时也养成这个习惯。

另外一个小坑：这里默认不允许重复 key（你没判重）。所以同一个 key 连续 Insert 两次，实际上会插进两条一模一样的结点，Find 只找到第一个，结果会回到 unordered_map 的语义冲突（unordered_multimap 才允许多个同 key）。如果你的接口要实现"去重的 set 语义"，就得在 Insert 前 Find 判重——这跟闭散列那套 if (Find(...)) return false; 是同一个动作，写上即可。

哈希桶的插入与扩容：一个效率优化

哈希桶的扩容，有一个和闭散列不一样、值得单独深挖的优化点。回想闭散列扩容是怎么做的？它是新建一张表，把旧表里每个 EXIST 的数据"复制"一份重新 Insert 进去。对哈希桶来说，如果照搬这个做法，就等于为每个旧结点重新 new 一个新结点，插入新表后再把旧的删掉——白白多分配一遍内存，上一批结点创建出来又立刻被抛弃，纯浪费。

所以哈希桶的扩容应该换个思路：把旧表的结点"移动"到新表，而不是复制。具体做法是，新表只分配一个 vector<Node*>（不 new 任何 Node），然后遍历旧表的每个桶，把结点从旧链上摘下来，直接头插到新表对应的桶里。这样全程没有产生新结点，只是把指针"搬家"了，既省内存又更快。你仔细看上面 rehash() 的实现：cur->_next = newtables[hashi]; newtables[hashi] = cur; 就是在做"摘下来→换个桶头插"的移动操作，而不是 new。

为什么"复制搬家"会白费内存：内部分配的账

我们算一笔"内存账"来理解这个优化为什么重要。桶方案里，每条数据都是一个 new 出来的 HashNode（堆上分配一块小内存）。如果扩容时用"复制"而非"移动"：

1. 为每个旧结点又 new 一块新结点（新分配）；
2. 把值拷进去；
3. 把旧结点 delete 掉（释放）。

这就等于每个数据在扩容瞬间被"复制了又抛弃",白白经历了两次 heap 操作（一次分配 + 一次释放）。而 heap 的 new/delete 在性能上是有成本的（要经过内存管理器的分配/回收，可能触发系统调用）。当数据量大时，"复制"扩容的额外开销相当可观。而"移动"方案一个 heap 分配都没做——它只改指针，把旧结点原封不动地"搬"到新桶里。这就是为什么工程化哈希桶扩容只用移动、绝不复制。想一下：闭散列没法用移动，因为数据存在 vector 数组里（不是 new 出来的独立结点），它只能复制；而桶的数据是独立结点，天生可以搬走——这是桶方案在"扩容效率"上的又一个优势。

极端场景：某个桶特别长，查找退化成 O(N)

这里还有个配套的极端场景值得了解：如果极端情况下某个桶特别长，查找效率怎么办？比如被恶意针对，专门构造一批哈希值全部相同的 key，让它们全挤进一个桶，那这个桶退化成一条超长的单链表，查找退化成 O(N)，哈希表的名存实亡。现实中的对策有两个方向：一是用前面提到的全域散列给哈希函数加随机性，让攻击者无法构造必坏的数据；二是像 Java 8 的 HashMap 那样，当某个桶长度超过阈值（8）时，把单链表转换成红黑树，把最坏查找降到 O(log N)。这些优化我们在课堂上实现时就先不做那么复杂了，你了解这个思路即可——真正的工程化哈希表，正是靠这些细节在极端情况下保护自己。

补充一句 C++ 侧的工程细节：std::unordered_map 在桶过长时的对策跟 Java 不同——C++ 标准库通常就是一个桶一条单向链表 + 定期扩容，如果某个桶真的退化成超长链，性能就会掉；因此对 unordered_* 这类容器，如果预测到 key 会被恶劣构造，最好自定义一个足够均匀的 Hash（比如全域散列思想的"随机种子哈希"）。这是面试和实战里"哈希被针对"话题的高级补充，你现在有概念即可。

最后做一个小结，把两种方案放在一起对比，你会记得更牢：哈希的本质是用函数从 key 一步映射到位置；直接定址让 key 当下标、适合值域集中；除留余数法用取模压缩到 [0,M)、M 尽量取质数；哈希冲突不可避免，于是有了两大解法——**开放定址法（闭散列）**把所有数据塞在表里，靠线性/二次探测找空位，负载因子必须小于 1，但有堆积问题和格子互相影响的先天弱点；链地址法（哈希桶）把冲突数据挂在各自格子的链表下，负载因子可以到 1 再扩容，更稳定，也是 unordered_* 的底层。而负载因子就是何时扩容的扳机，字符串的 key 则用 BKDR（累乘质数 + 加字符）转换成整数。你还亲手踩了两个坑：闭散列删除要打 DELETE 墓碑防止查找中断、二次探测负下标要先加 M 修正，以及哈希桶扩容应"移动结点"而非"重建结点"。

这一趟下来，你不仅搞懂了哈希表的思想和两种实现，更重要的是把"为什么标准库选链地址法""为什么删除不能真删""为什么扩容有讲究"这些只读概念学不透的细节，都用代码亲身体会了一遍。下次你再看到 std::unordered_map、std::unordered_set 这些 unordered_* 容器，应该能一眼看穿它们肚子里装的是什么了——就这些我们今天亲手搭的东西。感兴趣的话，可以把闭散列的哈希函数从线性探测改成二次探测跑一跑，感受一下堆积问题的变化；也可以自己实现一个 unordered_set 风格的去重接口练手。动手，永远是理解数据结构最好的方式。

全文思维导图（学完整理成一张网）

内容到这里其实已经把知识点都串完了，最后我再送你一张"知识地图"，让你对这篇多又杂的哈希专题有个总纲式的收束，防止学完就散：

哈希（散列） = key → 下标（O(1) 定位）
│
├─ 哈希函数：怎么把 key 变成下标
│    ├─ 直接定址法：key 值当下标（要求值域集中）→ 计数排序/力扣387
│    └─ 除留余数法：key % M，M 挑质数（避免 2/10 幂）→ 工程主流
│         └─ 了解：乘法散列(黄金分割) / 全域散列(随机防攻击) / 其他方法
│
├─ 字符串 key → 先转整数：BKDR（累乘质数 + 加字符）→ 保留位置信息
│
├─ 冲突不可避免 → 需要解决冲突的方案
│    ├─ 开放定址法（闭散列）：全住在表里，负载因子 < 1
│    │     ├─ 线性探测：+1 逐格找 → 堆积（群集）→ 删要删成 DELETE 墓碑
│    │     ├─ 二次探测：±i² 跳着找 → 缓解堆积，但要处理负下标
│    │     └─ 双重散列：偏移量跟 key 相关，最均匀（了解）
│    └─ 链地址法（开散列 / 哈希桶）：每格挂链表，负载因子可到 1
│          ├─ 插入头插 O(1)；删除用 prev 断链防 use-after-free
│          └─ 扩容"移动结点"而非"复制结点"（更省内存）
│
└─ 负载因子 N/M = "要不要扩容"的扳机
     ├─ 闭散列：约 0.7 扩容（表满会爆）
     └─ 桶：约 1.0 扩容（STL 阈值）

这张图的每个分支，你在前文都能找到对应的可运行代码和踩坑点。下次复习，先看它，再逐点对回正文，哈希就再也难不倒你了。

参考答案与详解

练习 ①：把闭散列的"线性探测"改成"二次探测"

只需改插入/查找循环里计算探测位置的那一行。线性是 hashi = (hash0 + i) % M（i = 1,2,3,...）；改成二次就往右按平方跳：

// 往右：每次偏移的平方
hashi = (hash0 + i * i) % M;   // i 从 1 开始，偏移依次 1, 4, 9, 16, ...

若想用课件里"左右来回 ±i²"的完整二阶形式，关键是要先把可能为负的 hash0 - i*i 拉回非负再取模。因为 size_t 是无符号类型，直接 hash0 - i*i 会回绕成天文数字，必须先提升成有符号（long long）再判断并加 M：

// 往左（演示）：hash0 - i*i 可能为负
long long left = (long long)hash0 - (long long)(i * i);
left %= (long long)M;
if (left < 0) left += (long long)M;   // 负数先加 M 归位
size_t hashi = (size_t)left;

改完后跑正文里的 {19, 30, 5, 36, 13, 20, 21, 12, 24, 96}，你会发现原本被迫在 9、10、0 上排队的冲突数据被"跳"着分散到不同格子，这就是二次探测缓解一次堆积的效果。要提醒：二次探测对质数 M 最多只能探到约 (M-1)/2 个不同位置，所以若要沿用这份代码，负载因子阈值应从 0.7 降到 0.5 以下才稳妥，否则可能"明明还有空位却插不进去"。

练习 ②：给哈希桶实现"去重"的 set 语义，或薄封装一个 set

去重的关键是插入前先查重。哈希桶原版 Insert 直接头插、不判重，加一行即可：

bool Insert(const pair<K, V>& kv)
{
    if (Find(kv.first))        // 已存在，不重复插入
        return false;
    // …… 之后的找桶、判断负载、头插逻辑不变
}

（闭散列版已经自带 if (Find(kv.first)) return false;，无需改动。）如果想做成"只存 key、不存 value"的 set，只需让底层 HashTable<K, K> 以 key 同时充当 value，再包一层薄壳暴露 insert / erase / find / count 即可；内存释放交给桶类的析构函数（遍历每个桶、依 _next 逐个 delete，正文代码已实现）。这也正是下一篇"用一个哈希表封装出 myunordered_map / myunordered_set"要做的事——你现在已经具备了把键值哈希表改造成单键集合的全部零件。