哈希中的碰撞概率 Table
Probability of Collisions in Hash Table
将 n 项插入大小为 m 的散列 table 时，假设每个项的目的地是独立均匀随机的，不发生冲突的概率是多少？
我目前的工作：
我们有 n 个项目和 m 个位置。
每个项目都有 1/m 的机会出现在任何特定位置。
有 nC2 个可能的项目对。
没有碰撞的概率是对于每个位置，每对项目都没有散列到该位置的概率。
对于任何给定位置，对于任何给定对，两个项目未散列到该位置的概率是 (m-1)/m。
然后，对于任何给定的位置，以上对所有对成立的概率是 ((m-1)/m)^(nC2)。
那么，每个位置都成立的概率是
[((m-1)/m)^(nC2)]^(m).
你在推理中犯了一些错误。最主要的是你假设没有散列在一起的概率是独立的，所以你可以将它们相乘。你没有证明是这样，事实上并非如此。考虑三个元素 a、b 和 c。如果知道a和b都不会和c发生碰撞，那么它们就被限制在m-1个地方而不是最初的m个地方，比起直接忽略c.
这里有一个简单的方法来找到您想要的概率。查看忽略碰撞的总可能性，n 个项目中的每一个都有 m 个地方可以去。这些位置是独立的，所以如果我们考虑顺序，总的可能性是 m^n（或 Python 中的 m**n）。
如果我们知道没有碰撞，那 n 个项目是一种从 m 个位置中选择而无需替换的方法。因此，如果我们考虑到顺序，这就会产生 mPn 可能性——从 m 个选项中选择 n 个项目而不用替换和按顺序（排列）的方法。因此你想要的概率是
mPn / m^n = (m!) / ((m-n)! * m^n) = m/m * (m-1)/m * (m-2)/m * ... * (m-n+1)/m
最后一个表达式中有 n 个因素。 （这在 MathJax 中会好得多！）您可以选择这三个等价表达式中的哪一个最适合您的目的。
当然，还有其他方法可以想出这些表达式。最后一个可以被认为是在 m 个插槽中放置 1 个项目的无碰撞概率乘以在没有先前碰撞的情况下放置第二个项目的条件概率乘以在没有先前碰撞时间的情况下放置第三个项目的条件概率......
这些表达式很容易测试。只需选择特定的、较小的 m 和 n 值，从这些 m 中生成 n 项的所有可能选择，并找到不发生碰撞的经验概率。这应该与上面的公式一致。我会将编程语言和编码的选择留给您。毕竟，这是一个编程站点。我刚刚在 Python 中对 n 和 m 进行了多项选择，结果成功了。
将 n 项插入大小为 m 的散列 table 时，假设每个项的目的地是独立均匀随机的，不发生冲突的概率是多少？
我目前的工作： 我们有 n 个项目和 m 个位置。 每个项目都有 1/m 的机会出现在任何特定位置。 有 nC2 个可能的项目对。 没有碰撞的概率是对于每个位置，每对项目都没有散列到该位置的概率。
对于任何给定位置，对于任何给定对，两个项目未散列到该位置的概率是 (m-1)/m。
然后，对于任何给定的位置，以上对所有对成立的概率是 ((m-1)/m)^(nC2)。
那么，每个位置都成立的概率是 [((m-1)/m)^(nC2)]^(m).
你在推理中犯了一些错误。最主要的是你假设没有散列在一起的概率是独立的，所以你可以将它们相乘。你没有证明是这样，事实上并非如此。考虑三个元素 a、b 和 c。如果知道a和b都不会和c发生碰撞，那么它们就被限制在m-1个地方而不是最初的m个地方，比起直接忽略c.
这里有一个简单的方法来找到您想要的概率。查看忽略碰撞的总可能性，n 个项目中的每一个都有 m 个地方可以去。这些位置是独立的，所以如果我们考虑顺序，总的可能性是 m^n（或 Python 中的 m**n）。
如果我们知道没有碰撞，那 n 个项目是一种从 m 个位置中选择而无需替换的方法。因此，如果我们考虑到顺序，这就会产生 mPn 可能性——从 m 个选项中选择 n 个项目而不用替换和按顺序（排列）的方法。因此你想要的概率是
mPn / m^n = (m!) / ((m-n)! * m^n) = m/m * (m-1)/m * (m-2)/m * ... * (m-n+1)/m
最后一个表达式中有 n 个因素。 （这在 MathJax 中会好得多！）您可以选择这三个等价表达式中的哪一个最适合您的目的。
当然，还有其他方法可以想出这些表达式。最后一个可以被认为是在 m 个插槽中放置 1 个项目的无碰撞概率乘以在没有先前碰撞的情况下放置第二个项目的条件概率乘以在没有先前碰撞时间的情况下放置第三个项目的条件概率......
这些表达式很容易测试。只需选择特定的、较小的 m 和 n 值，从这些 m 中生成 n 项的所有可能选择，并找到不发生碰撞的经验概率。这应该与上面的公式一致。我会将编程语言和编码的选择留给您。毕竟，这是一个编程站点。我刚刚在 Python 中对 n 和 m 进行了多项选择，结果成功了。