哈希数据结构

Question

考虑具有n个桶的哈希表，其中外部（溢出）链接用于解决冲突。散列函数使得密钥值被散列到特定桶的概率是1 / n。哈希表最初为空，并且在表中插入K个不同的值。

1. 第K次插入后，桶号1为空的概率是多少？
2. 在任何K插入中没有发生碰撞的概率是多少？
3. 在第K次插入时发生第一次碰撞的概率是多少？

Answer 1

1. 一次插入后桶1为空的概率为(n−1)/n。这是第一项未散列到桶1的概率。在两次插入后它是空的事件由“第一项错过桶1”和“第二项错过桶1”定义，即(n - 1) * (n - 1) / n * n。有了这个，我希望你能计算出K插入后铲斗空的概率。
2. 对于K = 1，它是1。对于K = 2，第二项必须错过第一项的桶。所以它有n − 1的地方，它可以安全地去。因此成功的可能性是(n − 1) / n。那第三项呢？它只有它可以去的n−2地方。所以K = 3的概率是(n − 1) * (n - 2) / n * n。你可以概括一下。小心K > n的情况。
3. 一旦你弄清楚前两个部分的细节，你也可以在这个部分上取得进展。 提示：第一次碰撞发生在kth插入上，如果（i）第一次k−1插入没有碰撞（见2）和（ii）kth插入导致碰撞（参见2的补码）。

如果你能弄明白这三个答案，请告诉我。否则，我会提供更多细节。