我正在阅读 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
问问题
1858 次
1 回答
0
为了分析的目的，通常假设使用的散列函数是Simple Uniform Hashing。这个假设表明，每个键都同样可能被散列到，而与其他键的散列方式无关。
换句话说，给定q哈希函数可以产生的可能值，每个值的概率为1/q。
在您链接到的示例中，他们讨论了虚假命中场景，即两个不同的字符串哈希到相同的值。给定一个简单的统一哈希，这个事件的概率是多少？
第一个字符串被散列到 value x。第二个字符串也被散列到 value 的概率是x多少？是1/q。
我推荐这个讲座，它讨论了 Karp-Rabin 算法。
于 2016-05-06T20:39:17.740 回答