从原理到实战：手写哈希表为什么是竞赛选手的必备技能？

哈希表这个东西，很多同学在洛谷上刷题迟早会撞上，P11615 这道【模板】题就是个很标准的敲门砖。我记得自己当年第一次见这题时，满脑子都是“这不就是 map 吗，凭什么要我自己写”，后来真在比赛里被卡了几次常数、被卡了几次内存，才明白手写哈希表到底值在哪儿。这篇东西我不打算只贴一份能 AC 的代码，而是把哈希表从原理到实现、从踩坑到调优，按我自己的理解完整讲一遍。代码会给出 C++ 和 Java 两个版本，你要是在洛谷刷题或者准备蓝桥杯、ICPC 这类比赛，认真看完应该能少走很多弯路。

1. 哈希表到底在解决什么问题

1.1 数组的局限与键值映射的痛点

先聊一个最朴素的问题：数组的随机访问是 O(1)，快得离谱，但它的下标只能是整数，而且必须是连续的。比如你有一批学生信息，学号从 1001 到 2000，想按学号查名字，开一个长度 2000 的数组就行，直接用student[1001] 就能拿到数据。可如果学号变成了字符串，比如 "A20240001"，数组下标就无能为力了。更麻烦的是，有些键根本不连续，比如你只有三个学号 1001、99999、88888888，难道为了存三条记录开一个八千万长度的数组？显然不现实。

这时候就需要一种结构：既能像数组一样快速定位，又不要求键是连续整数。哈希表（Hash Table）就是为这个场景诞生的。它的核心思路特别直白：设计一个函数，把任意类型的键转换成一个整数下标，然后把这个键值对存到数组的对应位置。这个函数就叫哈希函数（Hash Function），存数据的数组叫桶数组（Bucket Array）。

你完全可以这样理解：哈希函数就是一本“翻译词典”，它负责把千奇百怪的键翻译成数组听得懂的编号。查询的时候，同样用这本词典翻译一次，直接去对应位置取数据，平均时间复杂度能做到 O(1)。这就是“空间换时间”——我们付出的是额外设计哈希函数和维护桶数组的代价，换来的是接近数组的查询速度。

1.2 为什么洛谷要专门出一道模板题

你可能觉得，C++ 里不是有std::map和std::unordered_map吗？Java 里也有HashMap，Python 的dict本身就是哈希表。既然现成的工具一堆，为什么还要手写？

这里面有个很现实的理由：模板题的根本目的不是让你“用上”哈希表，而是让你“理解”哈希表。map底层是红黑树，查询 O(log n)，unordered_map底层是哈希表，平均 O(1)，但你要是连桶、冲突、负载因子这些概念都不清楚，遇到卡哈希的题目就只能瞪眼。竞赛真题里经常出现“构造数据卡掉默认哈希”这种操作，比如某些 OJ 的unordered_map用固定哈希函数，出题人可以构造一串字符串让它们全落在同一个桶里，查询直接退化成 O(n)。这时候你要是会手写哈希、会选模数、会设计冲突处理策略，就能轻松绕过去。

另外，手写哈希表的性能通常比 STL 容器更好。模板题的数据量一般不算极端，但很多题目用map会超时，用unordered_map可能内存爆炸（因为它为了支持迭代器，底层维护了很多额外结构）。自己维护一个精简的哈希表，插入、查询都是几条语句的事，常数极小。这就是为什么刷题到了中后期，手写哈希几乎成了必备技能。

2. 哈希函数与冲突处理：两种核心方案的取舍

2.1 哈希函数设计的三个原则

哈希函数是整个哈希表的灵魂，设计得好不好，直接影响冲突发生的概率。一个好的哈希函数通常满足三个特点：计算简单、分布均匀、结果确定。

