哈希表概率

Question

我仍然混淆了如何找到哈希表概率。我有大小为20的哈希表，具有开放的寻址，使用哈希函数。

散列(Int x) =x% 20

需要在哈希表中插入多少个元素，以便下一个元素碰撞的概率超过50%。

我用生日悖论来寻找问题，似乎得到了一个不正确的答案。我的错误在哪里？计算中

1/2=1-e^(-n^2/(2*20)) ln(1/2)=ln(e)*(-n^2/40) -0.69314718=-n^2/40 n=scr(27.725887)=5.265538

Answer 1

需要在哈希表中插入多少个元素，以便下一个元素碰撞的概率超过50%。

这要看几件事了。

简单的情况是，您已经用不同和有效的随机整数键执行了11个插入操作，例如11个桶正在使用，下一个插入使用另一个不同的、有效的随机键，因此它将以相同的概率散列到任意一个桶:很明显，这个桶被使用的概率只有9/20，这意味着您在第12次插入期间发生碰撞的几率首次超过50%。这是大多数公式、教科书、人等都能给你的答案，因为它是最有意义的，在哈希表与强散列函数和/或桶数质数等一起使用的情况下，哈希表闪闪发光，特别优雅。

另一种常见的情况是，您正在将业务的客户id放入哈希表中，并且从1开始为客户分配递增的id号。即使您已经插入了id为1到19的客户，您也知道他们在没有冲突的情况下处于[1]到[19]的桶中--您的哈希只是通过键传递，而不需要使用mod。然后，您可以将customer 20插入存储桶[0] (在mod操作之后)，而不会发生冲突。那么，第21位客户就有100%的机会发生碰撞。(但是，如果您的数据是这样的，请直接使用customer id或customer_id -1(如果您不想浪费桶)使用数组和索引。)

当您超过50%的碰撞概率时，键中还有许多其他可能的模式:例如，所有键都是某些值的奇数或倍数，或者是具有特定分布曲线的年龄或高度。

你使用生日悖论的错误在于认为它回答了你的问题。当您将"1/2“和"20”放入公式中时，它会告诉您，您的累积碰撞概率达到1/2，但您的问题是“next元素碰撞的概率超过50%”(重点是我的)。