如何计算哈希算法中发生冲突的概率？

Question

假设我有一个哈希算法，而且它是不错的（任何一个哈希值出现的概率与其他值相同）。

现在假设我知道选取2个哈希值并且它们发生冲突的概率（为了方便）是50000:1。

如果我选取了100个哈希值，如何计算在这一组100个值中发生冲突的概率，考虑到在2个值的集合中发生冲突的概率？

如何得出一般解决方案，以便我可以计算出在某些可接受的阈值以下的哈希尝试数量？例如，我可以说“49999个哈希值批次存在高碰撞概率”。

- izb

---

完美哈希算法是指没有冲突的算法。我只是想指出这一点。抱歉我有点挑剔 :-) - CiscoIPPhone

假设哈希函数的定义域大于值域，那是不可能的。如果不是这样，为什么要使用哈希呢？ - recursive

好的，你仍然可以获得使用哈希函数而不是搜索的速度优势。http://en.wikipedia.org/wiki/Perfect_hash_function - CiscoIPPhone

哦，抱歉。我没有意识到“完美哈希”在数学上有一个实际的定义。我习惯于软件定义，其中我们将字符串哈希为32位整数等。 - recursive

维基百科文章是软件定义。具有任何值的均等可能性的哈希术语为“平滑”。 - Pete Kirkham

http://davidjohnstone.net/pages/hash-collision-probability - Xeoncross

Answer 1

这是“生日问题”的一个泛化。

- Pesto

Answer 2

这听起来很像生日悖论。

你只需要将可能的生日数（365）替换为可能的哈希数（50000），然后运行他们在那里提供的相同计算即可。

如果你根据自己的数值修改了文章中呈现的Python脚本：

 def bp(n, d):
    v = 1.0
    for i in range(n):

         v = v * (1 - float(i)/d)
    return 1 - v

 print bp(2, 50000)

你最终得到的是两个数字碰撞的几率为0.00002。大约需要265个样本，你才有大约50％的概率发生碰撞。

- Dana

---

这是一个正确的端口吗？我得到了5.9的概率。 - Xeoncross

Answer 3

首先计算没有碰撞的概率：

hashes_picked = 100
single_collision_odds = 50000

# safe_combinations is number of ways to pick hashes that don't overlap
safe_combinations = factorial(single_collision_odds) / factorial(single_collision_odds - hashes_picked)

# all_combinations is total number of ways to pick hashes
all_combinations = single_collision_odds ** hashes_picked   

collision_chance = (all_combinations - safe_combinations) / all_combinations

- recursive

---

这意味着“乘方”或“指数”运算符。 2 ** 3 == 8。 - recursive

Answer 4

这被称为生日问题。要解决它，考虑不发生碰撞的概率（记为p_nc）。

• p_nc(1) = 1
• p_nc(2) = 1 - p_c(2)
• p_nc(3) = p_nc(2) * p_nc(2) * p_nc(2)

- MarkusQ

Answer 5

而在JS中

function calculate(n,k)
{

    var result =1;
    for (var i=0; i<k; i++){
        result=result*n/(n-i)
    }
    result=(1-1/result)*100;
    return result;
}

- Eyal Kenigsberg