我一直在试着用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;
我看了几篇关于模算术的文章，但是没有一篇文章能够让我听懂。请给我一些理解这个的指点。
首先，您需要了解哈希是如何计算的。
让我们以十进制字符串为例。你如何保证一个字符串的哈希码是唯一的呢？十进制用于表示数字，我们不会出现碰撞！
"523" = 5*10^2 + 2*10^1 + 3*10^0 = 523
使用上面的哈希函数，您可以保证每个字符串都有不同的哈希。
给定"523"的哈希值，如果你想要计算"238"的哈希值，即从左边取出数位5并将一个新的数位8从右边插入，您需要执行以下操作：
1）去除数字5的影响：hash = hash - 5*10^2 (523-500 = 23)
2）通过向左移动1位来调整其余字符的哈希值，hash = hash * 10
3）添加新字符的哈希值：hash = hash + 8 (230 + 8 = 238，这正是"238"的哈希值)
现在让我们将此扩展到所有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展开) hash = hash - ((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，与txtHash = (txtHash*R + txt.charAt(i)) % Q相同；但是取模最终哈希结果！
更仔细地观察属性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不会产生预期的效果）。它还将计算分解成多个阶段，可能是为了防止数字溢出。
R^M 而不是 R*M。 - interjay