★ FEATURED ARTICLE 正文开始1. 字符串哈希到底在解决什么问题1.1 一段比赛的朴素回忆先讲个故事。早些年打信息竞赛的时候我遇到过一个挺经典的题给一个长度为 (10^5) 的字符串每次询问两个子串是否相等。很多人第一反应就是直接截取子串然后比一比结果当然超时因为单次比较最坏就是 (O(L))而询问通常又是 (10^5) 级别那复杂度直接爆炸。后来某位学长跟我说“你把字符串当成一个数字比较字符串就是比较数字。”当时我脑子嗡了一下——对啊如果能把任意一个子串映射成一个整数判等就变成 (O(1)) 了。这个思路就是今天这篇博文的主角字符串哈希。字符串哈希是 ACM 算法竞赛里非常基础但极其实用的一类算法核心思想就是把字符串这种“无法直接比较大小”的东西通过一个数学映射转为一个整数然后用整数的相等判断代替字符串的逐字符匹配。你可能会问“那直接把字符串转成二进制整数不就行了”理论上可以但字符串太长那个“整数”会大到无法存储、无法计算。所以哈希的本质是在一个有限空间里做降维用可能碰撞换时间和空间的平衡。1.2 哈希在竞赛里的定位与适用范围在信息竞赛的算法体系里字符串哈希通常和 KMP、后缀数组、AC自动机、字典树放在一起讨论。KMP擅长单模式匹配后缀数组擅长排序和最长公共前缀但它们在很多场景里要么写法复杂、要么常数大、要么难以扩展。字符串哈希最大的优势是简单、直观、灵活能快速处理“子串相等判断”这一基本操作并在此基础上延伸出很多高级用法。适合学字符串哈希的人我觉得有两类刚开始接触数据结构和字符串算法的新手想找一种容易理解的工具来解决字符串判等问题已经会 KMP、后缀数组但遇到某些需要动态修改字符串、或者在两个字符串之间做快速比较的场景时发现经典算法实现成本高想找一个更轻量的方案。当然哈希也不是万能的。它存在碰撞概率在严格意义上不是“正确”算法而是“高概率正确”的随机化算法。但正因为概率可以被压到极低它在竞赛和工程实践中被广泛接受。学习的时候你要理解一个核心矛盾哈希的本质是牺牲确定性换取效率而我们要做的事就是通过选择合适的进制、模数、双哈希等手段把碰撞概率压到近乎为零。2. 核心原理多项式哈希的数学底子2.1 一个公式看懂字符串怎么变成数字字符串哈希最常见的方案是多项式哈希也叫滚动哈希。它的公式长这样[ H(s) \left( \sum_{i0}^{n-1} ord(s[i]) \times base^{n-1-i} \right) \bmod mod ]其中 (base) 是选定的进制基数(mod) 是取模的模数。你可以这么理解一个字符串就像一个大数的十进制表示只不过每一位不再是 0~9而是字符的编码值每一位的权重由 (base) 决定。举个例子假设 (base10)字符串 abc 中 (a1,b2,c3)那么[ H(abc) 1 \times 10^2 2 \times 10^1 3 \times 10^0 123 ]看到了吧abc 在 (base10) 下就是一个普通的整数 123。那 bc 就是 (2 \times 10 3 23)。这样两个字符串判等就变成了两个整数判等时间一下子从 (O(L)) 降到了 (O(1))。但竞赛里字符串长度经常是 (10^5)、(10^6)进制数选 131 的话(131^{10^5}) 这个数是天文数字根本没有数据类型能装下。所以我们要引入取模操作把计算限制在一个相对固定的范围内。取模之后的整数值在 (0 \sim mod-1) 之间这就是“哈希值”。由于多个不同的字符串可能映射到同一个整数碰撞问题随之而来。这里我特别想强调一个容易踩的坑ord(s[i])直接取 ASCII 码的话字符集范围小碰撞概率会明显偏高。更稳的做法是把字符映射到一个比较宽的数值空间比如 (s[i] - a 1)或者干脆用 ASCII 码再加一个偏移量。原因是字符之间的区分度越大哈希值分布的“扩散性”就越好。2.2 为什么 base 选 131、13331mod 选 1e97这是每个学哈希的人都会问的问题为什么模板里的 base 总是 131、13331、23333333模数总是 1e97、1e99而不是 2、10、100先说模数。1e97 和 1e99 都是质数而且足够大能保证哈希值分布范围宽减少碰撞。更关键的是取模运算在计算机里是除法用任意模数时编译器会调用较慢的取模指令但因为这俩数接近 (2^{30})很多优化技巧都可以用不过竞赛选手用不用优化其实影响不大主要图的是质数身份和足够大的值域。再解释进制。base 选 131 而不是 2是因为基数太小的话字符串的“数字值”范围太窄不同字符串很容易在一个较小的值域里发生碰撞。比如 base2相当于二进制表示ab 和 ba 的数值分别是多少可能就撞得比较厉害。而 base 选一个比较大的质数相当于让字符串的“数字”分布得更散。131 刚好是质数而且经验上碰撞率很低。有人做过测试对于长度 (10^5) 的随机字符串单哈希用 base131、mod1e97碰撞概率大约是 (10^{-9}) 量级几乎可以忽略。但注意“几乎”竞赛里经常有人故意构造数据卡哈希这时单哈希就不安全了。双哈希就是把碰撞率再次平方降到 (10^{-18}) 级别这就是为什么很多进阶选手直接上双哈希。我个人的习惯是先判断题目数据范围和数据是否可被构造。如果是经典的竞赛题且没有针对哈希的构造数据单哈希配合 unsigned long long 自然溢出也够用但如果是大型比赛比如区域赛、省选级别我一般直接写双哈希省心代码也只多几十行。3. 滚动哈希与 O(1) 子串查询3.1 区间哈希是怎么“滚动”出来的刚才我们知道了整个字符串的哈希值怎么算但这还不够。竞赛里最常见的需求是给定字符串 (s)多次询问区间 ([l,r]) 的子串哈希。如果每次从 l 到 r 重新计算复杂度还是 (O(L))。滚动哈希就是利用前缀哈希的差分在 (O(1)) 时间内推出任意子串的哈希值。做法是预处理一个前缀哈希数组[ h[i] (h[i-1] \times base ord(s[i-1])) \bmod mod ]其中 (h[0] 0)(h[i]) 表示前 i 个字符的哈希值。同时预处理 (base) 的 k 次幂数组p[k]。有了这两个数组区间 ([l,r]) 的哈希值就是[ H(l,r) (h[r] - h[l-1] \times p[r-l1]) \bmod mod ]这个公式的含义是(h[r]) 是前 r 个字符的哈希值但它的末位对应的是第 r 个字符(h[l-1]) 是前 l-1 个字符的哈希值把它“左移” (r-l1) 位乘以 (p[r-l1])就变成了一个低位占位到 l-1 之前的数字。两者相减正好只剩下 (l) 到 (r) 这一段。一句话总结前缀哈希扣掉前缀的“高位影响”剩下的就是区间哈希。3.2 手写一个可以直接抄的模板下面给你一个我经常用的单哈希模板注释写得很详细方便你直接改。拿 C 写因为竞赛里它还是主流。#include bits/stdc.h using namespace std; const int N 100010; const int BASE 131; const int MOD 1000000007; unsigned long long h[N]; // 前缀哈希值 unsigned long long p[N]; // BASE 的幂次 // 预处理前缀哈希和幂次数组 void init(string s) { int n (int)s.size(); p[0] 1; for (int i 1; i n; i) { p[i] p[i-1] * BASE; // 不用取模unsigned long long 自然溢出 h[i] h[i-1] * BASE (s[i-1] - a 1); // 字符映射到 1~26 } } // 查询区间 [l, r] 的哈希值注意 l、r 从 1 开始 unsigned long long getHash(int l, int r) { return h[r] - h[l-1] * p[r-l1]; }你可能注意到这里用了unsigned long long自然溢出取模。这个技巧的关键点在于无符号整数的溢出行为在 C 标准里就是取模 (2^{64})所以省掉了显式的% mod常数小很多。但代价是模数为 (2^{64})不是质数碰撞概率比质数模数稍高。使用的时候getHash(l, r)的返回值虽然是一个很大的数但判等只需要getHash(l1, r1) getHash(l2, r2)。注意h[r] - h[l-1] * p[r-l1]这里用的是无符号减法如果出现负数会自动溢出回绕但因为我们所有运算都在同一模系下所以结果依然是正确的区间哈希。双哈希就是多开一组h2、p2用两个不同的模数比如 1e97 和 1e99判等时两个哈希值都相等才算相同。代码我就不贴了在你理解单哈希之后扩展双哈希只是复制粘贴的问题。4. 进阶应用场景与变形技巧4.1 用哈希快速求最长回文子串一个非常经典的问题给你一个字符串求最长回文子串。常规解法有 Manacher 算法写起来稍复杂但其实是 (O(n))。那用哈希怎么做呢思路是枚举回文中心然后用二分 哈希判断左右两边是否相等。对于奇回文中心就是某个字符对于偶回文中心是两个字符之间。判断左侧区间和右侧区间是否互为逆序只需要预处理正向哈希和反向哈希然后 O(1) 取区间哈希并比较。具体步骤预处理正向哈希h和反向哈希rh。二分答案长度 L对每个可能的中心取左右两侧长度 L 的区间哈希正向哈希取左边反向哈希取右边注意反向哈希的下标变换两边相等则是回文。复杂度是 (O(n \log n))。虽然比 Manacher 的 (O(n)) 慢但哈希的代码量小、思路直观而且能轻松扩展到“回文串中可修改字符”的动态场景。竞赛里如果题目没有卡这个 (\log)哈希解法常常是我的首选。这里有一个小坑反向哈希的下标处理。反向哈希里 (i) 对应的是原串从右往左数的第 (i) 个位置。如果你直接用正向的区间计算方式去处理反向很容易把下标弄混。我的经验是先在纸上写出正向和反向的对应关系再写代码不要凭感觉。4.2 从判等延展出去匹配、循环节、二维哈希字符串哈希不只能判两个子串是否相等它还能解决很多看起来不太相关的题目。第一个场景是字符串匹配。KMP 能在线性时间里解决模式串匹配但如果你需要处理“两个字符串中所有相等子串”的枚举哈希就很有用。比如求两个字符串的最长公共子串可以二分长度然后匹配所有等长子串的哈希值。思路一样二分长度 L把所有 (s1) 中长度为 L 的子串哈希值放进 set再枚举 (s2) 中的子串哈希看是否存在。第二个场景是循环节判断。判断一个字符串是否有长度为 k 的循环节只需要检查所有间距为 k 的子串哈希是否相等。这个操作如果用 KMP 的 fail 数组也能做但哈希更能扩展到多字符串之间。第三个场景是二维哈希。二维矩阵里的子矩阵相等判断可以先用行哈希对每一行做一维哈希再对结果按列做一次哈希从而得到一个二维哈希值。查询子矩阵相等就是两个二维哈希值的比较。这在高频考题“矩阵中子矩阵匹配”里非常实用。从这些扩展你会看到字符串哈希本质上是一个“降维工具”它能把你想要比较的对象压缩成一个整数而整数之间的比较、排序、存储都极其高效。这也是哈希能融入图论状态压缩、树论树上哈希、几何网格哈希等各种领域的原因。4.3 哈希与其它字符串算法的取舍写到这里我想顺便聊一下哈希和 KMP、后缀数组的选型问题因为很多初学者会纠结“学了哈希是不是就不用学其他字符串算法了”。我的看法是如果题目明确要求线性复杂度比如 (10^7) 级别字符串的匹配KMP 是更稳的选择因为哈希的碰撞虽然概率低但万一被构造数据卡掉就是 0 分。如果题目要求求排名第 k 的小串、求所有后缀的字典序排序后缀数组或者其他后缀结构是绕不开的。哈希在这里只能辅助比如配合二分求两个后缀的最长公共前缀。如果题目只是做“若干次判等”哈希的代码量和思维复杂度最低性价比最高。哈希是一门“用概率换效率”的手艺它不是万能解药。我见过不少选手只会哈希遇到 KMP 模板题也能用哈希硬做但遇到数据范围大一点、时间严格一点就会很被动。我的建议是哈希一定要会但 KMP 和 Tire 树这类确定性算法也要掌握多一把钥匙总没坏处。5. 那些坑自然溢出、卡哈希与实战排查5.1 自然溢出到底能不能用先说结论能用但要分场景。自然溢出unsigned long long最大优势是快省掉取模指令。在我自己跑过的多次对比里自然溢出比用% MOD的版本至少快 20%~30%。如果你随便刷题、或者数据是随机生成的自然溢出完全足够。但自然溢出有一个隐患模数是 (2^{64})在数学上不是质数所以存在一些“看起来很不随机”的字符串组合会让哈希碰撞概率升高。更严重的是有选手做过针对性构造利用模数 (2^{64}) 的约数关系把两个不同字符串构造成哈希值相同的例子。这在大型比赛里是真实发生过的比如著名的“卡哈希”事件所以遇到面向全网的公开赛我会天然倾向双哈希 大质数模数。权衡方法很简单看数据是否可能是构造的。如果是交互题、Codeforces 这类极其容易被人构造数据的地方默认使用双哈希如果是日常练习或者校内比赛自然溢出一个质数模数也够用。5.2 双哈希和随机化基数的得失双哈希就是把正确率提高一个量级代价是常数加倍、代码长度变长。很多网上的模板是两个 mod 都是 1e9 级别的质数两个 base 都是 131、13331。其实这种做法只是“经验配置”并不是唯一答案。我个人喜欢第二个模数用 998244353一个常见 NTT 模数因为它在很多比赛里出现过而且质数性质很好。base 的选择上有人会随机化 base防止被构造数据的选手提前猜到进制。实现方法是base chrono::steady_clock::now().time_since_epoch().count(); % 100000000 131;当然随机化 base 也会带来一个问题如果程序在多次运行中 base 改变你的哈希结果只在单次运行内一致不能在多次运行之间做持久化比较。竞赛里这么做没问题但如果你写工程代码要注意这个细节。判断是否值得双哈希我的标准很朴素的如果这个题目数据范围在 (10^5) 级常数敏感度不高我直接双哈希如果题目要求极端常数优化比如 (10^6) 且要跑很多次我可能退回到自然溢出单哈希并且承担可接受的风险。5.3 常见错误速查表这里把我在教学和实战中看到的典型错误整理成一张表你可以直接收藏。错误类型原因分析解决方案区间哈希计算错误l-1前缀乘的幂次算错牢记长度是r-l1乘p[r-l1]字符映射为 0直接s[i] - a导致a映射为 0改成s[i] - a 1避免前导零歧义自然溢出哈希相加h[i-1] * base val溢出成负数用unsigned long long承接中间结果下标从 0 开始搞混前缀哈希习惯从 1 开始初始化h[0]0下标严格 1-based双哈希判等只判断一个哈希两个哈希值必须同时相等用 pair 或两个变量一并比较幂次数组忘记预处理p[i]没有计算到 n预处理到字符串长度 n二分哈希时边界错误区间长度和边界 l、r 混乱每次二分时在纸上推导左右区间这个表里最容易被忽略的是“字符映射为 0”。如果你把a映射成 0那么 ab 的哈希值其实是 b 的哈希值因为前导 0 不体现。这种错误极难排查因为大部分随机字符串都能过只有极少数用例会暴露。所以我建议所有字符映射都从 1 开始从根上规避这个问题。5.4 一个完整的实战排查流程最后我分享一个真实调 bug 的经历。某次模拟赛我写了一个最长公共子串的哈希解法结果输出始终比标准答案大一点。当时我排查了二十分钟步骤是这样的先用小样例目测。固定长度 L2打印出每个子串的哈希值和实际字符串发现哈希值相同但字符串不同——说明碰撞。单哈希碰撞我以为是 base 或 mod 的问题换成双哈希发现碰撞没了但答案还是不对。再打印每个候选位置发现有些子串在getHash中的区间取反了左边区间我取的是[i, iL-1]右边取的是[j-L1, j]但 j 本身计算有误导致两个区间并不是对称的。修正下标后答案正确。这次调式教给我的教训是哈希本身很少出错出错的多半是区间边界计算。你只要把l、r、长度 L三者关系在纸上列清楚再写代码就能少走很多弯路。最后分享一点个人经验做了这么多年题我越来越觉得字符串哈希是一个“易学难精”的算法。入门只要一小时但真正运用自如需要踩过很多构造数据的坑、打过很多场被卡哈希的比赛才能形成自己的模板习惯和风险意识。我的建议是先背一套标准双哈希模板把它用到滚瓜烂熟然后针对不同的题目场景学会在自然溢出、双哈希、随机化基数之间做出取舍。哈希不是银弹但懂得它的人能在很多看起来完全不像字符串的题目里发现哈希的影子——这才是这个算法最迷人的地方。
阅读完成 · 觉得有帮助？
