hash - ハッシュ長を指定した一般化された誕生日の計算

Question

次のものが与えられたとします。

• ハッシュの長さ
• 衝突の可能性

さて、上記を知った上で、与えられた確率パーセンテージを取得するために必要な「サンプル」の数をどのように取得できますか?

Answer 1

Simplified formula誕生日のパラドックスを考えると、次のようになります。

probability = k^2/2N

そう：

sqr(probability*2*n) = k

n = 2^lengthHash がわかっている場合

小さなテスト: ハッシュ = 16 ビット: N= 65536 確率 = 50% = 0.5

平方(0.5*2*65536) =256 samples

簡略化された式から始めたので、これは 100% 正しいわけではありませんが、大きなハッシュと大きなサンプル セットの場合、これは非常に近くなります。

数式のリンクについては、こちらを参照してください。