与散列的碰撞(CLRS)

Question

我正在努力解决这个问题(CLRS，第三版，练习11.2-1)：

假设我们使用哈希函数h将n个不同的键散列到长度为m的数组中，假设简单的均匀散列，那么所期望的碰撞次数是多少？

正确的解是n(n-1)/2m.这摘自CLRS的指导员手册。

我的解决办法如下：

• 插入键1:与前辈碰撞的预期#=0
• 插入键2:与前辈碰撞的预期#= 1/m
• 插入键3:与前辈碰撞的预期#= 1/m*(1/m) + (m-1)/m*(2/m) = (2m-1)/m^2

我的推理是:键1和2在一个时隙中碰撞的概率为1/m，这意味着键3的碰撞概率为1/m，密钥1和键2没有碰撞的概率为(m-1)/m，这意味着它们处于不同的时隙中，密钥3的碰撞概率为2/m。

按期望为0+ 1/m + (2m-1)/m^2 = (3m-1)/m^2的线性关系，计算了3个键的预期碰撞次数。

根据CLRS，3键的预期碰撞次数应为3/m。

我知道如何使用指标RV的找到正确的解决方案。

我的问题是：，我在解决方案上犯了什么错误？，为什么不一样？

Answer 1

指导员手册中的解决方案似乎已经过时了。简单的例子，12个键0.11，通过h(k) =k 3散列到一个3元素数组中。

桶0有键0、3、6、9，桶1有键1,4,7,10，桶2有键2,5,8,11，桶0的碰撞是{ (0，3)，(0,6)，(0，9)，(3,6)，(3,9)，(6,9)}，基数=6。

因此，这个例子的碰撞总数为18，如果n(n-1)/2m公式给出了所期望的碰撞次数，则为12*11/6 = 22。

不对。

通过这样的推理，我得出了另一个公式：

1. 如果假设是一致哈希，那么每个桶中的键数应该与任何其他桶中的键数相同，即n/m，因此，碰撞的总数将是m*冲突(单桶)。
2. 现在，我们如何得到每个桶中的碰撞次数？其中的每一个键都会与所有的键发生碰撞，而这组碰撞是通过一次取对来定义的。因此，我们正在研究(n/m)元素的数字组合，每次取两个元素。

C(n/m，2) = (n/m)!/2!(n/m -2)！= (n/m)(n/m -1)(n/m -2)！/2*(n/m2)！

(n/m-2)！分子/分母中的术语相互抵消，我们得到

C(n/m，2) = (n/m)(n/m - 1/2 = n(n-m)/2m^2

因此，碰撞总数为m*C(n/m，2) =n(/2m)/2m。

让我们把这个应用到我们的例子中，好吗？

12(12-3)/2*3 = 12*9/6 = 18

在我们的例子中，这正是一组碰撞的基数。

Answer 2

键1和2在一个槽内碰撞的概率为1/m，这意味着键3的碰撞概率为1/m。

这取决于如何处理碰撞。对于封闭哈希实现，将为键2选择另一个桶，因此当插入键3时，在第一个哈希时发生碰撞的几率仍然是2/m (然后在第二个选项桶、第三个选择桶等处可能会有更多的机会--参见下面)。对于公开哈希，碰撞元素将被链接在同一个桶上，因此，如果键1和2发生碰撞，则键3第一次哈希到同一个桶的几率降低了1/m (在第二选择桶等上发生碰撞的可能性更大)。

因此，一个很大的问题是，您假设了不同的冲突处理方法:封闭的和开放的哈希。

尽管如此，正如您所提出的问题一样，这个问题是模糊的--在碰撞后如何添加值可以影响进一步碰撞的概率。例如，使用同样实现简单一致散列的替代散列重散列意味着在每次碰撞后重新插入尝试时，另一个#插入/#桶碰撞概率，因此本系列文章如下：

• 键1:预期#冲突=0
• 键2:预期#碰撞= 1/m + 1/m*1/m +1/m*1*1/m+.
• 关键3:预期#碰撞= 2/m + 2/m*2/m +2/m*2*2/m+.

这对于线性探测、二次探测等来说是另一回事。