在Rabin-Karp字符串搜索算法中是否使用了滚动哈希函数的任何工作实现？

Question

我正在寻找使用滚动哈希函数,所以我可以采用一个非常大的字符串的n-gram哈希值.

例如:

"stackoverflow",分解成5克将是:

"stack","tacko","ackov","ckove","kover","overf","verfl","erflo","rflow"

这对于滚动哈希函数是理想的,因为在我计算第一个n-gram哈希之后,以下的哈希计算相对便宜,因为我只需要删除第一个哈希的第一个字母并添加第二个哈希的新的最后一个字母.

我知道通常这个哈希函数生成为:

H = c ₁ a ^{k - 1} + c ₂ a ^{k - 2} + c ₃ a ^{k - 3} + ... + c _k a ⁰其中a是常数,c1,...,ck是输入字符.

如果您在Rabin-Karp字符串搜索算法上遵循此链接,它会声明"a"通常是一些大素数.

我希望我的哈希值存储在32位整数中,那么素数的大小应该是"a",这样我就不会溢出整数？

在我可以使用的某个地方是否存在此哈希函数的现有实现？

---

这是我创建的一个实现:

public class hash2
{

    public int prime = 101;

    public int hash(String text)
    {
        int hash = 0;

        for(int i = 0; i < text.length(); i++)
        {
            char c = text.charAt(i);
            hash += c * (int) (Math.pow(prime, text.length() - 1 - i));
        }

        return hash;
    }

    public int rollHash(int previousHash, String previousText, String currentText)
    {

        char firstChar = previousText.charAt(0);
        char lastChar = currentText.charAt(currentText.length() - 1);

        int firstCharHash = firstChar * (int) (Math.pow(prime, previousText.length() - 1));
        int hash = (previousHash - firstCharHash) * prime + lastChar;

        return hash;
    }

    public static void main(String[] args)
    {
        hash2 hashify = new hash2();

        int firstHash = hashify.hash("mydog");
        System.out.println(firstHash);
        System.out.println(hashify.hash("ydogr"));
        System.out.println(hashify.rollHash(firstHash, "mydog", "ydogr"));
    }

}

我用101作为我的素数.我的哈希会溢出是否重要？我认为这是可取的,但我不确定.

这似乎是正确的方法吗？

Answer 1

据我了解，这是一个函数最小化：

2^31 - sum (maxchar) * A^kx

其中maxchar = 62（对于A-Za-z0-9）。我刚刚通过 Excel（OO Calc，准确地说）计算了它:)，它发现的最大 A 是76，或73，对于素数。