我读的是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这种假设表明，每个键都有可能被散列到，而与其他键的散列方式无关。
换句话说，给定hash函数可以产生的可能值，每个值的概率都是q。
在您链接到的示例中，他们讨论了当两个不同的字符串散列到同一个值时的虚假命中场景。给定一个简单的统一散列，这个事件的概率是多少？
第一个字符串被散列到值1/q。第二个字符串也被散列到值x的概率是多少？它是x。
我推荐this lecture，它讨论了Karp-Rabin算法。