algorithm - 散列冲突 (CLRS)

Question

我正在尝试解决这个问题(CLRS，第 3 版，练习 11.2-1):

Suppose we use a hash function h to hash n distinct keys into an array of length m. Assuming simple uniform hashing, what is the expected number of collisions?

正确的解是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 个槽中有 1/m 的几率发生碰撞，这意味着键 3 发生碰撞的概率为 1/m。键 1 和键 2 没有发生碰撞的概率为 (m-1)/m，这意味着它们位于不同的槽中，键 3 发生碰撞的概率为 2/m。

3 个键的预期碰撞次数，通过线性预期 = 0 + 1/m + (2m-1)/m^2 = (3m-1)/m^2

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

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

我的问题是:我的解决方案哪里出错了？为什么不同？

Answer 1

教师手册中的解决方案似乎不正确。简单示例，12 个键 [0..11]，通过 h(k) = k mod 3 散列成一个 3 元素数组。

我们有带键 0、3、6、9 的桶 0。存储桶 1 具有键 1、4、7、10。 Bucket 2 有键 2、5、8、11。桶 0 的碰撞是 {(0,3), (0,6), (0, 9), (3,6), (3,9), (6,9)}，基数 = 6。通过对称性，桶 1 和桶 2 也各有 6 次碰撞。

因此，此示例的总碰撞次数为 18。如果预期的碰撞次数由 n(n-1)/2m 公式给出，则为 12*11/6 = 22。

错了。

我通过这样的推理得到了另一个公式:

1. 如果我们假设统一哈希，每个桶中的键数应该与其他桶中的相同，即 n/m。因此，碰撞总数将为 m*Collisions(single bucket)。

2. 现在，我们如何获得每个桶中的碰撞次数？好吧，其中的每个键都会与所有其他键发生冲突，而碰撞集是通过一次取一对键来定义的。因此，我们正在查看一次取两个的 (n/m) 个元素的数字组合

C(n/m, 2) = (n/m)!/[2!(n/m -2)!] = [(n/m)(n/m -1)(n/m - 2)!]/[2*(n/m -2)!].

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

C(n/m, 2) = [(n/m)(n/m - 1]/2 = n(n-m)/2m^2

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

让我们将其应用到我们的示例中，好吗？

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

这正是我们示例中碰撞集的基数。