• 计算简单：函数本身不能太复杂，否则查一次要算半天，O(1) 就名存实亡了。字符串哈希里常见的 BKDR 算法、数字哈希里的取模运算，都是轻量级操作。
• 分布均匀：不同的键尽量映射到不同的桶。如果一堆键全挤到一个桶里，冲突就会爆炸。
• 结果确定：同一个键任何时候计算，结果必须一致。这是哈希表能正常工作的前提。

对整数键，最常用的哈希函数就是取模：H(x) = x % MOD。这里MOD的选择非常有讲究。很多人图省事直接用数组长度，比如x % 100000，这其实埋着隐患。假设你的键全是偶数，x % 100000的结果也全是偶数，那奇数编号的桶全空着，一半空间白费，冲突概率还翻倍。更差的情况是键都是 10 的倍数，那x % 100000的结果永远是 0，所有数据全挤进一个桶，哈希表直接退化成一条链表。

实际竞赛里，模数通常选一个“比较大的质数”。质数能减少公约数导致的分布不均问题，比如 1000003、1000033、10000019 这类都是经典的质数取值。经验法则是：模数取一个比你预计数据量大的质数，可以让数据在桶里铺得比较开。我常用1000003作为中小型题目的模数，数据量特别大的时候换成10000019，基本没翻过车。

2.2 链地址法：最直观也最稳妥的做法

有了哈希函数，下一个绕不开的问题是冲突。什么叫冲突？就是两个不同的键算出来同一个桶下标，比如 7 和 1000000 对 1000003 取模都等于 7，它们就要抢同一个位置。解决冲突的主流方案有两种：链地址法（拉链法）和开放寻址法。

链地址法的思路很朴素：每个桶不存数据本身，而是存一条链表的头节点。插入新键时，先计算它在哪个桶，然后往那条链表里挂一个节点；查询时同样定位到桶，再沿着链表一个个比对。

链地址法优点非常明显：

• 实现简单，思维负担小
• 删除操作直接操作链表，很方便
• 负载因子（数据量/桶数量）即使超过 1 也能正常工作，只是链表变长、查询变慢而已

竞赛中我百分之九十九的情况都用链地址法，因为它的上限稳定，最坏情况也“只是”退化成一条链表，不会出现开放寻址法那样无限探测的尴尬。链地址法有两种写法：一种是真的用vector + list或者vector + vector来模拟，随手就能写；另一种是数组模拟链表——用几个平行数组存节点的值和下一个节点的下标，逻辑和链式前向星几乎一模一样。后者在性能上更优，因为内存连续、指针开销小，后面我会给出完整代码。

2.3 开放寻址法：省内存但暗藏陷阱

开放寻址法则是另一种思路：数据直接存在桶数组里，冲突了就去寻找下一个空位。最常用的是线性探测：如果H(x)的位置被占了，就依次看H(x)+1、H(x)+2……直到找到空位。查询的时候也沿着同样的顺序找，直到找到目标或者遇到空位才停止。

开放寻址法的好处是空间利用率高，不需要额外链表结构，适合内存抠得很紧的题目。但它的坑也很多：

• 删除极其麻烦：不能直接清空位置，否则会截断后续探测路径。正确做法是“懒删除”，也就是给位置打一个删除标记，查询时跳过删除标记，插入时优先复用删除标记的位置。这个细节十个人有八个会踩。
• 负载因子必须严格控制：一旦数据量超过桶数组的 70%，冲突会急剧增多，插入和查询都会明显变慢。这个“临界点”不好把控，扩不扩容全凭经验。
• 容易引起聚集：线性探测会让冲突元素扎堆，形成一片连续占用区，后面的插入更频繁地撞上这片区域。

所以我个人建议：除非题目明确要求内存极小、或者你特别熟悉开放寻址法，否则默认选链地址法。做人要稳妥，写代码更是如此。

3. 完整模板实现：C++ 与 Java 两个版本逐段拆解

3.1 数组模拟链表的 C++ 实现

先解释一下数据结构。链地址法用三个平行数组：

