洛谷的题解写了不少但像 P11615 这种【模板】题反而是我觉得最值得认真写一篇的。因为模板题的核心价值不在“过题”本身而在于它把一类算法的骨架给你拆出来了。你把这套骨架吃透后面遇到的很多问题——字符串判重、离散化映射、缓存设计、集合运算——本质上都是在拿这套东西变花样。这篇题解我按自己的理解来写不光是贴一份能 AC 的代码更想把哈希表这套结构的“为什么”讲清楚为什么用哈希函数、为什么处理冲突、为什么模数选质数、为什么有些写法会超时。适合刚学完数组和链表、准备进阶数据结构或者刷题遇到哈希表总是靠map硬撑的同学。1. 模板题到底在考什么哈希表不是一个“新知识”先直接说结论哈希表就是“数组 哈希函数 冲突处理”三件事的组合。它本身没有任何一个组件是你没学过的。数组给你 O(1) 的随机访问能力这是哈希表性能的底子。但数组的下标必须是整数而且范围不能太大。哈希函数负责把“任意类型的键”映射成一个非负整数这样就能用数组下标来存储了。至于冲突处理是因为两个不同的键可能映射到同一个下标所以你需要一套规则来安置它们。之前有朋友问我说 P11615 这种题是不是就是背一个模板往上一交就行。我的看法是你背下来的模板必须是你自己看得懂、讲得出理由的模板。比如哈希函数为什么取模、取模的模数为什么用质数、链表头插和尾插有没有区别、删除操作到底该怎么标记——这些细节才是模板题真正想让你掌握的。如果只是把代码抄一遍下次换一道题比如键变成字符串、变成 pair你照样不会写。还有一个很重要的点哈希表在竞赛里通常用“手写”来实现而不是直接调 STL 的unordered_map。倒不是说 STL 不行而是手写哈希表能让你精确控制哈希函数、容量和冲突策略也更容易理解性能瓶颈在哪里。等你看懂手写实现之后回头用unordered_map也会更清楚它内部在做什么。2. 核心设计决策哈希函数、模数与装载因子哈希表从原理上讲是在“时间”和“空间”之间做权衡。你分配一个很大的数组冲突自然就少但你只有有限的内存所以数组不能无限大。这时候就需要一套设计来保证“在合适的内存占用下操作仍然接近 O(1)”。2.1 哈希函数如何把键变成数组下标最常见的做法是取模int hash(int key) { return (key % MOD MOD) % MOD; }这里有几个细节值得展开。第一key % MOD对于int范围内的键是够用的。C 里负数的取模结果是负数所以加一次MOD再取模保证结果落在[0, MOD - 1]。这个写法在竞赛里非常常见。如果你能保证键非负那么直接key % MOD就行。第二MOD的选择。通常取一个不大不小的质数比如1000003、10000019。为什么偏向质数这和取模的均匀性有关系。如果你的键本身有一些规律比如都是偶数或者说都是某个数的倍数而模数也有因子那么取模结果就会集中在某些位置上导致冲突急剧增加。质数的因子最少在各种键的分布下表现更稳定。这里说的不是玄学而是数论里一个经典的均匀性结论当模数与键的周期互质时映射结果在循环节内能覆盖更多不同的余数。第三容量问题。数组的容量也叫桶数应该比实际元素个数大。一般经验是让装载因子元素个数 / 桶数保持在 0.7 以下。装载因子太高冲突会明显变多最坏情况下哈希表会退化成链表遍历。竞赛题一般会给数据范围你开一个两倍于数据规模的桶数组基本就不用担心装载因子。2.2 冲突处理没有完美的哈希函数从数学上可以证明如果你把无限多个不同的键映射到有限个桶里那冲突必然发生。哈希表工程实践的核心就是怎么处理这些冲突。冲突处理有两大家族开放寻址法和链地址法。P11615 这类模板题绝大多数情况链地址法更好写也更稳。链地址法的思路每个桶不是存一个元素而是存一条链表的头节点。发生冲突的元素依次挂到同一个桶的链表上。查找时先定位桶再在链表里顺序比较。插入和删除本质上都是在链表上做操作。这个方案的优势是直观、好写、不容易出隐蔽的 bug。劣势是每个节点要额外存一个指针内存开销略大。不过对竞赛来说这个开销完全可接受。开放寻址法线性探测、二次探测、双重哈希是另一个思路冲突了就往后面的空位放。它省掉了指针但删除操作很麻烦需要“墓碑”标记。我后面会单独写一节对比。3. 链地址法实现的标准模板代码我直接给一份完整的链地址法实现基于洛谷模板题的常规操作集插入、查找、删除。这份代码以整数键为例但稍作修改就能扩展到long long或字符串。#include cstring #include iostream using namespace std; const int MOD 1000003; // 质数模数 const int N 1000005; // 桶数组大小 struct Node { int key; int val; // 可以存额外信息如果只需要判重可以不存 Node* next; Node(int k 0, int v 0, Node* nx nullptr) : key(k), val(v), next(nx) {} }; Node* head[MOD]; // 每个桶维护一条链表 int hash_key(int key) { return ((key % MOD) MOD) % MOD; } void insert(int key, int val) { int h hash_key(key); // 如果键已经存在先更新值很多题目要求去重 for (Node* p head[h]; p; p p-next) { if (p-key key) { p-val val; return; } } // 头插法 head[h] new Node(key, val, head[h]); } bool find(int key) { int h hash_key(key); for (Node* p head[h]; p; p p-next) { if (p-key key) return true; } return false; } void erase(int key) { int h hash_key(key); Node** pp head[h]; // 二级指针方便删除头节点 while (*pp) { if ((*pp)-key key) { Node* tmp *pp; *pp (*pp)-next; delete tmp; return; } pp ((*pp)-next); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; while (n--) { int op, x; cin op x; if (op 1) insert(x, 1); else if (op 2) { cout (find(x) ? Yes : No) \n; } else if (op 3) erase(x); } return 0; }3.1 为什么用头插而不是尾插头插法写起来最短而且 O(1)。更重要的是对于哈希表这种场景链表的顺序本来就不重要所以没有必要记录尾指针。很多人第一次写哈希表会惯性想“链表就要尾插”其实完全没有必要。3.2 删除操作的双重指针写法删除链表节点时如果要删的是头节点直接修改head[h]就行但如果是中间节点需要把前一个节点的next指过去。用二级指针Node** pp可以统一这两类情况pp一开始指向head[h]之后指向当前节点next字段的地址。这样无论是删头节点还是删中间节点都能通过*pp (*pp)-next一步完成。这是链表删除里非常标准的技巧值得记住。3.3 动态建节点和数组池化上面代码用了new Node(...)简单直观。但在某些题目里如果你插入操作特别多比如几十万次频繁new和delete会带来不小的开销也容易产生内存碎片。更稳妥的做法是提前开一个大数组当内存池Node pool[N]; int pool_idx 0; Node* new_node(int key, int val, Node* next) { pool[pool_idx].key key; pool[pool_idx].val val; pool[pool_idx].next next; return pool[pool_idx]; }这样所有节点从连续内存里分配写入速度更快也不用担心忘记释放。我个人的习惯是能开静态数组就开静态数组动态内存只在小数据量时使用。4. 开放寻址法另一种必须掌握的方案链地址法实现简单但不是唯一选择。开放寻址法在某些场景下更优比如你确定元素数量上限、希望避免指针带来的内存开销时。洛谷这类模板题虽然一般用链地址法就能过但很多高级数据结构比如哈希表实现的并查集、哈希表实现的记忆化搜索会用到开放寻址法的思想。4.1 线性探测的核心流程开放寻址法里整个哈希表就是一个数组。插入元素时如果算出来的桶位已经被人占了就往后找下一个空位。查找元素时从哈希位置出发一直往后找碰到空位说明元素不存在因为插入时不会跳过空位放到更后面。const int EMPTY 0; // 标记空位 const int DELETED -1; // 标记已删除 int table[MOD]; int key_table[MOD]; void insert(int key) { int h hash_key(key); while (key_table[h] ! EMPTY key_table[h] ! DELETED) { if (key_table[h] key) return; // 已存在 h (h 1) % MOD; } key_table[h] key; } bool find(int key) { int h hash_key(key); while (key_table[h] ! EMPTY) { if (key_table[h] key) return true; h (h 1) % MOD; } return false; }注意线性探测的查找必须一直找到空位才停不能只查一个位置。这是因为插入是往后“塌陷”的你最初哈希到的位置可能被别人占了真正的元素可能被挤到了后面。4.2 删除为什么要用墓碑标记开放寻址法最大的坑是删除。你想一下如果直接把某个位置的元素清成EMPTY那么查找一个原本在它后面、但因为探测路径需要经过这个位置的元素时就会提前遇到空位而返回“不存在”。这是逻辑错误。解决办法是用一个单独的DELETED标记。删除时不是清空而是打上“墓碑”。查找时遇到DELETED要当作有人占用继续往后走。插入时遇到DELETED则可以填入新元素。墓碑的代价是表里会积累大量“死亡”位置探测链越来越长性能下降。所以一般要在装载因子过高或者墓碑过多时做 rehash重新分配更大的表重建哈希表。这也是开放寻址法实现起来比链地址法烦琐的主要原因。4.3 两种方案怎么选一张表说清楚下面的对比我在做题时反复用来提醒自己维度链地址法开放寻址法线性探测实现难度较低逻辑直观删除逻辑较难内存利用每个节点额外存指针无指针内存利用率高缓存友好性链表节点分散缓存不友好数组连续缓存友好删除操作简单直接需要墓碑可能触发 rehash最坏情况退化成链表遍历退化成整表扫描适用场景大多数竞赛题目内存受限、数据规模明确如果是刷洛谷 P11615 这类模板题我个人推荐链地址法理由很简单在 10^6 级别的操作量下它足够快且不容易在删除操作上翻车。开放寻址法读完这篇能理解原理就好等遇到需要它的题再切换也不迟。5. 字符串键与哈希表的结合从模板题到实际应用P11615 标题里带【模板】但哈希表的应用场景远不止整数键。竞赛里最常见的变形是字符串键。比如洛谷上大量字符串判重、词组统计的题目核心就是“给字符串算一个整数哈希值然后用哈希表存起来”。5.1 字符串哈希的经典写法常见的字符串哈希是把它看成一个 base 进制的大整数然后对某个大质数取模。比如using ull unsigned long long; ull hash_string(const string s) { const ull base 131; ull h 0; for (char c : s) { h h * base c; } return h; }用unsigned long long的好处是溢出自动取模 2^64省去手动取模。base 取 131 或 13331 是网上流传很久的经验值冲突率足够低。如果你想要更稳妥可以取双哈希两个不同的 base/模数各算一次两个值都相同才认定相等冲突概率基本可以忽略。5.2 字符串哈希和哈希表的配合这里的“哈希”实际上有两层含义。第一层是把字符串映射成一个整数字符串哈希第二层是把这个整数映射到数组下标哈希表的哈希函数。很多初学者容易混淆calc_hash(s)的结果是ull范围的大整数不能直接当下标还需要再模一个MOD才能定位桶。所以正确流程是对字符串算一个 64 位哈希值h。再用h % MOD找到桶号。在桶的链表里逐个比较完整字符串确定是否存在。代码结构其实和第 3 节完全一样只是Node里存的key从int变成string或者存储哈希值和原串。注意哪怕两个字符串的哈希值不同它们一定不是同一个串但哈希值相同的两个串不一定相同。所以链表里必须存原串做精确匹配不能只存哈希值。5.3 一个实际的例子单词频次统计#include iostream #include string #include vector using namespace std; const int MOD 1000003; struct Node { string key; int cnt; Node* next; Node(const string k, Node* nx nullptr) : key(k), cnt(1), next(nx) {} }; Node* head[MOD]; ull hash_string(const string s) { const ull base 131; ull h 0; for (char c : s) h h * base c; return h; } void add(const string s) { int h hash_string(s) % MOD; for (Node* p head[h]; p; p p-next) { if (p-key s) { p-cnt; return; } } head[h] new Node(s, head[h]); }这就是很多字符串统计题的骨架。你只需要在这些基础操作上叠加题目要求的输出逻辑比如维护最大值、按字典序输出等等。这也解释了为什么【模板】题值得花时间吃透它给你的是真正可以复用的东西。6. 实测中容易踩的坑与性能优化哈希表实现看起来短小精悍但实际提交时翻车的点可不少。我把自己以及身边朋友踩过的坑整理在这里部分问题如果不注意在 P11615 这种模板题上就会直接 TLE 或 WA。6.1 模数开太小导致冲突爆炸有人图省事把MOD开成10007甚至1009。如果数据范围是 10^5那么平均每个桶挂 10 个甚至 100 个元素查找操作退化成线性扫链表直接超时。模板题的数据范围一般会在题面说明我建议桶数至少比最大操作数大 2 到 5 倍。如果题目没有明确数据范围你可以用一个较大的质数比如10000019然后把桶数组开成同样大小。内存上int数组开 10^7 是 40MB在洛谷一般能过Node*数组也差不多。稳妥起见我常在 10^6 量级的 MOD 上做文章。6.2 哈希函数质量差导致不均匀分布如果键本身有规律比如都是等差数列而你的模数恰好是这个数列公差的因子那它们会全部落在少数几个桶里。这种情况哪怕装载因子很低也没有用。我常用的改进是加入“扰动”。比如先乘以一个大质数再取模int hash_key(int key) { key ^ key 16; // 让高位的bit也参与运算 return ((long long)key * 1000003LL % MOD MOD) % MOD; }这能打散低位相同的键。对于整数键上面的异或右移来自 Java HashMap 的经典做法效果很好。对字符串键用 5.1 节的字符串哈希天然就能打散不需要额外处理。6.3 负数键的处理C 的%对负数是向零取整的-7 % 3 -1。如果不处理哈希函数返回负数数组越界直接 RE。之前有个学弟写删除操作所有键都是正数没暴露问题换了一组带负数的数据当场崩。唯一的解法就是统一加MOD取模或者先转成unsigned再算。6.4 哈希表的扩容和 rehash手写哈希表一般不会自动扩容所以入门选手选一个大桶数组直接静态分配就好。但如果你的键数量不可预估或者你打算把这份模板用在工程代码里那么需要实现扩容当装载因子超过某个阈值比如 0.75就把桶数组扩大一倍把所有元素重新插入。在竞赛里静态分配大数组是性价比最高的方案。因为扩容逻辑本身有 bug 风险而且new再delete的代价并不低。不过你要理解扩容的思路毕竟这是面试和工程里绕不开的考点。6.5 用unordered_map和手写哈希该怎么权衡洛谷允许用unordered_map过很多题因为题目的数据范围不一定卡你。但如果你要用它有两点必须注意自定义类型比如pairint,int需要自己提供哈希函数和相等比较否则编译不过。unordered_map在某些版本的 C 标准库里有反哈希攻击的保护但实测性能在极端情况下可能不如手写。我个人的建议是对于模板题手写一遍哈希表AC 之后再用unordered_map重写一版对比一下你会对手写优势有更直观的感受。刷题的核心目的是掌握原理而不是追求最快 AC。7. 从模板题延伸出去的几个使用场景学习模板题的最高境界是能看出它在别的题里“换皮”。哈希表在竞赛里的应用非常多我这里列三个最常见的给后面刷题做个铺垫。7.1 离散化离散化是把范围很大的数值映射到连续的 1..M。经典做法是先排序再去重然后用二分查下标。但如果你不想排序可以借助哈希表先给每个值分配一个 id之后直接用 id 作为数组下标。这在键数量不多但有大量查询的场景下特别好用。7.2 记忆化搜索记忆化搜索的本质就是“保存已经算过的状态避免重复计算”。状态往往是个多维的组合比如(pos, mask, cnt)。你当然可以用高维数组来存但如果状态空间很稀疏比如只有 10^5 个状态会真正被访问而完整状态空间是 10^9哈希表就是唯一可行的方案。做法把多维状态编码成一个字符串或一个long long然后用哈希表存答案。这是很多状态压缩 DP 题目的关键优化。7.3 集合差集与去重哈希表的查找是 O(1)所以凡是需要在 O(1) 时间内判断“某个东西在不在集合里”的场景都可以考虑哈希表。比如统计一批数字中哪些出现过两次、求两个数组的交集、判断一条路径上有没有重复节点等等。这些题的难点往往不在哈希表本身而在你能否想到“我要用集合来维护”。8. 我实际做题时的几个习惯最后分享一些我自己的做题习惯不一定是最优解但都是实战检验过的。第一先把“键”抽象出来。不管题目给的是整数、字符串还是二元组我都先在纸上写清楚哈希函数输入是什么输出是什么桶里要存哪些信息。很多时候思路卡住不是哈希表不会写而是“键和值”没想明白。第二能静态分配就不用动态内存。我在第 3 节已经提过内存池这里再强调一次静态数组配合预分配的内存池既不慢也不容易出内存泄漏调试起来还方便。唯一要注意的是数组大小别开小了这个靠读题面的数据范围就能判断。第三写完代码先测边界数据。负数、0、重复插入、删除不存在的元素、删除后继续插入这些操作对应哈希表的各个分支很可能藏着 bug。模板题虽然往往数据温和但你写出来的模板是要以后复用的不把边界情况测清楚后面用的时候迟早要踩坑。第四不要过早优化。哈希函数加扰动、用二级指针、内存池都是优化手段但代码可读性和正确性永远排第一。先把最朴素、最直白的写法跑通再在清楚瓶颈的情况下做优化。比如第 3 节的代码我用new就直接能过很多题不需要一开始就上内存池。P11615 这样的模板题很多人会觉得“题解都差不多没啥好写”。但如果你把这道题当成理解哈希表的起点花时间把冲突处理、模数选择、删除逻辑这几个点彻底弄明白那这道题的价值就远超一道 AC 记录本身。哈希表在后面的树、图、DP 优化里反复出现早一天把这个基本功打牢后面刷题会顺很多。