algorithm - 为 Rabin-Karp 字符串搜索算法找到一个好的散列函数

Question

有哪些好的散列函数可用于实现Rabin-Karp 字符串搜索算法？我只知道多项式散列，但它有一些缺陷——最值得注意的是，如果散列是以 ​​2 ⁶⁴为模完成的，则有一个测试可以保证经常产生冲突（并且使用另一个模数是不切实际的，因为mod操作非常昂贵） . 那么，有没有一个快速、易于编写的好哈希函数呢？

PS 我知道 buzhash，但我想知道是否还有其他选择......</p>

Answer 1

由于它不是安全哈希，您只需要一个“好的”指纹，我建议使用Tabulation hashing之类的东西。孔操作将比 mod 操作快几倍。