一、从一个常见的烦恼说起
相信很多开发者朋友都遇到过这样的问题：给你一个很长的文本，比如一篇小说或者一个日志文件，然后又给你一小段文字，让你快速判断这一小段文字是否在那个长文本里出现过。最直接的想法，就是拿着小段文字，从长文本的开头一个字符一个字符地往后滑动比较，这个方法我们称之为“暴力匹配”。
这个方法简单直接，但效率上有点让人头疼。想象一下，如果你的长文本有100万个字符，小段文字有1000个字符，那么最坏情况下你需要比较大约100万次，每次比较可能还要对比最多1000个字符。这个计算量对于需要频繁查询的场景，比如搜索引擎或者文本编辑器里的查找功能，就显得太慢了。
那么，有没有一种方法，能让我们像查字典一样，给文本的每一段都编个“唯一”的号码（哈希值），然后我们只需要比较号码，就能知道两段文字是否相同呢？这就是我们今天要聊的“字符串哈希”，特别是其中一种强大又实用的方法——多项式哈希。它能让我们在绝大多数情况下，以O(1)的时间复杂度完成子串的匹配比较。
二、什么是多项式哈希？—— 给字符串上“身份证”
我们可以把字符串看成是一个由数字组成的序列。比如，字符‘a’对应数字1，‘b’对应2，以此类推（实际中我们常用字符的ASCII码）。多项式哈希的核心思想，就是把这个数字序列当作一个多项式的系数。
举个例子，字符串“abc”。我们假设‘a’=1, ‘b’=2, ‘c’=3。我们选择一个固定的“底数”，比如base = 131，和一个大的“模数”，比如mod = 1e9+7。
那么，“abc”的哈希值可以这样计算： hash(“abc”) = (‘a’ * base² + ‘b’ * base¹ + ‘c’ * base⁰） % mod = (1 * 131² + 2 * 131¹ + 3 * 131⁰） % mod = (17161 + 262 + 3） % mod = 17426 % mod
看，我们得到了一个数字17426。这个数字，在理想情况下，就可以看作是“abc”这个字符串的“身份证号”。只要计算方式固定，同一个字符串算出来的这个号码就是固定的。
技术栈：Python 3
def simple_hash(s, base=131, mod=10**9+7):
"""
计算一个字符串的简单多项式哈希值。
参数:
s: 输入字符串
base: 多项式的底数（通常取质数）
mod: 取模的大质数，防止溢出
返回:
字符串s的哈希值
"""
hash_value = 0
for char in s:
# 将字符转换为其ASCII码值作为系数
# 每次循环相当于将之前的哈希值左移一位（乘以base），然后加上新的字符
hash_value = (hash_value * base + ord(char)) % mod
return hash_value
# 示例
text = "algorithm"
hash_result = simple_hash(text)
print(f"字符串 '{text}' 的哈希值是: {hash_result}")
# 输出类似：字符串 'algorithm' 的哈希值是: 947441683
三、如何实现O(1)的子串匹配？—— 前缀哈希的魔法
只计算整个字符串的哈希值，对我们匹配子串帮助不大。真正的魔法在于“前缀哈希”数组。
我们预先计算出原字符串S每个前缀的哈希值，并存储在一个数组H里。H[i]表示字符串S从开头到第i个字符（假设下标从1开始）这个前缀的哈希值。
技术栈：Python 3
def compute_prefix_hashes(s, base=131, mod=10**9+7):
"""
计算字符串所有前缀的哈希值。
参数:
s: 输入字符串
base, mod: 同前
返回:
h: 列表，h[i] 表示 s[0:i] 的哈希值 (i个字符)
p: 列表，p[i] 存储 base^i 的值，用于后续计算
"""
n = len(s)
h = [0] * (n + 1) # 多一位，h[0]表示空串哈希，通常为0
p = [1] * (n + 1) # p[0] = base^0 = 1
for i in range(1, n + 1):
# 递推计算前缀哈希：H[i] = (H[i-1] * base + S[i]) % mod
h[i] = (h[i-1] * base + ord(s[i-1])) % mod
# 同时计算base的幂次
p[i] = (p[i-1] * base) % mod
return h, p
# 示例：计算字符串"banana"的前缀哈希
s = "banana"
h, p = compute_prefix_hashes(s)
print("前缀哈希数组h:", h)
print("幂次数组p:", p)
有了前缀哈希数组h和幂次数组p，我们就可以像做加减法一样，在O(1)时间内得到任意子串的哈希值！
公式如下：
对于字符串S，子串 S[l: r]（左闭右开区间，从0开始计数，包含第l个字符到第r-1个字符）的哈希值为：
hash(S[l: r]) = (h[r] - h[l] * p[r-l] % mod + mod) % mod
这个公式怎么理解呢？h[r]代表了从开头到r的哈希值，它相当于一个“大数”。h[l]代表了从开头到l的哈希值。我们想要l到r这段，就需要把h[r]中开头到l的那部分“减去”。但是因为哈希计算是乘以base的，h[l]在h[r]中已经被乘了(r-l)次base，所以要减去h[l] * p[r-l]。最后取模确保结果是正数。
技术栈：Python 3
def get_substring_hash(l, r, h, p, mod=10**9+7):
"""
通过前缀哈希数组，在O(1)时间内获取任意子串的哈希值。
参数:
l: 子串起始索引（从0开始）
r: 子串结束索引（从0开始，取到r-1）
h: 前缀哈希数组
p: 幂次数组
mod: 取模数
返回:
子串 s[l:r] 的哈希值
"""
# 公式：hash(s[l:r]) = (h[r] - h[l] * p[r-l] % mod + mod) % mod
return (h[r] - h[l] * p[r - l] % mod + mod) % mod
# 示例：验证"banana"中不同位置的"ana"哈希值是否相同
s = "banana"
h, p = compute_prefix_hashes(s)
# 获取子串 s[1:4] 即 "ana" (第一个ana)
hash_ana1 = get_substring_hash(1, 4, h, p)
# 获取子串 s[3:6] 即 "ana" (第二个ana)
hash_ana2 = get_substring_hash(3, 6, h, p)
print(f"第一个 'ana' (索引1-4) 的哈希值: {hash_ana1}")
print(f"第二个 'ana' (索引3-6) 的哈希值: {hash_ana2}")
print(f"哈希值是否相等? {hash_ana1 == hash_ana2}") # 输出应为 True
四、一个完整的示例：在文本中查找模式串
现在，让我们把上面的知识用起来，解决开头提出的问题：在一个长文本text中，查找一个模式串pattern是否出现。
技术栈：Python 3
def rabin_karp_search(text, pattern):
"""
使用Rabin-Karp算法（基于多项式哈希）查找模式串在文本中的位置。
参数:
text: 主文本字符串
pattern: 要查找的模式字符串
返回:
一个列表，包含所有匹配到的起始索引
"""
n, m = len(text), len(pattern)
if m == 0 or n < m:
return []
base = 131
mod = 10**9 + 7
# 1. 计算模式串的哈希值
pattern_hash = simple_hash(pattern, base, mod)
# 2. 计算文本的前缀哈希
h, p = compute_prefix_hashes(text, base, mod)
matches = []
# 3. 遍历文本中所有可能的长度为m的子串
for i in range(n - m + 1):
# 计算当前文本子串 text[i:i+m] 的哈希值
text_sub_hash = get_substring_hash(i, i + m, h, p, mod)
# 4. 比较哈希值
if text_sub_hash == pattern_hash:
# 注意：哈希值相等可能存在巧合（哈希冲突），需要再次验证字符是否真的一致
# 这一步对于保证绝对正确是必要的，但在很多算法竞赛或低冲突率场景下可省略以提高速度
if text[i:i+m] == pattern:
matches.append(i)
return matches
# 综合示例
def main():
# 场景：在一段技术博客中查找关键词
blog_text = """
字符串哈希是一种高效的字符串处理技术，特别是多项式哈希。
它允许我们在常数时间内比较任意两个子串是否相等。
这项技术广泛应用于字符串匹配、最长回文子串查找等领域。
多项式哈希的核心是选择一个合适的底数和模数。
"""
keyword = "哈希"
print(f"在文本中查找关键词: '{keyword}'")
print("-" * 40)
positions = rabin_karp_search(blog_text, keyword)
if positions:
print(f"找到 {len(positions)} 处匹配:")
for idx in positions:
# 打印匹配位置及上下文
start = max(0, idx - 10)
end = min(len(blog_text), idx + len(keyword) + 10)
context = blog_text[start:end].replace('\n', ' ')
print(f" 位置 {idx}: ...{context}...")
else:
print("未找到匹配。")
if __name__ == "__main__":
main()
五、深入理解：关联技术与细节
为了让哈希更可靠，我们常常会用到“双哈希”甚至“多哈希”技术。简单说，就是用两套不同的(base, mod)参数分别计算哈希值。只有当两个哈希值都相等时，我们才认为字符串相等。这就像给字符串上了双重保险，能极大降低哈希冲突（两个不同的字符串算出相同哈希值）的概率。
技术栈：Python 3
class DoubleHash:
"""一个简单的双哈希类，用于极大降低冲突概率。"""
def __init__(self):
# 使用两对不同的质数作为(base, mod)
self.base1, self.mod1 = 131, 1000000007
self.base2, self.mod2 = 137, 1000000009
self.p1, self.p2 = None, None
def preprocess(self, s):
"""预处理字符串，计算两套前缀哈希和幂次。"""
n = len(s)
self.h1 = [0] * (n + 1)
self.h2 = [0] * (n + 1)
self.p1 = [1] * (n + 1)
self.p2 = [1] * (n + 1)
for i in range(1, n + 1):
self.h1[i] = (self.h1[i-1] * self.base1 + ord(s[i-1])) % self.mod1
self.h2[i] = (self.h2[i-1] * self.base2 + ord(s[i-1])) % self.mod2
self.p1[i] = (self.p1[i-1] * self.base1) % self.mod1
self.p2[i] = (self.p2[i-1] * self.base2) % self.mod2
def get_hash_pair(self, l, r):
"""获取子串的两个哈希值 (hash1, hash2)。"""
hash1 = (self.h1[r] - self.h1[l] * self.p1[r-l] % self.mod1 + self.mod1) % self.mod1
hash2 = (self.h2[r] - self.h2[l] * self.p2[r-l] % self.mod2 + self.mod2) % self.mod2
return (hash1, hash2)
# 示例：演示双哈希如何区分极相似的字符串
dh = DoubleHash()
s = "apple"
dh.preprocess(s)
# 计算"apple"和假设的另一个字符串"applf"的哈希（我们手动模拟冲突场景）
# 假设单哈希系统下，'e'(101)和'f'(102)在某个模数下导致哈希相同
print("双哈希示例：")
print("字符串 'apple' 子串(0,5)的双哈希值:", dh.get_hash_pair(0, 5))
# 如果我们改变最后一个字符，双哈希值几乎不可能仍然同时相等
# 这演示了双哈希如何提供更强的唯一性保证。
六、应用场景：不止于匹配
字符串哈希的用途非常广泛：
- 快速字符串匹配：正如上面的Rabin-Karp算法，是它的经典应用。
- 判断回文串：可以同时计算原串和反串的哈希，快速判断任意子串是否是回文。
- 最长重复子串查找：结合二分搜索，可以高效找到字符串中最长重复出现的子串。
- 字符串比较与字典序：通过二分查找两个字符串的最长公共前缀(LCP)，可以在O(log n)时间内比较任意两个子串的字典序。
- 文件或数据块去重：将文件内容视为字符串，计算其哈希值，用于快速判断内容是否重复。
七、技术的优点与缺点
优点：
- 极高的查询效率：一旦完成O(n)的预处理，后续任何子串的哈希值获取和比较都是O(1)时间。
- 强大的灵活性：可以比较任意位置的子串，而不仅仅是开头对齐的字符串。
- 易于实现：核心算法只需十几行代码，容易理解和集成。
- 空间效率高：只需要存储前缀哈希数组和幂次数组，空间复杂度为O(n)。
缺点与注意事项：
- 哈希冲突：这是理论上的最大缺点。不同的字符串可能计算出相同的哈希值。尽管通过选择大质数模数和双哈希可以将其概率降到极低（远低于硬件错误概率），但在对正确性要求绝对严格的场景（如金融系统），可能仍需在哈希匹配后进行一次直接的字符串验证。
- 预处理开销：虽然查询快，但需要O(n)的预处理时间和空间。对于“只查询一次”的超短文本，可能不如直接暴力匹配。
- 模运算开销：取模运算是相对耗时的操作，在极端性能要求下需要考虑。
- 参数选择：
base和mod的选择会影响哈希质量。base通常需要大于字符集大小（如ASCII是128，可选131、137等质数），mod需要选择足够大的质数（如1e9+7, 1e9+9, 2^64自然溢出也可作为一种选择）。
八、总结
字符串哈希，特别是多项式哈希，为我们提供了一把处理字符串问题的“瑞士军刀”。它将复杂的字符串比较问题，转化为了数字的运算和比较问题，从而带来了性能上的飞跃。其O(1)时间查询子串哈希的能力，是许多高级字符串算法（如后缀数组的优化）的基础。
理解并掌握它，意味着你在处理字符串相关的问题时，多了一个强大而高效的思维工具和实战工具。记住它的核心：前缀预处理、哈希公式推导、以及警惕但可控的哈希冲突。从简单的单次匹配，到复杂的动态字符串问题，多项式哈希都能以其简洁而强大的特性，帮助你找到优雅的解决方案。希望这篇博客能帮你揭开字符串哈希的神秘面纱，并在你的开发之旅中助你一臂之力。
评论