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 個ある場合に新しい 1 つの乱数が異なる確率との間には違いがあります。

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% の確率は、次のエントリが衝突する可能性ではなく、任意の 2 つのエントリが衝突する可能性です。

于 2012-04-18T16:31:40.087 に答える