关于 Rabin-Karp 算法中滚动哈希的混淆 Java

Question

我试图在这里理解 Rabin-Karp 算法：http://algs4.cs.princeton.edu/53substring/RabinKarp.java.html。

看了很多文章，现在知道多项式哈希的一般形式是C1*A^k-1+C2*A^k-2+C3*A^k-3。看了代码，我明白了他们是如何在字符串中加减数字的。

txtHash = (txtHash + Q - RM*txt.charAt(i-M) % Q) % Q; txtHash = (txtHash*R + txt.charAt(i)) % Q;

此处程序减去前导数字，乘以整个哈希值，然后添加新数字。但是，当我查看计算散列的函数时，它并没有遵循多项式散列的一般形式。它看起来像这样：

 private long hash(String key, int M) { 
    long h = 0; 
    for (int j = 0; j < M; j++) 
        h = (R * h + key.charAt(j)) % Q; 
    return h; 
}

在这个函数中，他们将散列和基数相乘，然后添加 key.charAt()。我认为该函数会将 key.charAt() 与从 R^k-1 开始的基数相乘。然后随着 for 循环的继续，基数将除以 R 以提供多项式的递减幂。有人可以解释一下这个函数是如何工作的以及它是如何以我上面提到的形式生成哈希的吗？谢谢！

Answer 1

假设哈希函数需要传递3位数字。它看起来像：

{digits[0]*R^2+digits[1]*R^1+digits[2]}%Q  
= {(digit[0]*R^1+digits[1])*R+digits[2]}%Q

这将使散列函数更容易计算。

然后应用于Rabin-Karp算法，
你可以看到

RM = R^2 %Q;(M=2)

当您想移动下一个数字进行验证时，
您需要删除最左边的数字并添加下一个数字。

txtHash = {[txtHash - R^2*most_left_digit(equal charAt(i-M))]*R+next_digit(equal charAt(i))}%Q

与

相同

txtHash = (txtHash + Q - RM*txt.charAt(i-M) % Q) % Q; 
txtHash = (txtHash*R + txt.charAt(i)) % Q;

Mod Q每一步防止溢出。

关于 Rabin-Karp 算法中滚动哈希的混淆 Java

Confusion Regarding Rolling Hash in Rabin-Karp Algorithm Java

java

hash

rabin-karp