我一直在尝试在Java中实现Rabin-Karp算法。我很难计算恒定时间内的滚动哈希值。我在 http://algs4.cs.princeton.edu/53substring/RabinKarp.java.html 找到了一个实现。我仍然无法理解这两条线是如何工作的。
txtHash = (txtHash + Q - RM*txt.charAt(i-M) % Q) % Q;
txtHash = (txtHash*R + txt.charAt(i)) % Q;
我看了几篇关于模算术的文章，但没有一篇文章能够穿透我厚厚的头骨。请给出一些指导来理解这一点。
首先，您需要了解如何计算哈希。
让我们以 10 个字符串为基数的简单情况为例。您如何保证字符串的哈希代码是唯一的？以10为基数是我们用来表示数字的，我们没有碰撞！
“523” = 5*10^2 + 2*10^1 + 3*10^0 = 523
使用上面的哈希函数，您可以保证为每个字符串获得不同的哈希。
给定“523”的哈希值，如果要计算“238”的哈希值，即通过突出最左边的数字5并从右侧引入新的数字8，则必须执行以下操作：
1）从哈希中删除5的效果：哈希= 哈希 - 5 * 10 ^ 2（523-500 = 23）
2） 通过移位 1 来调整剩余字符的哈希值，哈希 = 哈希 * 10
3）添加新字符的哈希：哈希= 哈希+ 8（230 + 8 = 238，正如我们预期的那样，这是“238”的基数10哈希）
现在，让我们将其扩展到所有 ascii 字符。这把我们带到了256基地的世界。因此，同一字符串“523”的哈希值现在是
= 5*256^2 + 2*256^1 + 3*256^0 = 327680 + 512 + 3 = 328195。
您可以想象，随着字符串长度的增加，您将相对较快地超过大多数编程语言中的整数/长整型范围。
我们该如何解决这个问题？通常解决这个问题的方法是使用模量一个大素数。这种方法的缺点是，我们现在也会得到误报，如果它将算法的运行时从二次到线性，这是一个很小的代价！
您引用的复杂方程只不过是上面用模数数学完成的步骤1-3。上面使用的两个模量属性是->
a） （a*b） % p = （（a % p） * （b % p）） % p
b） a % p = （a + p） % p
让我们回到上面提到的步骤1-3->
1） （使用属性 a 扩展） 哈希 = 哈希 - （（5 % p）*（10^2 %p） %p）
与您引用的内容
txtHash = （txtHash + Q - RM*txt.charAt（i-M） % Q） % Q;
以下是两者是如何相关的！
- RM = 10^3 % p
- txt.charAt（i-M） % Q = 5 % p
- 您看到的附加 + Q 只是为了确保哈希不是负数。请参阅上面的属性 b。
2 & 3） hash = hash*10 + 8， vs txtHash = （txtHash*R + txt.charAt（i）） % Q;是一样的，但采取mod的最终哈希结果！
更仔细地查看属性a和b，应该可以帮助您弄清楚！
这是哈希的“滚动”方面。它消除了最古老字符（）的贡献，并结合了最新字符（）的贡献。txt.charAt(i-M)txt.charAt(i)
哈希函数定义为：
M-1
hash[i] = ( SUM { input[i-j] * R^j } ) % Q
j=0
（我用来表示“到权力”的地方。^
但这可以写成一个有效的递归实现，如：
hash[i] = (txtHash*R - input[i-M]*(R^M) + input[i]) % Q
您的参考代码正在执行此操作，但它使用各种技术来确保始终正确（有效地）计算结果。
因此，例如，第一个表达式中没有数学效应，但它确保总和的结果始终为正（如果它变为负，则不具有所需的效果）。它还将计算分解为多个阶段，大概是为了防止数值溢出。+ Q% Q
