我正在阅读 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
最佳答案
为了分析的目的,通常假设使用的散列函数是Simple Uniform Hashing
。该假设表明每个键被散列的可能性相同,而与其他键的散列方式无关。
换句话说,给定 q
个哈希函数可能产生的值,每个值的概率为 1/q
。
在您链接到的示例中,他们讨论了 虚假命中 情况,当两个不同 字符串散列为相同的值时。给定一个简单的统一哈希,这个事件的概率是多少?
第一个字符串被散列为值 x
。第二个字符串也被散列为值 x
的概率是多少?它是 1/q
。
我推荐this lecture , 其中讨论了 Karp-Rabin 算法。
关于algorithm - Rabin Karp 算法中的 Spurious Hits 如何等于 O (n/q)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36965063/