我正在尝试解决这个问题（CLRS，第 3 版，练习 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 个插槽中发生碰撞的概率为 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's 找到正确的解决方案。
我的问题是：我的解决方案哪里出错了？为什么不一样？
讲师手册中的解决方案似乎已关闭。简单的例子，12 个键 [0..11]，通过 h(k) = k mod 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。通过对称，存储桶 1 和 2 也各有 6 次碰撞。
因此，此示例的冲突总数为 18。如果预期的冲突数由 n(n-1)/2m 公式给出，则为 12*11/6 = 22。
错误的。
通过这样的推理，我得出了另一个公式：
如果我们假设统一散列，每个桶中的键数应该与任何其他桶中的相同，即 n/m。因此，碰撞总数将是 m*Collisions（单桶）。
现在，我们如何获得每个桶中的碰撞次数？好吧，其中的每个键都与所有其他键发生冲突，并且通过一次获取一对它们来定义冲突集。因此，我们正在查看一次取两个的 (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(nm)/2m^2
因此，碰撞总数为 m*C(n/m, 2) = n(nm)/2m。
让我们将此应用于我们的示例，好吗？
12(12-3)/2*3 = 12*9/6 = 18
这正是我们示例中碰撞集的基数。
密钥 1 和 2 在 1 个槽中发生碰撞的概率为 1/m，这意味着密钥 3 的碰撞概率为 1/m
这取决于如何处理冲突。对于封闭式哈希实现，将为密钥 2 选择一个替代存储桶，因此在插入密钥 3 时第一个哈希存储桶发生冲突的机会仍然是 2/m（那么在第二选择时可能会有更多机会桶，第三选择桶等 - 见下文）。对于开放散列，冲突元素将被链接到同一个桶，因此如果键 1 和 2 发生冲突，则键 3 第一次散列到同一个桶的机会减少 1/m（并且可能有更多的机会在第二选择桶等）。
因此，一个大问题是您假设不同的冲突处理方法：封闭式哈希与开放式哈希。
也就是说，您提出的问题很模糊 - 碰撞后如何添加值会影响进一步碰撞的概率。例如，使用另一种哈希算法进行重新哈希，该算法也实现了简单的统一哈希，这意味着每次碰撞后重新插入尝试时都会有另一个 #inserted/#buckets 碰撞概率，因此该系列如下：
关键 1：预期 # 冲突 = 0
关键 2：预期 # 碰撞次数 = 1/m + 1/m*1/m + 1/m*1/m*1/m + ...
关键 3：预期 # 碰撞次数 = 2/m + 2/m*2/m + 2/m*2/m*2/m + ...
对于例如线性探测、二次探测等，情况会有所不同。