Rabin-Karp 字符串匹配如何用滚动哈希加速？哈希冲突怎么处理？

简化版

Rabin-Karp 用哈希值比较代替逐字符比较：先算模式串哈希，再在主串上维护长度为 m 的滚动窗口哈希。窗口哈希等于模式串哈希时，再逐字符确认，避免哈希冲突导致误判。平均时间 O(n + m)，最坏在大量冲突时可能退化。

详细版

核心是把字符串看成一个进制数：hash = (((c1) * base + c2) * base + c3) ...。窗口右移时，减掉最高位字符贡献、乘以 base、加上新字符。因为整数可能溢出，通常配合取模；因为取模会有冲突，命中哈希后要二次校验。

int rabinKarp(String s, String p) {
    int n = s.length(), m = p.length();
    if (m == 0) return 0;
    if (m > n) return -1;
    long base = 256, mod = 1_000_000_007L;
    long power = 1, hp = 0, hs = 0;
    for (int i = 0; i < m; i++) {
        hp = (hp * base + p.charAt(i)) % mod;
        hs = (hs * base + s.charAt(i)) % mod;
        if (i < m - 1) power = power * base % mod;
    }
    for (int l = 0; l + m <= n; l++) {
        if (hp == hs && s.startsWith(p, l)) return l;
        if (l + m < n) {
            hs = (hs - s.charAt(l) * power % mod + mod) % mod;
            hs = (hs * base + s.charAt(l + m)) % mod;
        }
    }
    return -1;
}

适合多模式、重复搜索、字符串去重、子串判等这类题。面试里重点说明：滚动哈希只是候选过滤器，不是严格相等证明。

完整版教学

一、Rabin-Karp 想解决什么问题

朴素匹配每个起点都逐字符比较，最坏 O(nm)。Rabin-Karp 的思路是：先快速判断“这个窗口有没有可能等于模式串”，只有可能时才逐字符确认。

比如模式串长度是 4，主串窗口也固定为 4。我们不每次比较 4 个字符，而是比较一个整数哈希值：

s:  a b c d e
win abcd -> hash1
win bcde -> hash2

哈希不同，窗口一定不同；哈希相同，窗口可能相同，也可能冲突，需要再确认。

易错点：Rabin-Karp 的哈希命中只是“候选命中”，不能直接返回，除非题目允许概率算法或使用了可证明无冲突的编码范围。

二、字符串为什么能变成滚动哈希

把字符串当成 base 进制数：

"abcd" = a * base^3 + b * base^2 + c * base + d

窗口从 "abcd" 右移到 "bcde"：

先去掉 a * base^3
剩下 b * base^2 + c * base + d
再整体乘 base
最后加 e

这样每次右移只需要 O(1) 更新，而不是重新扫描窗口的 m 个字符。

操作	作用	复杂度
减最高位	删除离开窗口的字符贡献	`O(1)`
乘 base	所有字符位权左移一位	`O(1)`
加新字符	接纳右侧新字符	`O(1)`
命中后校验	防止哈希冲突	最多 `O(m)`

三、取模与负数修正

真实字符串可能很长，哈希数会超过整数范围，所以一般对大质数取模。取模后更新公式常写成：

hash = (hash - old * power % mod + mod) % mod
hash = (hash * base + new) % mod

这里加一次 mod 是为了避免减法后变成负数。Java 的 % 对负数仍可能是负数，如果不修正，后续比较会出现假失败。

四、代码里的关键变量

base 可以理解为字符集大小或一个固定进制；mod 用来控制数值范围；power 是 base^(m-1)，用于删除窗口最左字符的贡献。

long power = 1;
for (int i = 0; i < m - 1; i++) {
    power = power * base % mod;
}

如果少算或多算一次 power，删除最高位时就会删错量，整个滚动哈希都会偏掉。

五、为什么必须处理哈希冲突

不同字符串可能取到相同哈希。比如在小模数下，很多字符串都会被压缩到同一个余数。面试时要主动说：“哈希相等后我会逐字符校验，所以算法结果是确定正确的；冲突只影响性能，不影响正确性。”

if (hashText == hashPattern && s.startsWith(p, left)) {
    return left;
}

如果为了性能使用双哈希，也只能显著降低冲突概率；严格场景下仍建议保留校验，或者说明概率假设。

六、复杂度如何描述更准确

预处理模式串和第一个窗口是 O(m)，滑动窗口是 O(n)。若哈希分布好，只有少量候选需要校验，平均近似 O(n + m)。

最坏情况下，每个窗口都哈希相等且校验失败，就会退化到 O(nm)。这不是代码写错，而是哈希过滤器本身的理论边界。

七、常见误区与追问

误区：哈希值相等就代表字符串相等。 哈希有冲突，严格匹配题必须二次校验。
误区：窗口右移时忘记加 mod 修正负数。 Java 负数取模仍可能为负，比较会错。
误区：power 算成 base^m。 删除最左字符需要的是最高位权重 base^(m-1)。
追问：为什么 Rabin-Karp 平均是线性？ 每个窗口 O(1) 更新，哈希命中次数通常很少。
追问：双哈希能不能完全消除冲突？ 不能，只是把概率降得非常低；严格正确仍靠字符校验。
追问：它比 KMP 适合什么场景？ 多次子串判等、去重、多个模式或需要滚动窗口哈希的题更自然。

八、加强记忆

Rabin-Karp 的主线是“窗口字符串先变数字，数字不等直接跳过，数字相等再验真”。记住 3 个变量：base 决定位权，power=base^(m-1) 删除左端，mod 控制范围。面试回答时把“哈希冲突不影响正确性，因为命中后会校验”讲出来，就不会把它说成不可靠的玄学算法。

简化版

详细版