一个看似简单的问题
给你一个字符串"abcdefg"，现在需要判断子串s[1:4]和子串s[3:6]是否相等。你会怎么做？
最直观的方法是逐字符比较：遍历两个子串的每个字符，逐一对比。对于长度为k的子串，这需要O(k)的时间复杂度。当子串较长或者需要进行大量比较时，这种方法的性能瓶颈就会暴露出来。
如果需要在O(1)时间内完成这个判断呢？字符串哈希提供了一种优雅的解决方案。
多项式哈希：把字符串变成数字
字符串哈希的核心思想是将字符串映射为一个整数，这个整数就是字符串的"指纹"。如果两个字符串的指纹相同，那么它们极大概率是相同的字符串（存在哈希冲突的可能，但概率极低）。
哈希函数的设计
最常用的字符串哈希方法是多项式哈希（Polynomial Rolling Hash）。对于一个字符串s，其哈希值计算公式为：
$$hash(s) = s[0] \times p^{n-1} + s[1] \times p^{n-2} + ... + s[n-1] \times p^0$$其中：
- $s[i]$表示字符串第i个字符的ASCII码或自定义编码
- $p$是一个基数（base），通常选择质数，如31、131、137等
- $n$是字符串的长度
为了避免哈希值过大导致溢出，通常需要对一个大质数M取模：
$$hash(s) = (s[0] \times p^{n-1} + s[1] \times p^{n-2} + ... + s[n-1] \times p^0) \mod M$$为什么选择这些参数？
基数p的选择很有讲究。根据生日悖论，当使用模M时，大约需要进行$O(\sqrt{M})$次哈希操作后才会遇到第一次冲突。选择较大的M（如$10^9+7$或$10^9+9$）可以显著降低冲突概率。
关于p和M是否需要互质的问题，研究表明：如果p是随机选择的，那么即使M不是质数，冲突概率也最多是n/M（n为字符串长度）。但如果M是质数，冲突概率的上界会更紧。
前缀哈希：O(1)时间获取任意子串哈希
如果我们预先计算字符串的每个前缀的哈希值，就可以在O(1)时间内获取任意子串的哈希值。
定义前缀哈希数组h，其中h[i]表示前缀s[0…i-1]的哈希值：
$$h[0] = 0$$$$h[i] = (h[i-1] \times p + s[i-1]) \mod M$$
同时预计算p的幂次数组pow，其中pow[i] = $p^i \mod M$。
那么子串s[l…r]的哈希值可以通过前缀哈希数组快速计算：
$$hash(s[l...r]) = (h[r+1] - h[l] \times pow[r-l+1] + M) \mod M$$这个公式的直观理解是：先取出前缀s[0…r]的哈希值，然后减去前缀s[0…l-1]的贡献。由于s[0…l-1]在s[0…r]中占据了高位，所以需要乘以$p^{r-l+1}$来进行对齐。
public class StringHash {
private long[] h; // 前缀哈希
private long[] pow; // p的幂次
private final int P = 131; // 基数
private final long M = (long)1e9 + 7; // 模数
public StringHash(String s) {
int n = s.length();
h = new long[n + 1];
pow = new long[n + 1];
pow[0] = 1;
for (int i = 1; i <= n; i++) {
h[i] = (h[i-1] * P + s.charAt(i-1)) % M;
pow[i] = (pow[i-1] * P) % M;
}
}
// 获取子串s[l...r]的哈希值（0-indexed）
public long getHash(int l, int r) {
return (h[r+1] - h[l] * pow[r-l+1] % M + M) % M;
}
}
有了这个数据结构，判断两个子串是否相等只需要比较它们的哈希值，时间复杂度为O(1)。
滚动哈希：滑动窗口的魔法
滚动哈希（Rolling Hash）是字符串哈希的一个重要应用场景，特别适合处理滑动窗口相关的问题。其核心思想是利用前一个窗口的哈希值，在O(1)时间内计算出下一个窗口的哈希值。
基本原理
假设我们有一个长度为n的字符串，需要计算所有长度为k的子串的哈希值。朴素方法需要对每个子串重新计算，时间复杂度为O(nk)。使用滚动哈希，可以将时间复杂度降低到O(n)。
对于长度为k的窗口，假设当前窗口的哈希值为$H_{old}$，窗口向右滑动一个字符后，新窗口的哈希值$H_{new}$可以这样计算：
$$H_{new} = ((H_{old} - s[i] \times p^{k-1}) \times p + s[i+k]) \mod M$$Rabin-Karp算法：模式匹配的经典应用
Rabin-Karp算法是滚动哈希最著名的应用之一，用于在文本中查找模式串的所有出现位置。
算法步骤：
- 计算模式串pattern的哈希值patternHash
- 计算文本text中第一个长度为m的子串的哈希值
- 使用滚动哈希依次计算后续子串的哈希值
- 当哈希值匹配时，进行逐字符验证（避免哈希冲突导致的误判）
public List<Integer> rabinKarp(String text, String pattern) {
List<Integer> result = new ArrayList<>();
int n = text.length(), m = pattern.length();
if (m > n) return result;
final int P = 31;
final long M = (long)1e9 + 7;
// 计算p^m
long pm = 1;
for (int i = 0; i < m; i++) pm = (pm * P) % M;
// 计算pattern的哈希值
long patternHash = 0;
for (int i = 0; i < m; i++) {
patternHash = (patternHash * P + pattern.charAt(i)) % M;
}
// 计算text前m个字符的哈希值
long textHash = 0;
for (int i = 0; i < m; i++) {
textHash = (textHash * P + text.charAt(i)) % M;
}
// 滑动窗口
for (int i = 0; i <= n - m; i++) {
if (textHash == patternHash) {
// 哈希值匹配，进行逐字符验证
if (text.substring(i, i + m).equals(pattern)) {
result.add(i);
}
}
// 计算下一个窗口的哈希值
if (i < n - m) {
textHash = ((textHash * P - text.charAt(i) * pm % M + M)
+ text.charAt(i + m)) % M;
}
}
return result;
}
Rabin-Karp算法的平均时间复杂度为O(n+m)，最坏情况下为O(nm)（当所有子串的哈希值都相同时）。
哈希冲突：不可忽视的风险
哈希冲突是指两个不同的字符串计算出相同的哈希值。虽然冲突概率很低，但在竞赛编程和实际工程中仍然需要重视。
冲突概率分析
对于多项式哈希，两个长度为n的不同字符串发生冲突的概率上界为n/M。当M=$10^9+7$，n=$10^5$时，冲突概率约为$10^{-4}$，这在大多数情况下是可以接受的。
但如果我们需要进行大量哈希比较，冲突风险会累积上升。例如，比较$10^5$个不同的字符串对，期望的冲突次数会显著增加。
降低冲突的方法
双哈希（Double Hashing）
使用两个不同的参数组合（p₁, M₁）和（p₂, M₂）计算两个哈希值，只有当两个哈希值都相同时才认为字符串相等。这将冲突概率降低到约$(n/M_1) \times (n/M_2)$。
public class DoubleHash {
private long[] h1, h2;
private long[] pow1, pow2;
private final int P1 = 31, P2 = 137;
private final long M1 = (long)1e9 + 7, M2 = (long)1e9 + 9;
public DoubleHash(String s) {
int n = s.length();
h1 = new long[n + 1];
h2 = new long[n + 1];
pow1 = new long[n + 1];
pow2 = new long[n + 1];
pow1[0] = pow2[0] = 1;
for (int i = 1; i <= n; i++) {
h1[i] = (h1[i-1] * P1 + s.charAt(i-1)) % M1;
h2[i] = (h2[i-1] * P2 + s.charAt(i-1)) % M2;
pow1[i] = (pow1[i-1] * P1) % M1;
pow2[i] = (pow2[i-1] * P2) % M2;
}
}
public long[] getHash(int l, int r) {
long hash1 = (h1[r+1] - h1[l] * pow1[r-l+1] % M1 + M1) % M1;
long hash2 = (h2[r+1] - h2[l] * pow2[r-l+1] % M2 + M2) % M2;
return new long[]{hash1, hash2};
}
}
随机基数
在运行时随机选择基数p，可以有效对抗针对特定参数构造的恶意数据。这也是为什么在竞赛中推荐使用随机化策略。
LeetCode经典题目解析
最长重复子串（LeetCode 1044）
问题描述：给定一个字符串s，找出其中最长的重复子串。重复子串是指出现至少两次的子串。
思路分析：
这是一个经典的字符串哈希应用问题。直接枚举所有子串并检查是否重复需要$O(n^3)$的时间复杂度。使用字符串哈希可以将比较时间降到O(1)，但仍然需要$O(n^2)$的时间。
进一步优化：使用二分查找+字符串哈希。二分查找最长重复子串的长度，对于每个候选长度，使用哈希集合检查是否存在重复。
class Solution {
long[] h, pow;
final int P = 131;
final long M = (long)1e9 + 7;
public String longestDupSubstring(String s) {
int n = s.length();
h = new long[n + 1];
pow = new long[n + 1];
pow[0] = 1;
// 预处理前缀哈希和幂次
for (int i = 1; i <= n; i++) {
h[i] = (h[i-1] * P + s.charAt(i-1)) % M;
pow[i] = (pow[i-1] * P) % M;
}
// 二分查找最长长度
int l = 1, r = n;
String result = "";
while (l <= r) {
int mid = l + (r - l) / 2;
String dup = check(s, mid);
if (dup != null) {
result = dup;
l = mid + 1;
} else {
r = mid - 1;
}
}
return result;
}
private String check(String s, int len) {
int n = s.length();
Map<Long, Integer> seen = new HashMap<>();
for (int i = 0; i + len <= n; i++) {
long hash = (h[i+len] - h[i] * pow[len] % M + M) % M;
if (seen.containsKey(hash)) {
// 验证是否真的相同（避免哈希冲突）
int start = seen.get(hash);
if (s.substring(start, start + len).equals(s.substring(i, i + len))) {
return s.substring(i, i + len);
}
}
seen.put(hash, i);
}
return null;
}
}
时间复杂度：$O(n \log n)$，其中二分查找需要$O(\log n)$次，每次检查需要$O(n)$时间。
重复的DNA序列（LeetCode 187）
问题描述：给定一个DNA序列字符串，找出所有出现超过一次的10字符子串。
思路分析：
这是滚动哈希的直接应用。由于DNA序列只包含’A’、‘C’、‘G’、‘T’四种字符，可以将它们编码为0、1、2、3，这样每个10字符子串可以用一个40位的整数表示（每个字符2位）。
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
List<String> result = new ArrayList<>();
if (s.length() < 10) return result;
Map<Character, Integer> mapping = new HashMap<>();
mapping.put('A', 0);
mapping.put('C', 1);
mapping.put('G', 2);
mapping.put('T', 3);
Map<Integer, Integer> count = new HashMap<>();
int hash = 0;
final int mask = (1 << 20) - 1; // 只保留低20位
for (int i = 0; i < s.length(); i++) {
hash = ((hash << 2) | mapping.get(s.charAt(i))) & mask;
if (i >= 9) {
count.put(hash, count.getOrDefault(hash, 0) + 1);
if (count.get(hash) == 2) {
result.add(s.substring(i - 9, i + 1));
}
}
}
return result;
}
}
时间复杂度：O(n)，其中n为字符串长度。
最长重复子数组（LeetCode 718）
问题描述：给定两个整数数组nums1和nums2，找出两个数组中都出现的最长公共子数组的长度。
思路分析：
这个问题可以转化为字符串哈希问题。将数组视为"字符串"，数组元素视为"字符"。使用二分查找确定最长公共子数组的长度，对于每个候选长度，使用哈希集合检查两个数组中是否存在相同的子数组。
class Solution {
long[] h1, h2, pow;
final int P = 101;
final long M = (long)1e9 + 7;
public int findLength(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
// 预处理nums1的前缀哈希
h1 = new long[m + 1];
pow = new long[Math.max(m, n) + 1];
pow[0] = 1;
for (int i = 1; i <= m; i++) {
h1[i] = (h1[i-1] * P + nums1[i-1]) % M;
pow[i] = (pow[i-1] * P) % M;
}
// 预处理nums2的前缀哈希
h2 = new long[n + 1];
for (int i = 1; i <= n; i++) {
h2[i] = (h2[i-1] * P + nums2[i-1]) % M;
if (i > m) pow[i] = (pow[i-1] * P) % M;
}
// 二分查找
int l = 0, r = Math.min(m, n);
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (check(nums1, nums2, mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
private boolean check(int[] nums1, int[] nums2, int len) {
Set<Long> seen = new HashSet<>();
for (int i = 0; i + len <= nums1.length; i++) {
long hash = (h1[i+len] - h1[i] * pow[len] % M + M) % M;
seen.add(hash);
}
for (int i = 0; i + len <= nums2.length; i++) {
long hash = (h2[i+len] - h2[i] * pow[len] % M + M) % M;
if (seen.contains(hash)) return true;
}
return false;
}
}
时间复杂度：$O((m+n) \log \min(m,n))$。
字符串中不同子串的数量（LeetCode 1698）
问题描述：给定一个字符串s，返回s中不同子串的数量。
思路分析：
使用字符串哈希可以高效地统计不同子串的数量。枚举所有子串的起点和长度，计算哈希值并存入集合，最终集合的大小就是不同子串的数量。
class Solution {
public int countDistinct(String s) {
int n = s.length();
long[] h = new long[n + 1];
long[] pow = new long[n + 1];
final int P = 131;
final long M = (long)1e9 + 7;
pow[0] = 1;
for (int i = 1; i <= n; i++) {
h[i] = (h[i-1] * P + s.charAt(i-1)) % M;
pow[i] = (pow[i-1] * P) % M;
}
Set<Long> seen = new HashSet<>();
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
long hash = (h[j+1] - h[i] * pow[j-i+1] % M + M) % M;
if (!seen.contains(hash)) {
seen.add(hash);
count++;
}
}
}
return count;
}
}
时间复杂度：$O(n^2)$，空间复杂度$O(n^2)$。
字符串哈希与其他方法的对比
与KMP算法对比
KMP算法是经典的字符串匹配算法，时间复杂度为O(n+m)。与Rabin-Karp相比：
- 适用场景：KMP适合单模式匹配，Rabin-Karp适合多模式匹配
- 实现复杂度：KMP需要理解next数组的构造，Rabin-Karp实现更直观
- 实际性能：单模式匹配时KMP通常更快，但Rabin-Karp可以方便地扩展到多模式
与字典树对比
字典树适合处理前缀相关的问题，如前缀统计、前缀匹配等。字符串哈希的优势在于：
- 空间效率：字符串哈希只需要O(n)的预处理空间
- 子串查询：字符串哈希擅长处理任意子串的比较，字典树更适合前缀操作
- 实现难度：字符串哈希实现更简洁
与后缀数组对比
后缀数组可以高效解决大量子串相关的问题，如最长公共子串、最长重复子串等。字符串哈希的优势：
- 实现难度：字符串哈希实现更简单
- 适用范围：字符串哈希更适合"存在性"查询，后缀数组适合"最优化"问题
- 时间复杂度：对于最长重复子串，字符串哈希+二分是$O(n \log n)$，后缀数组也是$O(n \log n)$，但常数因子不同
实践建议
参数选择
在实际应用中，推荐使用以下参数组合：
- 基数：选择大于字符集大小的质数，如31（小写字母）、131（ASCII）、137（通用）
- 模数：使用$10^9+7$或$10^9+9$，这两个数是$10^9$级别最大的质数之一
- 双哈希：在竞赛或对正确性要求高的场景下，使用两组不同参数
边界处理
- 模运算时注意处理负数：
(a - b) % M可能为负，需要加M后再取模 - 幂次数组预计算时考虑溢出：使用long类型存储中间结果
- 哈希冲突：关键场景下进行字符串直接比较验证
调试技巧
- 使用小数据测试：先用简单的字符串验证哈希函数的正确性
- 打印中间结果：输出前缀哈希和子串哈希，便于定位问题
- 验证边界情况：空字符串、单字符、全相同字符等
总结
字符串哈希通过将字符串映射为整数，实现了O(1)时间的子串比较，这是一个看似不可能的优化。其核心在于多项式哈希的数学设计和前缀哈希的空间换时间策略。
从判断子串相等到最长重复子串，从DNA序列分析到公共子数组查找，字符串哈希在各类问题中展现出强大的通用性。结合二分查找、滑动窗口等技术，可以解决许多看似复杂的字符串问题。
虽然哈希冲突是潜在的风险，但通过合理选择参数和双哈希策略，可以将冲突概率降到可接受的水平。在实际工程和算法竞赛中，字符串哈希都是不可或缺的工具。