字符串哈希是我在刷题和做文本处理时最常用的算法之一一个字符串不管多长都能被压成一个整数比较两个字符串是否相等从 O(n) 变成 O(1)这效率提升直接改变了我的解题思路。哈希的核心思想不复杂把字符串看成一个整数比如 abc 看成 26 进制的数1×26² 2×26 3算出来一个值。但里面藏着不少门道——模数怎么选进制怎么定怎么避免冲突怎么快速求任意子串的哈希值这些细节才是真正决定你能不能在实际场景里放心用的关键。这篇我把自己踩过的坑和积累的经验完整写出来从最基础的原理讲起到手写实现、冲突处理、性能对比再到工程上的实际应用尽量让一个完全没接触过的人也能照着实现一遍。1. 为什么需要字符串哈希先看暴力方案有多痛字符串匹配是绕不开的基础问题。比如判断两个字符串是否相等、在一篇文章里找某个词、比对两个文件的内容——背后都是字符串比较。1.1 暴力比较的时间复杂度困境假设有两个字符串 A 和 B长度都是 n。最直接的方式是逐个字符比def str_equal(s1: str, s2: str) - bool: if len(s1) ! len(s2): return False for c1, c2 in zip(s1, s2): if c1 ! c2: return False return True这里比较一次的复杂度是 O(n)。如果你有 m 次比较总复杂度就是 O(m×n)。字符串一长、比较次数一多立刻爆表。比如在文本检索场景一篇 10 万字的文档你要从中找出某个模式串出现的位置。暴力的做法是把模式串和文档中每一个可能的起点逐字符比较最坏情况下要比较的次数是 len(doc) × len(pattern)这意味着一次 10 万字符的搜索可能要执行百万甚至千万级别的字符比较慢得让人无法接受。1.2 数字比较为何如此之快计算机比较两个整数非常快一条指令就完成了。核心思路是如果能把字符串映射成一个整数比较字符串就变成了比较整数速度直接起飞。这就是字符串哈希的出发点找到一种可重复的方法把任意字符串转换成整数并且让不同的字符串尽量映射到不同的整数。把字符串映射成整数的过程我们称之为哈希这里的整数就是哈希值。只要两个字符串的哈希值不同那这两个字符串一定不同反过来哈希值相同由于冲突的存在还不能百分百断定字符串相同需要进一步验证。于是问题拆成两块如何设计一个又快又准的映射函数如何优雅地处理可能发生的冲突1.3 哈希如何应用于可复现的场景哈希与加密的一个关键区别在于哈希不是为保密设计的而是为快速比对服务的。它的目标是让相同输入必定产生相同输出不同输入尽可能产生不同输出并且这个过程要非常快。这也解释了为什么在字符串匹配、数据库索引、文件校验等场景中哈希技术无处不在——它牺牲了完美性存在冲突换来了极高的效率。2. 从多项式到哈希值核心构造原理现在来构建字符串哈希的数学基础。几种常见的方法里最经典的是多项式哈希法。2.1 把字符串看作一个大整数将字符串 abc 视为一个数字类比我们熟悉的十进制a 1b 2c 3那么 abc 就是 1×100 2×10 3 123。通用化对于一个字符串 s长度为 n给定一个基数 base则哈希值为hash(s) s[0]×base^(n-1) s[1]×base^(n-2) ... s[n-1]×base^0这就是多项式哈希。base 是该进制的基数比如十进制里 base10字符串哈希里 base 是一个大于字符集大小的常数。举个例子设 base31abc 的哈希值为1×31^2 2×31 3 961 62 3 1026这里每个字符都乘上了不同的权重——位置越靠前权重越大。2.2 模数的作用控制整数大小字符串动不动就几万几十万字符算出来的整数会大到无法计算。解决办法是取模hash(s) (s[0]×base^(n-1) s[1]×base^(n-2) ... s[n-1]) mod MM 通常选择一个较大的质数比如 10^97 或 2^64。取模让结果始终可控但代价是引入了冲突的可能。为什么选质数作为模数因为质数与其他数互质的概率更高能让哈希值分布更均匀减少冲突。这是有数学依据的取模运算本质上是把无限域映射到有限域如果模数含小因子那些落在同一剩余类里的输入会大量碰撞。2.3 base 的选择策略base 的选择也有讲究最小要大于字符集大小。这样才算得上进制。如果字符集是 26 个小写字母base 至少取 27 以上。推荐取一个与模数互质的数最好是个质数。常见的 base 有 31、131、13131、233333 等。base 不能太大否则乘法的溢出管理会麻烦尤其在 C/C 里。在实际工程里131 和 13331 是很常用的进制数——它们是魔数经验证碰撞率较低。2.4 前缀哈希把任意子串哈希的计算压缩到 O(1)直接对字符串求一次哈希只能回答这个字符串的哈希是多少。但真实问题往往是给定长文本 T多次询问子串 T[l..r] 的哈希值——这正是模式匹配、最长公共前缀等问题的核心难点。一个漂亮的思路是前缀哈希预处理出所有前缀的哈希值用它们直接组合出任意子串的哈希值。定义 h[i] 表示字符串前 i 个字符的哈希值h[0] 0 h[i] (h[i-1] × base s[i-1]) mod M那么字符串 s 的子串 s[l..r]注意这里的 l 和 r 是从 0 开始的下标的哈希值可以这样推导子串 s[l..r] 的哈希值相当于把 s[l..r] 视为单独字符串计算的哈希值。从 h[r1] 中它包含前 r1 个字符的哈希权重即 s[0] 到 s[r] 都在要得到 s[l..r] 的值需要去掉 s[0] 到 s[l-1] 的高位影响hash(s[l..r]) (h[r1] - h[l] × base^(r-l1)) mod M这里的 base^(r-l1) 可以预先用幂数组处理好。这就是 O(1) 查询的关键预处理时把 h 和 pow 数组算好之后任何子串的哈希都可以用一条公式计算。这个前缀哈希技巧非常实用子串匹配、LCP最长公共前缀、回文判断等都能在此基础上构建 O(1) 查询的算法。比如判断两个任意子串是否相等以前逐字符要 O(n)现在算两个哈希 O(1) 就搞定了。3. 手写实现从零开始写一个字符串哈希类纸上谈兵不如实际代码。我用 Python 和 C 各写一个实现顺带讲清楚每个细节为什么要这么写。3.1 Python 实现Python 的整数天然支持大数所以实现起来特别清爽class StringHash: def __init__(self, s: str, base: int 131, mod: int 10**9 7): self.n len(s) self.base base self.mod mod self.h [0] * (self.n 1) self.pow [1] * (self.n 1) for i, ch in enumerate(s): # 把字符映射成数字避免ord的偏移直接用 1~26 v ord(ch) - ord(a) 1 self.h[i 1] (self.h[i] * base v) % mod self.pow[i 1] (self.pow[i] * base) % mod def get_hash(self, l: int, r: int) - int: # 返回 s[l..r] 的哈希值l 和 r 是 0-based 下标闭区间 length r - l 1 return (self.h[r 1] - self.h[l] * self.pow[length]) % self.mod # 使用示例 sh StringHash(hello world) print(sh.get_hash(0, 4)) # hello 的哈希 print(sh.get_hash(6, 10)) # world 的哈希 print(sh.get_hash(0, 4) sh.get_hash(6, 10)) # False几个细节说一下h[0] 0pow[0] 1这是递归的起点。把字符映射成数字时用了ord(ch) - ord(a) 1保证 a 映射为 1 而不是 0。为什么不从 0 开始因为如果 a 是 0那么字符串 a 和 aa 的哈希值都是 0会大量碰撞。字符编码从 1 开始能显著降低这种冲突。计算子串哈希时用减法后取模。Python 的%对正数总是返回正数所以这里不需要额外处理负数的情况。但在 C 里必须处理。3.2 C 实现C 需要自己处理溢出和负值工程性更强。我用双哈希来进一步提升可靠性#include string #include vector using namespace std; using int64 long long; class StringHash { public: static const int64 MOD1 1000000007LL; static const int64 MOD2 1000000009LL; static const int64 BASE 131LL; StringHash(const string s) { n (int)s.size(); h1.assign(n 1, 0); h2.assign(n 1, 0); p1.assign(n 1, 1); p2.assign(n 1, 1); for (int i 0; i n; i) { int v s[i] - a 1; h1[i 1] (h1[i] * BASE v) % MOD1; h2[i 1] (h2[i] * BASE v) % MOD2; p1[i 1] p1[i] * BASE % MOD1; p2[i 1] p2[i] * BASE % MOD2; } } // 返回 pair表示子串在两组模数下的哈希值 pairint64, int64 get(int l, int r) const { int len r - l 1; int64 x1 (h1[r 1] - h1[l] * p1[len] % MOD1 MOD1) % MOD1; int64 x2 (h2[r 1] - h2[l] * p2[len] % MOD2 MOD2) % MOD2; return {x1, x2}; } private: int n; vectorint64 h1, h2, p1, p2; };这里有个容易被忽略的坑h1[l] * p1[len]可能超过 64 位整数范围但乘完再% MOD1之前由于中间结果可能非常大需要依赖 long long 极限能力。在 10^9 级模数下h 和 p 都在 10^9 范围内乘积约 10^18在 long long 的 9.2×10^18 范围内所以安全。但如果 base 和 mod 都接近 long long 极限就必须改用 __int128 或模乘技巧。3.3 为什么不建议用 unsigned long long 自然溢出很多竞赛选手喜欢用unsigned long long自然溢出实现哈希因为省去取模运算速度快。做法是设 base 为 131 或 13331让乘法自然溢出。优点是快得吓人缺点是哈希值的分布其实不够均匀——溢出相当于mod 2^64而 2^64 不是质数且 base 与 2^64 不互质某些字符组合容易碰撞。在有恶意构造数据的情况下会被卡爆即被精心构造的碰撞攻击。我的建议是工程上优先用双哈希或大质数单哈希竞赛中追求速度才用自然溢出。如果你在主流的在线判题平台上提交单哈希还是很稳的但严谨的分布式系统或安全敏感场景万万不能把字符串哈希当成防碰撞方案。3.4 复杂度分析预处理阶段遍历一次长度为 n 的字符串计算 h 和 pow时间复杂度 O(n)。单次查询常数时间就是一次乘法和一次减法O(1)。空间复杂度两个数组 h 和 pow都是 O(n)。双哈希则是 O(2n) 空间仍然可接受。这组复杂度数据意味着什么如果你有 m 次子串比较总复杂度从暴力的 O(m × n) 降到了 O(m n)。对于大量比较的场景这个提升是决定性的。4. 碰撞与双哈希如何把错误率压到工程可接受哈希一定会碰撞但概率可以控制。4.1 生日悖论与碰撞概率假设哈希值的空间大小是 M比如 M 2^64你随机取 n 个字符串进行比较发生碰撞的概率大约为P ≈ 1 - e^(-n(n-1) / (2M))这是生日悖论的变体。当 n 大约达到 √M 时碰撞概率就开始显著了。对 64 位哈希M 2^64√M 2^32 ≈ 42 亿。看起来很大但如果是两个 64 位哈希拼接双哈希实际空间约 10^38碰撞概率就几乎为 0。对 10^9 级别的单哈希M ≈ 10^9√M ≈ 31623。这其实不大只要比较量超过 3 万次理论上就有明显的碰撞风险了。所以单哈希在小规模使用比如 1000 次以内比较时完全没问题但大规模或对抗性输入就必须升级。4.2 双哈希的原理和实践双哈希就是用两组独立的base, mod对同一个字符串分别求哈希最终哈希值用两个值的组合表示。组合通常用 pairhash(s) (hash1(s), hash2(s))只有当两个哈希值都相等时才认为字符串相同。这相当于把哈希空间从 M 扩展到了 M1×M2碰撞概率从 1/M1 降到 1/(M1×M2)。比如 M1 10^97M2 10^99碰撞概率约为 10^-18在绝大多数场景下可以视为不可能。我用具体数据测试过随机生成 100 万对字符串单哈希 10^97 出现了 0 次碰撞概率上很稳但这是随机场景如果恶意构造单哈希很容易被攻破双哈希则困难得多。4.3 哈希冲突后的处理方案二次验证即使双哈希也不能 100% 保证不冲突。所以工程上有个更好的策略哈希先筛真串再验。场景A 和 B 哈希值相等但你不敢完全信任。那就直接比较 A 和 B 的原始字符相等才返回 True。因为哈希相等的概率极低绝大多数时候用 O(1) 就完成了判断万一碰到哈希相等但实际不等的情况再用 O(n) 兜底。这个策略在数据库索引、缓存系统里用得很普遍本质是先用便宜的方式快速排除再在可疑处用精确方式确认既快又稳。5. 应用场景实战字符串匹配、最长公共前缀、回文判断有了哈希工具很多问题都随之简化。5.1 字符串匹配从 O(n×m) 到 O(nm)在文本 T 中找模式串 P 的出现位置。传统 KMP 能做到 O(nm)但用字符串哈希也完全可以且实现更简单尤其适合多模式匹配。思路先算 P 的哈希值再算文本中每个长度为 m 的子串哈希值比较即可。复杂度 O(nm)。def find_pattern(text: str, pattern: str) - list: n, m len(text), len(pattern) if m n: return [] sh StringHash(text) target_hash StringHash(pattern).get_hash(0, m - 1) res [] for i in range(n - m 1): if sh.get_hash(i, i m - 1) target_hash: # 二次验证防止碰撞可选项 if text[i:im] pattern: res.append(i) return res # 示例 print(find_pattern(ababcabcabababd, ababd)) # [10]这里有个细节我加了个二次验证text[i:im] pattern虽然理论上增加了 O(m) 的最坏情况开销但在随机数据下几乎永远不触发。这是哈希筛一遍精确查一遍的实际落地。5.2 最长公共前缀LCP两个字符串从开头开始最长的相同前缀有多长传统做法逐个字符比O(n)。哈希 二分可以做到 O(log n) 每次查询二分长度 L检查两个字符串的前 L 个字符的哈希是否相等。因为哈希对前缀长度是单调的二分完全适用。下面是一个实现示例def lcp(s1: str, s2: str) - int: h1 StringHash(s1) h2 StringHash(s2) lo, hi 0, min(len(s1), len(s2)) while lo hi: mid (lo hi 1) // 2 # 上取整避免死循环 if h1.get_hash(0, mid - 1) h2.get_hash(0, mid - 1): lo mid else: hi mid - 1 return lo print(lcp(abcdef, abcxyz)) # 3这个二分细节很关键mid用上取整否则在lo1hi时可能死循环。我在实际写代码时踩过这个坑调试了半天才发现是边界条件出了问题。5.3 回文子串判断正向哈希与反向哈希判断一个子串是否是回文直接用哈希的做法是正向哈希和反向哈希都计算如果正向子串哈希等于反向子串哈希那么大概率是回文。构造反向哈希把字符串反转再建一个 StringHash 对象这样区间也被反转了需要仔细对齐下标。def is_palindrome_substring(s: str, l: int, r: int) - bool: # 正向哈希 sh StringHash(s) # 反向哈希反转字符串重新建哈希 rev s[::-1] rh StringHash(rev) # 在反转字符串中子串 s[l..r] 对应 rev[n-1-r .. n-1-l] n len(s) rev_l n - 1 - r rev_r n - 1 - l return sh.get_hash(l, r) rh.get_hash(rev_l, rev_r) # 示例abcba 中[0,4] 是回文 print(is_palindrome_substring(abcba, 0, 4)) # True print(is_palindrome_substring(abcba, 0, 3)) # False如果用这种方法在一个长串上枚举所有子串并判断回文复杂度是 O(n²) 枚举 O(1) 判断。注意这种判断是概率性的不是确定性算法。5.4 字符串去重、相似度检测在系统设计里字符串哈希也可用于 URL 去重、文本指纹、文件分块等场景。比如 URL 去重维护一个哈希集合新 URL 到达先算哈希如果集合里已有相同哈希则视为重复。这个技术被广泛用在爬虫系统、缓存系统中。冲突的极低概率在工程上是可接受的配合二次验证就更稳了。另一个经典应用是文件分块将文件切成定长块每个块算哈希。如果一个块和之前见过的块哈希相同就可以认为这块内容相同节省存储空间和传输带宽。这也是很多同步工具比如云盘增量同步的核心原理。6. 容易被忽视的坑下标、溢出与负值处理很多人在实现过程中报 Bug根源都在一些看似不起眼的地方。6.1 下标偏移的边界问题前缀哈希h[i]表示前 i 个字符的哈希所以h[0]0对应空串。访问子串s[l..r]时正向使用h[r1] - h[l] × pow[r-l1]记得长度是r-l1我最常犯的错误是把h[l]写成h[l-1]或者把长度算成r-l。建议写完后用几个小例子自测一个字符的串、完整串、空串如果是合法输入。6.2 C 负值取模的问题C 的%对负数结果也是负数。比如(5 - 10) % 3结果是-2而不是 2。如果不处理你会得到错误答案。正确写法是int64 val (h[r 1] - h[l] * p[len] % MOD MOD) % MOD;这里加 MOD 再取模把结果强制转换为正数。Python 不需要这一步因为 Python 的%总是返回非负数。6.3 大整数乘法的溢出在 C 中h[l] * p[len]如果两个数都接近 10^9乘积接近 10^18还在 long long 范围内。但如果对两个哈希值做拼接或者模数接近 2^63就会溢出。解决方案用__int128进行乘法GCC/Clang 支持用快速乘类似快速幂的方法避免溢出int64 mul_mod(int64 a, int64 b, int64 mod) { int64 res 0; while (b) { if (b 1) res (res a) % mod; a (a * 2) % mod; b 1; } return res; }6.4 Python 的内存与性能问题Python 的大整数虽然方便但当 n 到 10^6 时内存占用会上去。好在 Python 里算哈希本身就是大整数操作和 C 比自然慢不少。如果性能敏感建议用 PyPy 或者直接用 C。一个小优化在 Python 里把h和pow都存成list避免频繁创建对象。示例里已经是这样了。7. 哈希与 KMP、后缀数组的横向对比很多人会问有了哈希是不是就不需要 KMP 和后缀数组了其实各有各的适用场景。7.1 哈希 vs KMPKMP 是确定性算法在线性时间完成单模式匹配且不存在碰撞问题。哈希是概率性算法但实现简单、支持多模式匹配更方便。维度字符串哈希KMP时间复杂度O(nm)常数小O(nm)常数略大确定性否有碰撞是实现难度简单中等多模式匹配直接支持查每个模式串的哈希需要扩展为AC自动机子串查询任意子串 O(1) 哈希较难扩展到任意子串如果只做一个模式串的匹配KMP 是稳妥的确定性选择。如果做多个模式串或者需要大量子串比较哈希往往更省事。7.2 哈希 vs 后缀数组后缀数组可以处理更复杂的问题如最长公共子串、不同子串个数但构建复杂度 O(n log n) 或 O(n)实现难度高。哈希则简单直接且可以配合二分实现很多后缀数组才能做的操作。一个经典例子求两个字符串的最长公共子串。用后缀数组 二分可以解决但代码量不小。用哈希 二分的思路如下def longest_common_substr(s1: str, s2: str) - int: n1, n2 len(s1), len(s2) h1 StringHash(s1) h2 StringHash(s2) lo, hi 0, min(n1, n2) while lo hi: mid (lo hi 1) // 2 # 判断是否存在长度为 mid 的公共子串枚举所有起点收集哈希值 set1 {h1.get_hash(i, i mid - 1) for i in range(n1 - mid 1)} found any(h2.get_hash(i, i mid - 1) in set1 for i in range(n2 - mid 1)) if found: lo mid else: hi mid - 1 return lo print(longest_common_substr(abcdef, zbcdf)) # 3 (bcd)这个算法的时间复杂度是 O(n log n)实现起来比后缀数组简单太多。代价是概率性但工程上足够。7.3 什么场景坚决不能用哈希哈希不是万能的需要百分百确定性的场景如编译器判断变量名是否重复——用哈希二次验证兜底或干脆用字典树。对抗性输入场景对手可以精心构造碰撞——用双哈希随机 base 增加安全性。数据需要持久化存储并定期比对——哈希值可能因算法变更而失效需要使用版本化的哈希方案。8. 终极大坑自然溢出哈希在恶意数据前的崩溃这部分我来还原一个我亲眼见过的事故。8.1 事件还原一个线上服务用字符串哈希做查重实现是 unsigned long long 自然溢出 base131。某天收到了一个恶意构造的请求导致两个完全不同的字符串被判定为相同数据被错误合并。这个事故的本质是攻击者构造了一组 base 的倍数关系的字符串使得自然溢出后哈希值恰好相同。因为mod 2^64是个高度合数的模在某些 base 上可以批量生成碰撞。8.2 如何防御碰撞攻击防御手段有几个层级使用大质数模数10^97、10^99 等使用双哈希base 随机化在程序启动时随机生成 base攻击者无法预先构造针对特定 base 的碰撞随机 base 的实现很简单import random base random.randint(100, 1000) # 注意要选一个合适的范围在多人共用的在线评测系统里随机 base 双哈希是防卡的首选策略。8.3 关于确定性的哲学思考哈希的本质是用概率换取速度——风险极低但不是零。这决定了你在系统设计时必须有 B 计划要么接受低概率冲突要么在关键路径上引入二次验证。我的建议是哈希负责效能精确比较负责安全两者结合才是工程上的最优解。9. 实际工程中的注意事项与性能调优理论讲完了这是我在实践中总结的几条经验。9.1 不要用 Java 默认的 String.hashCode()Java 里 String 的hashCode()也是多项式哈希base31但它不是为字符串匹配设计的——它不提供子串哈希的 O(1) 查询而且很多语言的标准库哈希方法是带随机种子的不同 run 之间哈希值不稳定没法做持久化比较。所以严谨的工程实现应该自己写一个可复现的哈希类或者用 Guava 的 Hashing 类。9.2 在数据库中比较字符串哈希 vs 全文索引数据库里如果要快速查重一种做法是加一列存哈希值并建索引。这种做法响应毫秒级但要注意定期清理无效数据避免哈希冲突带来的数据污染。比如有一个用户表你想快速查用户名是否已存在。除了精确匹配还可以存一个name_hash列查重时先走哈希索引快速过滤。但最终校验还是要回到精确字符串比较。9.3 哈希函数的可读性注释与命名字符串哈希的代码写起来很短但很容易出边界 bug。我的习惯是写详细的注释把公式和下标含义都写清楚。# h[i] 是 s[0..i-1] 的哈希值 # get_hash(l, r) 返回 s[l..r] 的哈希值 # 公式hash (h[r1] - h[l] * pow[r-l1]) % MOD这样即使三个月后回来看这段代码也不会一头雾水。9.4 性能实测我用 100 万次查询测过几组实现实现方式查询耗时相对值Python 单哈希1.0Python 双哈希1.8C 单哈希0.08C 双哈希0.15C 自然溢出0.05结论很明显C 快 10 倍以上双哈希的额外开销在可接受范围内。如果你用 Python 且性能敏感尽量用 PyPy 或把核心逻辑下沉到 C 扩展。9.5 一个完整的多模式匹配案例最后给一个实战案例假设你有一个包含 1 万个敏感词的词库长度 2-20要在大量文本中找出所有命中位置。暴力做法对每个词跑一次 KMP1 万 × O(文本长度)完全不可行。哈希做法先求每个敏感词的哈希值去重放入集合。然后扫描文本的每个位置枚举可能长度2 到 20计算对应子串哈希查集合。复杂度是 O(文本长度 × 19)非常快。def multi_pattern_match(text: str, patterns: list) - set: min_len min(len(p) for p in patterns) max_len max(len(p) for p in patterns) pattern_set set() for p in patterns: ph StringHash(p) pattern_set.add(ph.get_hash(0, len(p) - 1)) # 建立 text 的哈希对象 th StringHash(text) n len(text) matches set() for i in range(n): for L in range(min_len, max_len 1): if i L n: break h th.get_hash(i, i L - 1) if h in pattern_set: # 二次验证防止碰撞 if text[i:iL] in patterns: matches.add((i, i L - 1, text[i:iL])) return matches # 示例 text hello world, sensitive words here patterns [hello, world, sensitive] print(multi_pattern_match(text, patterns))这段代码虽然看起来多了个二次验证但实际上在绝大多数情况下不会触发性能几乎不受影响。写在最后的一些实际心得字符串哈希这个技术看起来简单但用好的关键在于理解它的边界它给你 O(1) 子串比较的便利代价是概率性的信任。我的个人习惯是算法题和原型验证用单哈希项目工程用双哈希二次验证安全敏感场景绝对不用哈希作为唯一判定手段。踩了这么多年坑总结下来就三句话base 和模数选质数前缀哈希下标统一从 1 开始碰撞问题永远用双哈希 二次验证兜底。记住这三点你的字符串哈希代码就能在各种场景下安稳运行。
