哈希表这个东西很多同学在洛谷上刷题迟早会撞上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 里也有HashMapPython 的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 ArrayListInteger[] 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一个比预期数据量稍大的质数比如 1000003MAXN操作次数的上限 一个余量有人会问MOD 1000003但数据量只有 10^5是不是浪费空间完全不是。桶数组每个元素只是一个 int100 万个 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拖后腿也是白搭。我把这些坑整理成一张速查表方便你写代码前挨个自检常见问题典型症状解决办法负数取模越界数据含负数时 WA(x % MOD MOD) % MODhead 数组未初始化插入 0 或查 0 异常memset(head, -1, sizeof(head))模数不是质数冲突率偏高链表变长模数选大质数如 1000003MAXN 开小了运行时报错或越界按操作次数上限 余量开查询只查链头冲突数据查不到查询用 for 完整遍历链表Java Scanner 太慢大数据量 TLE用 BufferedReader 或 FastReader忘记用 StringBuilder 攒答案Java 频繁 IO 导致 TLE全部拼接后一次性输出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 它不算本事把这套东西理解透、能灵活迁移到后面的实战题目里才是它存在的真正意义。 
长河君 · 2026/10/10 13:04:40 · 阅读 1.2k 从原理到实战：手写哈希表为什么是竞赛选手的必备技能？
哈希表这个东西很多同学在洛谷上刷题迟早会撞上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 里也有HashMapPython 的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 ArrayListInteger[] 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一个比预期数据量稍大的质数比如 1000003MAXN操作次数的上限 一个余量有人会问MOD 1000003但数据量只有 10^5是不是浪费空间完全不是。桶数组每个元素只是一个 int100 万个 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拖后腿也是白搭。我把这些坑整理成一张速查表方便你写代码前挨个自检常见问题典型症状解决办法负数取模越界数据含负数时 WA(x % MOD MOD) % MODhead 数组未初始化插入 0 或查 0 异常memset(head, -1, sizeof(head))模数不是质数冲突率偏高链表变长模数选大质数如 1000003MAXN 开小了运行时报错或越界按操作次数上限 余量开查询只查链头冲突数据查不到查询用 for 完整遍历链表Java Scanner 太慢大数据量 TLE用 BufferedReader 或 FastReader忘记用 StringBuilder 攒答案Java 频繁 IO 导致 TLE全部拼接后一次性输出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 它不算本事把这套东西理解透、能灵活迁移到后面的实战题目里才是它存在的真正意义。