• head[i]：第i个桶的链表头节点编号，初始为 -1 表示空
• ver[idx]：编号为idx的节点存的键值
• nxt[idx]：编号为idx的节点指向的下一个节点编号

插入时，先给新节点分配一个编号idx，让ver[idx] = x，然后把它链到head[H(x)]的头部：nxt[idx] = head[H(x)]，head[H(x)] = idx。这种头插法操作 O(1)，而且不需要遍历链表。

查询时，从head[H(x)]出发，沿着nxt一路走，逐个比较ver[i] == x，找到返回 true，走完链表都没找到返回 false。

#include <cstdio> #include <cstring> const int MOD = 1000003; const int MAXN = 1000005; // head[桶编号] = 链表头节点编号，-1 表示空 int head[MOD]; // ver[节点编号] = 键值, nxt[节点编号] = 下一个节点编号 int ver[MAXN], nxt[MAXN]; // idx 表示当前已经用到第几个节点 int idx = 0; inline int H(int x) { return (x % MOD + MOD) % MOD; } void insert(int x) { int h = H(x); // 新节点存值 ver[idx] = x; // 头插法：新节点的 next 指向当前链头 nxt[idx] = head[h]; // 更新链头 head[h] = idx; idx++; } bool find(int x) { int h = H(x); for (int i = head[h]; i != -1; i = nxt[i]) { if (ver[i] == x) return true; } return false; } int main() { // head 数组全部置为 -1 memset(head, -1, sizeof(head)); int n; scanf("%d", &n); while (n--) { char op[5]; int x; scanf("%s %d", op, &x); if (op[0] == 'I') { insert(x); } else { printf(find(x) ? "Yes\n" : "No\n"); } } return 0; }

逐段看几个关键点：

• H(x)里为什么写(x % MOD + MOD) % MOD？因为 C++ 的负整数取模结果可能是负数，比如-7 % 5 = -2，直接拿它当数组下标会越界。先加上一个MOD再取模，能把结果规整到[0, MOD-1]区间。这个坑刷负数数据的题必踩，别问我怎么知道的。
• memset(head, -1, sizeof(head))是必须的，因为head数组初始全是 0，而 0 会被误认为是合法节点编号。不用-1初始化的话，空桶会被当成“链头指向 0 号节点”，产生一条根本没有存储数据的假链表。
• idx从 0 开始累加，每个节点只分配一次编号，所以插入操作不需要动态分配内存，效率比new高一个量级。数组长度MAXN建议开数据量上限再加一点余量，比如题面说最多 10^5 次操作，开 1000005 就稳了，多出来的 5 是为了防止idx越界，属于个人小习惯。

3.2 Java 手写版与 HashMap 的对比

Java 选手用内置的HashMap做这题也会非常轻松，一句map.getOrDefault(x, 0)就能统计频率、一个map.containsKey(x)就能查询。那我为什么还要给出手写版？因为 Java 的HashMap在竞赛里的表现并不总是可靠。默认负载因子 0.75，扩容时要把所有元素重新哈希，数据量大时开销很可观；而且自动装箱拆箱会产生大量中间对象，拖慢速度，内存占用也不小。手写版的逻辑虽然长，但胜在完全可控。

Java 手写版本用“二维动态数组”模拟拉链是最好懂的写法：

import java.util.ArrayList; import java.util.Scanner; public class Main { static final int MOD = 1000003; static ArrayList<Integer>[] buckets; static { buckets = new ArrayList[MOD]; for (int i = 0; i < MOD; i++) { buckets[i] = new ArrayList<>(); } } static int hash(int x) { return (x % MOD + MOD) % MOD; } static void insert(int x) { int h = hash(x); if (!buckets[h].contains(x)) { buckets[h].add(x); } } static boolean find(int x) { int h = hash(x); return buckets[h].contains(x); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); StringBuilder sb = new StringBuilder(); while (n-- > 0) { String op = sc.next(); int x = sc.nextInt(); if (op.charAt(0) == 'I') { insert(x); } else { sb.append(find(x) ? "Yes\n" : "No\n"); } } System.out.print(sb); } }

