在 rabin-karp 滚动哈希中选择基数和模素数

Question

哈希函数在维基百科上有解释

它说，“a 和 n 的选择对于获得良好的散列至关重要；” 并参考了一篇感觉不相关的线性同余生成器文章。我无法弄清楚如何选择这些值。有什么建议？

Answer 1

该算法的基础是次数最多为d的非零多项式最多有d个零。每个长度为 k 的字符串都有其自己关联的k - 1 次多项式，我们通过减去相关字符串的多项式并评估a来筛选可能的匹配项。如果字符串相等，则结果始终为零。如果字符串不相等，则当且仅当a是多项式差的零之一时，结果为零（这是对n提出素数要求的事实，因为否则整数 mod n将不是一个字段）。

至少从理论上讲，我们希望a是随机的，这样不经意的对手就无法以任何频率产生误报。如果我们预计不会出现麻烦，那么最好选择a，这样乘以a的成本就低（例如， a的二进制展开式具有少量的 1 位）。然而，某些选择对于典型的字符串集（例如，a = 1）是不好的。我们希望n足够大，以避免随机出现误报（概率 ( k - 1)/ n），但又足够小，并且最好采用特殊形式，以便模计算高效。