algorithm - 32ビットハッシュを使用した場合の衝突の確率

Question

データベースに10文字の文字列キーフィールドがあります。このフィールドをハッシュするためにCRC32を使用しましたが、重複が心配です。この状況での衝突の可能性を誰かに教えてもらえますか？

ps私の文字列フィールドはデータベース内で一意です。文字列フィールドの数が100万の場合、衝突の確率はどのくらいですか？

score 102 · Accepted Answer

ここに画像の説明を入力

score 43 · Accepted Answer

あなたが引用した場合、少なくとも1つの衝突が本質的に保証されます。少なくとも 1 回衝突する確率は、約 1 ～ 3x10 ^-51です。予想される衝突の平均数は約 116 です。

一般に、 k 個のサンプルでの衝突の平均数は、それぞれがn 個の可能な値からランダムに選択されます。

N(n,k)~=k(k-1)/(2n)

少なくとも 1 回の衝突の確率は次のとおりです。

p(n,k)~=1-e^(-k(k-1)/(2n))

あなたの場合、n = 2 ³²およびk = 10 ⁶です。

あなたの場合の3方向衝突の確率は約 0.01 です。誕生日問題を参照してください。

2 に答える 2