这个版本本质上每个桶就是一个小动态数组，contains方法内部做线性扫描，数据不冲突时桶内只有一两个元素，扫描成本很低；数据构造得毒的时候才会退化。Java 版的关键优化是用StringBuilder攒答案，而不是查一次System.out.println一次——后者的 IO 开销能让你直接 TLE。这也是 Java 选手在 OJ 上必须养成的习惯，千万别小看这块性能损耗。

手写版和HashMap怎么选？我的意见是：模板题和教学场景用手写版，吃透原理；正式比赛如果题目没卡哈希，直接HashMap最省事；一旦发现题目故意构造数据或时间卡得很紧，立刻换手写版。两套都要会，这不是“二选一”的事，是“互为备份”的事。

3.3 模板的通用化：不只是整数才能用

这份整数哈希模板非常容易扩展成字符串版本。字符串哈希常用的办法是把它当成一个 131 进制（或者 13331 进制）的大整数，边遍历边取模：

inline int hashString(const char* s) { unsigned long long h = 0; for (int i = 0; s[i]; i++) { h = h * 131 + s[i]; } return h % MOD; }

选 131 这个乘数不是因为玄学，而是它作为质数，能让字符串各位字符在哈希值里充分混合，分布比较均匀。字符串很长的时候，可以先算哈希值，再决定存入哪个桶，判断相等时再逐字符比较，避免哈希碰撞导致的误判。刷字符串哈希题、统计单词频率题的时候，把整数版本里的int x换成const char* s，配上strcmp，就是一份可用的字符串哈希模板。很多选手搞不清楚“哈希表”和“字符串哈希”的区别，其实前者是一种数据结构，后者是哈希函数设计的一种应用场景——数据结构上它们共享同一套骨架。

4. 常见错误与排查技巧：那些让我 WA 到怀疑人生的细节

4.1 负数和零的处理：正确性坑里最大的一个

我第一次提交 P11615 时，自信满满，结果 WA 了两发，问题就出在负数。题目给的x范围是[-10^9, 10^9]，负数取模后是负数，head[-1]这种操作在 C++ 里不会立刻报错，它会静默访问越界内存，然后给出一个毫无规律可言的错误结果。这个 bug 最难查的地方在于它不是必现的——数据里没负数就 AC，有负数就 WA，你甚至会怀疑是不是哈希函数写错了。

解决办法就是我前面提到的(x % MOD + MOD) % MOD。这行代码干的活很简单：负数取模后加一个模数，再取模，把结果“掰正”。记住，只要题目数据范围包含负整数，这个修正必须写，没有例外。

另外还有一个隐蔽问题：0的存在。我在 3.1 节说过，head数组必须初始化为 -1，原因就是 0 会被当成合法节点编号。如果你忘了初始化，往表里插入 0 和插入任何一个x % MOD == 0的数都会跟假想的 0 号节点纠缠不清，轻则查询错误，重则死循环。所以初始化别偷懒，memset(head, -1, sizeof(head))六个字，救你一夜的头发。

4.2 模数与数组容量的匹配

模数和数组容量不匹配是另一个高频坑。我发现很多新手喜欢让模数跟MAXN一样大，比如数据量最多 10^5，就设MOD = 100000、MAXN = 100000。这里有个连环问题：MOD必须是质数才能均匀分布，100000 显然不是；MAXN应该对应“节点总数量上限”，而不是桶数量。链地址法里，每个插入操作都会产生一个新节点，所以MAXN取操作总次数上限。如果MAXN取小了，idx会越界；如果MOD取合数，冲突率会莫名其妙地高。正确的配置是：

• MOD：一个比预期数据量稍大的质数，比如 1000003
• MAXN：操作次数的上限 + 一个余量

