刷信息学奥赛一本通的朋友对 1456 这道“图书管理”应该不陌生。它是一道非常标准的哈希表模板题系统里有一堆 add 操作往集合中加书名还有一堆 find 操作询问某本书是否存在。很多人第一次遇到它时第一反应是拿std::map或std::set直接写确实能过但题号前挂着的“【模板哈希表】”提醒我们这道题真正想让你练的是自己动手实现一张哈希表而不是只依赖现成的红黑树容器。本文我会把从读题到写完模板的关键节点全部拆开为什么非哈希不可、哈希函数和容量怎么选、拉链法和开放寻址法两套代码怎么背以及藏在输入数据里的坑。如果你正准备用这道题入门哈希表或者想把手写哈希练成肌肉记忆可以直接照抄这套模板再花十分钟把后面的原理补上。1. 这道题的暴力解法为什么过不去先算一笔复杂度账1.1 先看题add 与 find 的本质题目结构很简单去掉包装本质就是维护一个字符串集合。遇到add 书名就往集合里放一本书遇到find 书名就查一下这本书有没有出现过出现过输出Yes没出现过输出No。初始时集合是空的。我这里不打算死记原题的具体数据范围因为一本通题库在不同版本里可能有差异但这类模板题的操作次数一般都在万级到十万级书名长度往往也不会短到可以忽略。别小看这个“维护集合”的要求它背后藏的是一个经典的动态查找问题数据在不停插入还要回答若干次存在性查询。如果每次查询都从头扫一遍整个集合复杂度立刻失控。1.2 暴力解法的时间账单最直觉的写法是维护一个vectorstring booksadd就直接push_backfind就 for 循环逐个比较。假设总操作数为 n其中插入操作和查询操作各占一半每个书名的长度是 L那么一次查询的最坏情况要比较 n/2 个字符串每个字符串比较又最多要扫 L 个字符单次查询就是 O(nL)。把数字带进去感受一下。如果 n 100000L 100那全部查询下来大约是 100000 / 2 次查询每次查 50000 个字符串每个字符串比 100 个字符你会在脑子里算出这样一个量级50000 次查询乘以 50000 个字符串乘以 100 个字符结果是 2.5 乘以 10 的 11 次方次字符比较。这个量级在竞赛环境下基本等于铁定超时。有人可能会说那我不扫 vector我用std::mapstring, bool不就行了吗map底层是红黑树单次查找是 O(log n)理论上也能过。但你要知道这道题叫“模板哈希表”不是“模板平衡树”。map虽然复杂度对数级别看起来很稳定可它常数不小而且在后续很多场景里哈希表的思想才是正解——字符串哈希判重、大整数映射、二维坐标压缩全都依赖这张表。1.3 哈希表是怎么把查询变成 O(1) 的哈希表的想法非常朴素与其把所有书放在一个大仓库里每次挨个翻找不如先给每本书算一个“门牌号”然后直接走到对应的房间门口只要看这个房间里有没有就行。具体到实现就是把一个字符串通过某种规则压缩成一个整数下标然后用这个下标去访问一个数组。不同的字符串可能算出同一个下标这就是“哈希冲突”。冲突不可避免但我们可以用拉链法在同一个下标下挂一条链表或者用开放寻址法去找下一个空位。只要冲突控制得当平均查询复杂度就是 O(1)。这一步是整个模板的基石。很多初学者背代码却不清楚为什么head数组、nxt数组、val数组三件套要这么组合。下面我会把哈希函数、容量选择和冲突处理这三个核心决策单独拎出来讲。2. 哈希表的核心三要素哈希函数、桶容量与冲突策略2.1 哈希函数把字符串压成一个无符号整数字符串不能直接当数组下标所以第一步要设计一个函数把字符串映射成整数。竞赛里最常见的字符串哈希算法是 BKDR 哈希核心公式是unsigned long long calcHash(const string s) { unsigned long long val 0; for (char c : s) { val val * 131 c; } return val; }这个循环做了什么你可以把字符串想象成一个 131 进制的大整数。比如字符串abc第一次循环算出的值是 a第二次变成 a131b第三次变成 (a131b)131c展开之后就是 a131^2 b*131 c。也就是说BKDR 哈希本质上是在把一个字符串编码成一个巨大无比的数字。为什么要选 131 或者 13331 这种质数当种子因为如果种子和模数有公因子不同字符串算出来的哈希值就更容易撞在一起。131 是质数乘法和加法混合之后分布比较均匀。unsigned long long在 C 里是 64 位无符号整数乘法溢出时会自动对 2 的 64 次方取模所以你不需要手动处理溢出这是一个被广泛使用的特性。需要注意桶下标不能直接拿这个 64 位整数当用否则数组得开 2 的 64 次方那么大。正确做法是让哈希值对桶数量取模也就是calcHash(s) % N得到一个 0 到 N-1 之间的下标。2.2 桶容量不是随便开的哈希表的桶数量 N 是一个关键参数。如果开太小所有字符串都往少数几个桶里挤冲突严重退化成链表遍历如果开太大浪费内存。竞赛场景里的经验值是拉链法下N 取 100003、200003、1000003 这类质数只要大于可能插入的元素数量即可。为什么压力推荐质数因为 BKDR 哈希的乘法特性里如果取模的模数是合数可能会和种子产生周期性的公因子导致某些规律构造的数据大量碰撞。比如模数是 2 的幂时结果只由低位决定很容易被特殊数据卡掉。质数取模虽然不是说绝对无碰撞但均匀性要好得多。开放寻址法的容量要求更苛刻。因为线性探测要靠空位来终止查找装载因子已占用位置 / 总容量太高时查找会连锁探测效率暴跌。一般建议桶数组开到实际插入数量的两倍以上所以如果操作数上限是 100000我就开 200003留出足够的空位。2.3 冲突处理拉链法与开放寻址法的江湖地位再好的哈希函数也不能保证完全无冲突所以必须有一套冲突处理策略。主流有两类拉链法和开放寻址法。拉链法是在每个桶位置挂一条链表。哈希值相同的字符串都进同一个桶查找的时候遍历这条链表。这样即使冲突链表平均长度也很短不影响整体效率。实现时可以用 vector 动态数组当桶但竞赛更常用静态数组模拟链表因为速度更快。开放寻址法则是整个数组只放一份数据一旦发现目标位置被别人占了就按某种规则继续找下一个空位。最简单的是线性探测下标 h 被占了就看 h1h2一路找下去。这种方式不额外占用链表节点内存紧凑但如果装载因子太高会出现“聚集”现象——连续一段都被占满导致后续插入要探测很长一段距离才找到空位。这两套模板我都会在后面给完整代码。我的个人建议是如果是竞赛刷题优先把拉链法练熟因为它更通用还能顺便统计每个哈希值下挂了多少字符串如果只是解决某个小规模查询开放寻址法写起来更快。3. 模板一拉链法手写哈希表的完整代码与逐行讲解3.1 完整代码静态链表版下面是这份题目最标准的拉链法实现我用的是静态数组模拟链表而不是vectorstring h[N]原因稍后单独说。#include bits/stdc.h using namespace std; const int N 100003; const int MAXN 200010; unsigned long long calcHash(const string s) { unsigned long long val 0; for (char c : s) { val val * 131 c; } return val; } int head[N], nxt[MAXN], tot; string valStr[MAXN]; bool queryBook(const string s) { int h calcHash(s) % N; for (int i head[h]; i; i nxt[i]) { if (valStr[i] s) return true; } return false; } void addBook(const string s) { int h calcHash(s) % N; valStr[tot] s; nxt[tot] head[h]; head[h] tot; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); memset(head, 0, sizeof(head)); int n; cin n; string op, book; while (n--) { cin op book; if (op add) { if (!queryBook(book)) addBook(book); } else { cout (queryBook(book) ? Yes : No) \n; } } return 0; }3.2 关键细节逐行拆解head数组是哈希桶表头长度 N每个元素存储以该下标为表头的第一条链表节点的编号。nxt数组是每个节点指向的下一个节点编号valStr数组存真正的字符串内容tot是当前已使用的节点总数。三个数组配合取代了传统意义上的malloc和指针。addBook用的是头插法新节点先接上当前表头的旧节点再把表头指向新节点。我一开始学静态链表的时候总搞不清nxt[tot] head[h]和head[h] tot的顺序。其实你就想先把新节点的“下一个”指到原来的第一个节点再更新表头把新节点变成第一个。顺序反了的话原来的链表就断了。queryBook就顺着表头一路遍历判断条件就是valStr[i] s。这里必须强调判断的是原字符串相等而不是只比哈希值。虽然理论上我们可以只存哈希值来省空间但那样可能误判因为不同字符串可能算出同一个哈希值。这道题的数据量下每个桶的链表很短多存一个 string 不费多少空间却换来了正确性。还有一点小细节addBook里我加了if (!queryBook(book))这个判断再插入。严格来说这道题重复添加某一本已经存在的书答案不会变化但如果不判重开放寻址法会白白消耗空位拉链法也会让链表里出现重复节点。养成插入前先查重的好习惯能让你的模板在别的题目里更安全。3.3 为什么不用 vector 当桶很多人会写这样的版本vectorstring h[N];这确实能 AC而且代码看起来更短。但它有两个小问题第一程序启动时就要构造 N 个 vector 对象N 是十万级别光构造对象的开销就不小第二每次插入到 vector 尾部可能触发扩容和拷贝常数比静态链表大。在时间卡得紧的比赛里细节决定生死。静态链表版本的手写模板本质上是把一个“链表”压进了两个数组里牺牲一点点思维负担换来稳定的速度和可控的内存。我觉得刷题阶段还是值得多用这种写法它能强迫你理解指针链表到底是怎么串起来的。4. 模板二开放寻址法的实现以及它与拉链法的取舍4.1 完整代码线性探测版开放寻址法的代码比拉链法还要短因为不需要nxt数组。我用一个used数组来标记某个位置是否被占用避免用空字符串当空位判断——万一哪道题的书名就是空字符串那整个逻辑就崩了。#include bits/stdc.h using namespace std; const int M 200003; string table[M]; bool used[M]; unsigned long long calcHash(const string s) { unsigned long long val 0; for (char c : s) { val val * 131 c; } return val; } int locate(const string s) { int h calcHash(s) % M; while (used[h] table[h] ! s) { h (h 1) % M; } return h; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; string op, book; while (n--) { cin op book; int p locate(book); if (op add) { if (!used[p]) { used[p] true; table[p] book; } } else { cout (used[p] ? Yes : No) \n; } } return 0; }locate函数的逻辑是先算初始位置 h如果这个位置没被使用或者已经存放了同一个字符串就停下来否则不断向后探测(h 1) % M形成了一个环直到找到空位或者找到相同的字符串。在add操作里如果locate返回的位置没有被使用说明这本书不在表里直接放进去。如果位置已存在相同字符串说明书已经入库不需要再放。在find操作里只要used[p]为真说明要么找到了该字符串要么找到了一个已经被占用的位置且该位置就是它如果used[p]为假说明探测链走到一个空位这本书一定不存在。4.2 开放寻址法容易翻车的三个点第一装载因子一定要控制住。我刚才说 M 要开到插入数量的两倍以上不是随便拍脑袋。线性探测最怕表满了一旦装载因子接近 1哪怕只差一个位置都会出现一个很长的探测链查询从 O(1) 退化到近乎 O(n)。这里可以做个实验M100003插入 90000 个字符串再随机查询你会发现某些探测链长得离谱。而 M200003插入同样数量平均探测次数只有 1 到 2 次。第二删除操作非常麻烦。如果某本书被删了你直接把used[p]改成 false那本来探测链后面排着队的字符串就找不到了。正确做法是引入一个“墓碑”标记删除时标记成 DEL 而不是空位。本题没有删除操作所以我没写但如果以后遇到需要删元素的哈希表一定要想到这个点。第三locate里的字符串比较是必要的。和拉链法一样不能只存哈希值。虽然用 string 比较会多花一点时间但换来的正确性绝对值得。4.3 和拉链法对比什么时候用哪个我把两种方法放在一张表里方便你以后选题维度拉链法开放寻址法内存组织桶数组 节点池链表串联一个连续数组所有元素直接放里面冲突处理同桶挂链表向后找空位删除操作容易删链节点即可困难需要墓碑标记装载因子容忍度可以接近 1但链表变长一般不超过 0.7 到 0.8实现复杂度中等需要理解静态链表简单逻辑直白缓存友好性链表跳转缓存不友好数组连续缓存友好适用场景竞赛刷题、插入删除频繁小规模查询、初始化成本低我个人在比赛里更常用拉链法因为开放寻址对装载因子太敏感而很多题目不会告诉你数据会不会故意卡你。但如果你只是快速写一个工具函数比如处理几千个字符串的判重开放寻址法几行代码搞定非常舒服。5. 图书名字里的奇怪坑空格、换行与多组数据5.1 书名带空格cin 直接读只能读一半这是很多人在“图书管理”这道题上栽过的坑。题目背景是图书管理系统那你想想真实世界的书名C Primer、The Art of Computer Programming哪个不带空格有的题目数据里书名就是普通单词用cin op book能过但如果书名带有空格cin book会在第一个空格处停下来后面的内容全被丢到下一次读取里去了。我见过不止一个同学拿着题解代码怎么提交都错最后发现是数据里书名带了空格而他的读入逻辑把一整句书名拆成了好几个字符串查重时当然找不到。你在本地造数据时也一定要注意这一点最好直接把可能的坑提前堵上。5.2 更稳妥的整行解析方案既然书名可能包含空格最稳的做法是整行读入再手动把操作符和书名切开。下面这段是兼容性更强的读入逻辑string line; while (getline(cin, line)) { if (line.empty()) continue; size_t pos line.find( ); string op line.substr(0, pos); string book; if (pos ! string::npos) { book line.substr(pos 1); // 去掉书名前面的多余空格 size_t start book.find_first_not_of( ); if (start ! string::npos) book book.substr(start); else book.clear(); } if (op add) { if (!queryBook(book)) addBook(book); } else if (op find) { cout (queryBook(book) ? Yes : No) \n; } }这种方式要求我们按 EOF 判断输入结束而不是先读一个 n。如果原题是先给 n 再给 n 行操作那你可以在输入 n 之后用cin.ignore()吃掉落后的换行符再开始 getline。否则第一次 getline 会读到一个空字符串程序直接跳过一行操作白白丢数据。5.3 多组数据与 Windows 换行的隐藏问题一本通题库有些题目是多组测试数据每组先给操作次数 n然后是 n 行命令直到 EOF。如果用while (cin n)包一层循环体内记得重新初始化哈希表否则上一组的数据会污染下一组。我见过有人把memset(head, 0, sizeof(head))写在循环外第二组就开始输出错误结果排查半天才发现是初始化位置不对。还有一个 Windows 环境下的坑如果你在本地用 Windows 造数据行尾可能是\r\ngetline 读到\r也会把它留在字符串末尾导致书名末尾多一个\r字符。OJ 一般在 Linux 环境下跑数据不会带\r但如果你在本机自测就可能莫名奇妙的 WA。稳妥起见解析出书名后做一次清理if (!book.empty() book.back() \r) { book.pop_back(); }这种细节不是算法问题却会让代码在不同环境下飘忽不定值得记下来。6. 把模板改造成通用工具封装、双哈希与扩展6.1 把模板封装成可以带走的哈希结构模板题最大的价值是让你拥有一段可以复用的代码。不要每次新开一道题都把数组从零开始写一遍直接把拉链法封装成一个结构体会省很多事struct StringHash { int head[100003], nxt[200010], tot; string valStr[200010]; void init() { memset(head, 0, sizeof(head)); tot 0; } unsigned long long calcHash(const string s) { unsigned long long val 0; for (char c : s) val val * 131 c; return val; } void insert(const string s) { int h calcHash(s) % 100003; for (int i head[h]; i; i nxt[i]) { if (valStr[i] s) return; } valStr[tot] s; nxt[tot] head[h]; head[h] tot; } bool find(const string s) { int h calcHash(s) % 100003; for (int i head[h]; i; i nxt[i]) { if (valStr[i] s) return true; } return false; } };要注意这个结构体如果定义在局部head、nxt这种大数组会开在栈上可能爆栈。要么把结构体对象定义成全局要么在结构体内部改用vectorint。竞赛里我一般直接把对象定义为全局变量省心。6.2 双哈希把误判率继续压低上面模板虽然比较的是原字符串不会误判但有些时候你只存哈希值来省空间那就必须考虑碰撞。一个很实用的升级是双哈希用 131 和 13331 两个种子各算一个哈希值只有两个值都相同才认为字符串相同。两个哈希同时冲突的概率极低工程上基本可以忽略不计。pairunsigned long long, unsigned long long calcHash2(const string s) { unsigned long long a 0, b 0; for (char c : s) { a a * 131 c; b b * 13331 c; } return make_pair(a, b); }双哈希的本质相当于在另一个空间重新洗牌。单独一个哈希可能因为某些规律数据碰撞但两个独立种子同时碰撞的概率是相乘关系小到可以认为为零。如果你在写字符串判重题想省字符串比较的开销双哈希是性价比很高的改进。6.3 哈希表和字典到底啥关系热搜里有人问“哈希表和字典的区别”我顺手解释一下。字典Dictionary/Map是一种抽象数据结构强调“键值对映射”它只定义了应该提供什么操作比如按 key 查找 value。哈希表则是实现这种映射的一种具体底层结构它用哈希函数把 key 映射到数组位置来加快查找。C 里std::map是红黑树实现的字典std::unordered_map才是哈希表实现的字典。所以“哈希表和字典”并不是非此即彼的关系而是一个是底层工具一个是上层概念。理解了这一点你在看不同语言文档时就不会迷糊比如 Python 的 dict 底层就是一个动态扩容的哈希表。6.4 从这道题延伸开去最后给个扩展思路。想统计每种书出现多少次可以在节点里加一个计数插入时如果发现已经存在就把计数加一想输出所有出现过的书名可以从 0 到 N-1 遍历head数字再顺着链表把valStr全部收集起来。这些都是哈希表模板的常规变形。网上常有人把这道题叫“图书管理”名字听着很朴素但它在哈希表模板题里算是一个很经典的起点。我的经验是如果你想真正掌握哈希表不要只背代码一定要自己动手把拉链法改成开放寻址法再把封装好的结构体用到下一道判重题里。写坏几次、翻几次车你对“冲突处理”四个字的理解就会真正落地。刷完这道题再去碰字符串哈希、双模数哈希你会发现自己已经站上一个新台阶了。