algorithm - Rabin Karp 算法中的 Spurious Hits 如何等于 O (n/q)？

Question

我正在阅读 CLRS，因为我遇到了这条线“然后我们可以预期虚假命中的数量是 O(n/q)，因为任意 ts 的机会等于 p，模 q，可以估计为 1/q。”

我将包含完整描述的网站放在 34.2 主题下

请解释我们如何预期虚假命中 = O (n/q)

供引用http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap34.htm

Answer 1

为了分析的目的，通常假设使用的散列函数是Simple Uniform Hashing。该假设表明每个键被散列的可能性相同，而与其他键的散列方式无关。

换句话说，给定 q 个哈希函数可能产生的值，每个值的概率为 1/q。

在您链接到的示例中，他们讨论了 虚假命中 情况，当两个不同 字符串散列为相同的值时。给定一个简单的统一哈希，这个事件的概率是多少？

第一个字符串被散列为值 x。第二个字符串也被散列为值 x 的概率是多少？它是 1/q。

我推荐this lecture , 其中讨论了 Karp-Rabin 算法。