有人会问，MOD = 1000003但数据量只有 10^5，是不是浪费空间？完全不是。桶数组每个元素只是一个 int，100 万个 int 大概 4MB 内存，对于 OJ 动辄 256MB 的内存限制来说，这点开销完全不是事。用一点空间换均匀分布，这笔账非常划算。

4.3 查询与插入逻辑的细微差别

还有一个特别容易犯的错：把“插入”当成“无论如何都插”，而把“查询”写成了 Insert 的复制粘贴。插入和查询确实都先算桶编号，但从桶里取出的动作不一样——插入是创建新节点、修改nxt指针、更新链头；查询是沿链表遍历、比较值、返回 bool。很多时候代码写着写着，查询就漏了for循环，只比了链头一个节点，结果所有冲突数据全都查不到。这个问题排查起来特别烦，因为数据不冲突时它 AC，冲突时它 WA，让人百思不得其解。

我的习惯是：把查询和插入两个函数分开写，插入函数一定不要返回 bool（除非题目要求判重），查询函数一定不要修改任何数组。这两个函数在逻辑上必须“井水不犯河水”，一旦你想顺手在查询里改点什么，多半就要出事。所有修改状态的操作，只能发生在插入函数内部。

4.4 TLE 不一定是哈希的错：IO 优化也要跟上

有段时间我在讨论区看一道题目的提交记录，许多同学手写哈希写得很好，但就是 TLE，最后发现问题出在 IO 上。C++ 的cin/cout默认同步 C 的stdio，性能很差，数据量一大就很伤。要么用scanf/printf，要么在main开头加两行：

ios::sync_with_stdio(false); cin.tie(0);

Java 端更夸张，Scanner的解析速度极慢，大数据量下动不动就 TLE。换用BufferedReader + StringTokenizer或者手写FastReader都能明显提速。IO 这个东西在洛谷题解区很少被强调，但实际比赛里 IO 时间和算法时间同样珍贵。哈希表 O(1) 的查询再快，被一个慢吞吞的Scanner拖后腿，也是白搭。

我把这些坑整理成一张速查表，方便你写代码前挨个自检：

5. 从模板题到真正的竞赛实战

5.1 哈希表在题目中的三种典型用法

把模板题吃透以后，你会在很多题目里看到哈希表的身影。我总结了三种最常见的用法。

第一种是去重。给一串数，问里面有多少个不同的数。很多人都知道用set，但set是平衡树结构，插入 O(log n) 且常数大。哈希表插入时先查一下在不在，不在才插，顺便统计个数，一趟搞定，效率高出一个量级。我拿这个模板做过一道 100 万级别的去重题，手写哈希跑得比unordered_set还快，内存还小。

第二种是频率统计。洛谷的“统计单词出现次数”“统计成绩档位人数”这类题，本质上就是键值对映射。用哈希表存每个键出现的次数，插入时freq[x]++，查询时直接读。这种场景下，哈希表里的“值”不一定是原键，也可以是一个计数器。你甚至可以换成二维哈希或结构体存储，比如键是一个坐标(x, y)，值是一个标记，照样能处理，只要你会设计哈希函数把结构体转成整数。

第三种是映射关系存储。这其实是哈希表最“正统”的用途：键值对。比如 CF 里常见“给一个序列，问每个数在另一个序列里的位置”，用哈希表存值 -> 下标的映射，一次遍历全部查完。map也能做，但当数据量到 10^6 量级时，两者性能差距就很明显了。

5.2 哈希表和字典、map 的区别，到底怎么跟别人唠明白

搜索热词里有个“哈希表和字典的区别”，正好借这题说明白。哈希表是数据结构本身的名称，它描述的是“用哈希函数散列键、解决冲突、O(1) 访问”这一整套机制。字典（Dictionary）在不同语言里对应不同的内置容器——Python 的dict、Java 的HashMap、C++ 的unordered_map，它们底层基本都是哈希表，只是包装了更多功能，比如自动扩容、迭代顺序、线程安全策略等。而 C++ 的map不一样，它底层是红黑树，保证按键排序，但查询是 O(log n)，不是哈希表。

