在Rabin-Karp字符串搜索算法中是否使用了滚动哈希函数的任何工作实现？
我正在寻找使用滚动哈希函数，因此我可以使用非常大的字符串的n-gram哈希值。
例如：
“stackoverflow”，分解成5克将是：
“stack”，“tacko”，“ackov”，“ckove”，“kover”，“overf”，“verfl”，“erflo”，“rflow”
这对于滚动哈希函数是理想的，因为在我计算第一个n-gram哈希之后，以下的哈希计算相对便宜，因为我只需要删除第一个哈希的第一个字母并添加第二个哈希的新的最后一个字母。
我知道通常这个哈希函数生成为：
H = c 1 a k – 1 + c 2 a k – 2 + c 3 a k – 3 + … + c k a 0其中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作为我的素数。 我的哈希会溢出是否重要？ 我认为这是可取的，但我不确定。
这似乎是正确的方法吗？
我记得一个稍微不同的实现，似乎来自sedgewick的算法书之一（它还包含示例代码 – 尝试查找）。 这是一个调整为32位整数的摘要：
你使用模运算来防止你的整数在每次操作后溢出。
最初设定：
- c = text（“stackoverflow”）
- M =“n-gram”的长度
- d =您的字母大小（256）
- q =一个大素数，因此（d + 1）* q不会溢出（8355967可能是一个不错的选择）
- dM = d M-1 mod q
首先计算第一个n-gram的哈希值：
h = 0 for i from 1 to M: h = (h*d + c[i]) mod q
并为每一个后续的n-gram：
for i from 1 to lenght(c)-M: // first subtract the oldest character h = (h + d*q - c[i]*dM) mod q // then add the next character h = (h*d + c[i+M]) mod q
在减去最旧的字符之前必须添加d * q的原因是因为由于先前的模运算引起的小值而可能会遇到负值。
包括错误，但我认为你应该得到这个想法。 尝试找到sedgewick的算法书之一，以获取详细信息，减少错误和更好的描述。 🙂
据我所知，这是一个函数最小化：
2^31 - sum (maxchar) * A^kx
其中maxchar = 62 （对于A-Za-z0-9 ）。 我刚刚通过Excel（OO Calc，确切地说）:)计算了它，并且对于素数，它找到的最大值A是76或73 。
不确定你的目标是什么，但是如果你想提高性能，使用math.pow将比你通过计算滚动哈希值节省的成本更高。
我建议你从保持简单和高效开始，你很可能发现它足够快。