algorithm - 在 rabin-karp rolling hash 中选择基数和模素数

Question

散列函数在 Wikipedia 上有解释。

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

Answer 1

该算法的基础是最多 d 次的非零多项式最多有 d 个零点。每个长度为 k 的字符串都有其相关的 k - 1 次多项式，我们通过减去相关字符串的多项式并在 一个。如果字符串相等，则结果始终为零。如果字符串不相等，则结果为零当且仅当 a 是多项式差的零点之一(这是对 n ，因为整数 mod n 否则将不是一个字段)。

至少在理论上，我们希望 a 是随机的，这样一个健忘的对手就不会以任何频率产生误报。如果我们不希望遇到麻烦，那么选择 a 可能会更好，这样乘以 a 就很便宜(例如，a 的二进制展开em> 有少量的一位)。然而，有些选择对典型的字符串集来说是不好的(例如，a = 1)。我们希望 n 足够大以避免随机误报(概率 (k - 1)/n)但又足够小且最好的特殊形式，以便模计算是有效的。