哈希冲突担忧

Question

如果我有一个系统，其中一个散列是由100万个可能性的总排列产生的。如果有10%的可能性发生碰撞，我应该担心生成算法运行5次吗？

• 我有一个类似jsfiddle的系统，用户可以在我的服务器上“保存”一个文件。现在我使用的是'23456789abcdefghijkmnopqrstuvwxyz'，它是33个字符，文件有4个字符长，总共有33^4 = 1,185,921的可能性。
• “文件名”是随机生成的，如果发生冲突，它会重新运行以获得另一个文件名。使用一个生日悖论计算器，我可以看到，在我有500个条目之后，我有10%的机会发生碰撞。
• 我连续碰撞5次以上的可能性有多大？那四块呢？
• 有什么办法解决这个问题吗？我该担心吗？在5000条条目之后会发生什么？
• 有没有一个程序可以用任意的输入来解决这个问题？

Answer 1

我的数学有点生疏，所以请容忍我。

在一行中获得x碰撞的机会很简单：

chance of collision ^ x;  

发生碰撞的可能性是：

entries/space (which is 500/1185921 or 0.04%).

您可以在上面看到，越多的条目(越大的空间越好)，这种情况会变得更糟。

另外要注意的是，生日悖论可能并不完全是你想要的。10%的概率是任何两个条目都会发生碰撞的机会，而不是下一个条目发生碰撞的可能性。