1

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

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

2 回答 2

3

我不认为生日悖论计算适用。1185921 中的 500 个随机数字的几率完全不同，而一旦您拥有 500 个已知的唯一数字，一个新数字的几率就会不同。

如果您有 500 个分配的号码并随机生成一个新号码，则发生碰撞的几率为 500/1185921。使用 500 个名称，连续 4 次冲突的可能性为 (500/1185921) 4 < 10 -13。对于 5000 个现有文件名，新名称发生冲突的几率为 5000/1185921，并且连续 4 次冲突的几率 < 10 -9。

于 2012-04-18T16:37:08.290 回答
1

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

chance of collision ^ x;

碰撞的可能性是： 

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

您可以在上面看到，条目越多，情况就越糟（空间越大越好）。

另请注意，生日悖论可能不是您想要的。10% 的几率是任何两个条目发生冲突的几率，而不是下一个条目发生冲突的几率。

于 2012-04-18T16:31:40.087 回答