哈希冲突问题

Question

如果我有一个系统，该系统会在100万种可能性的总排列中生成哈希。如果有10％的碰撞机会，我应该担心生成算法运行5次吗？

• 我有一个类似于jsfiddle的系统，用户可以在其中“保存”服务器上的文件。现在，我正在使用'23456789abcdefghijkmnopqrstuvwxyz'，它是33个字符，文件长4个字符，总共33^4 = 1,185,921个可能性。
• “文件名”是随机生成的，如果发生冲突，它将重新运行以获取另一个文件名。使用birthday paradox calculator，我可以看到在输入500个条目之后，发生碰撞的机会为10％。
• 我连续发生5次以上碰撞的机率是多少？那4呢？
• 有没有办法解决这个问题？我应该担心吗？ 5000次输入后会发生什么？
• 是否有一个程序可以用任何人为的输入来解决这个问题？

Answer 1

我不认为生日悖论计算适用。当您拥有500个已知的唯一数时，在1185921中的500个随机数的几率全都不同，而一个新数字的几率也有所不同。

如果您有500个分配的数字并随机生成一个新数字，则发生冲突的几率是500/1185921。使用500个名称，连续发生4次冲突的机会是（500/1185921）⁴ <10 ^-13。使用5000个现有文件名，新名称发生冲突的几率是5000/1185921，并且连续4次发生冲突的机率是<10 ^-9。

Answer 2

我的数学有点生疏，请耐心等待。连续发生x次碰撞的机会很简单：

chance of collision ^ x;  

发生碰撞的可能性为：

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

您可以在上面看到，条目越多（空间越大，效果越好）。

还请注意，生日悖论可能并不是您想要的。 10％的机会是任何两个条目发生碰撞的机会，而不是下一个条目发生碰撞的机会。