如果我有一个系统，其中从 100 万种可能性的总排列中生成哈希。如果有 10% 的概率发生碰撞，我是否应该担心生成算法运行 5 次？
- 我有一个类似于 jsfiddle 的系统，用户可以在其中“保存”我的服务器上的文件。现在我使用的是
'23456789abcdefghijkmnopqrstuvwxyz'，它有 33 个字符，文件长 4 个字符，总共有33^4 = 1,185,921种可能性。 - “文件名”是随机生成的，如果发生冲突，它会重新运行以获取另一个文件名。使用 birthday paradox calculator 我可以看到在我有 500 个条目后我有 10% 的机会发生碰撞。
- 我连续发生 5 次以上碰撞的可能性有多大？ 4 呢？
- 有什么办法可以解决这个问题吗？我应该担心吗？ 5000 个条目后会发生什么？
- 是否有一个程序可以通过任意输入解决这个问题？
最佳答案
我认为生日悖论计算不适用。在 1185921 中有 500 个随机数完全不同的几率与一旦您有 500 个已知的唯一数字后有一个新数字不同的几率之间存在差异。
如果您分配了 500 个号码并随机生成一个新号码，则它发生碰撞的几率为 500/1185921。取了 500 个名字，连续发生 4 次碰撞的概率是 (500/1185921)4 < 10-13。对于 5000 个现有文件名，新名称发生冲突的几率为 5000/1185921，连续发生 4 次冲突的几率为 < 10-9。
关于php - 哈希冲突的担忧，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10213709/