一句话总结：哈希表是一种底层思想实现，字典是编程语言层面的封装产品，map 可能是哈希表也可能是红黑树，得看具体语言。跟别人聊这个区别时，你只要抓住“性能取决于底层结构而不是容器名字”这个点，就算真的懂了。

5.3 什么时候该手写，什么时候该调包

我见过一些人走向两个极端：一种恨不得啥都手写，连用个队列都要自己造轮子，浪费时间；另一种从头到尾只会unordered_map，比赛被卡了哈希就抓瞎。我的建议分三层：

• 日常刷题：能用现成容器就用现成容器，重点是算法思路
• 备战竞赛：手写哈希作为必练项，专门找一些卡哈希的题目训练
• 实际比赛：提前确定好策略，数据量小、无恶意数据用 STL/内置容器，数据量大或疑似被卡时果断换手写

判断数据是否被卡有个笨办法：本地随机生成大一点的数据先跑一遍，如果unordered_map明显比平时慢，多半是哈希碰撞严重，赶紧换手写模板。好多老手赛前会提前准备好几个常用模板放进代码库，哈希表、快读、并查集、树状数组这些，到时直接复制粘贴改参数。这个习惯我很推荐，能省下大量时间专注思考题目本身。

5.4 真实比赛题目里的哈希表变体

模板题解决的是最基础的插入查询，但真实题目很少这么直白。我去年做过一道洛谷的月赛题，题目给了一个排列，要求统计所有“区间极差小于等于 k”的区间里有多少个不同的值。解法里既要用滑动窗口维护区间，又要用哈希表做值频次统计，还得拿一个变量记录当前窗口有多少个不同的数。这题不要求你输出哈希表的实现细节，但你必须理解哈希表在“动态频率统计”里怎么用——桶里存的不是键本身，而是键对应的频次计数。类似地，很多图的题目里，你要给边或点做编号映射，结构体哈希就派上用场了。

再比如搜索题里的“状态判重”。八数码、推箱子这类题目，状态是一个排列或一个棋盘，你需要快速判断当前状态是否访问过。把状态转换成一个字符串或者一个整数，塞进哈希表作为 visited 标记，这就是哈希表在搜索剪枝里的经典应用。我碰到最多的情况是用“三维坐标转一维编号 + 哈希表判重”来写三维 BFS。这些题目共同点都是：核心数据结构就是哈希表，但套了一层应用场景的外壳。你手里这份模板，改一改照样扛得住。

6. 最后再分享一个我调试哈希表时的小技巧

调试哈希表最痛苦的地方在于：数据量一大，你根本不知道哪个键查不到、哪次插入出了问题。我后来养成一个习惯，在调试版本里把桶的长度、最长链表长度、总冲突次数打印出来。这三个指标直接反映了哈希函数选得好不好。

• 桶的平均长度 = 总元素数 / 桶数量，理想情况下接近 1
• 最长链表长度如果超过平均长度的 10 倍，说明哈希函数分布极差
• 总冲突次数如果等于总元素数，那基本等于所有元素都冲突了，跟没散列一样

正常来说，模数选质数后，最长链表长度和平均长度差距不会太大。如果你发现某一道题哈希表表现异常，先别急着改冲突处理，把哈希函数换一下往往更有效。比如整数取模不行就试试乘法散列——用(x * 2654435761u) >> 20这类位运算哈希，把高 20 位当桶编号。这种散列方式在数据规律性很强（比如全是偶数、全是等差数列）的时候，效果会比取模更好。

哈希表的调试说白了就是“用数据说话”，别靠猜。把这三个指标打印出来看一眼，问题往往一目了然。P11615 作为模板题，你 AC 它不算本事，把这套东西理解透、能灵活迁移到后面的实战题目里，才是它存在的真正意义。