これは基本的に数学の問題ですが、非常にプログラミングに関連しています。URL を含む 10 億の文字列があり、それぞれの MD5 ハッシュの最初の 64 ビットを取得すると、どのような衝突頻度が予想されるでしょうか?
URL が 1 億しかない場合、答えはどのように変わりますか?
衝突は非常にまれであるように私には思えますが、これらは混乱を招く傾向があります。
MD5 以外のものを使用した方が良いでしょうか? 注意してください、私はセキュリティを探しているのではなく、高速なハッシュ関数を探しているだけです。また、MySQL のネイティブ サポートも優れています。
編集：まったく重複していません
MD5 の最初の 64 ビットが理想的な分散のハッシュを構成する場合、誕生日のパラドックスは、2^32 個の URL ごとに衝突が発生することを意味します。つまり、衝突の確率は、URL の数を 4,294,967,296 で割った値になります。詳細については、 http://en.wikipedia.org/wiki/Birthday_paradox#Cast_as_a_collision_problemを参照してください。
MD5 のビットの半分を捨てるだけでは気が進まないでしょう。上位および下位の 64 ビット ワードを XOR して、混合する機会を与える方がよいでしょう。繰り返しになりますが、MD5 は決して高速でも安全でもないので、まったく気にしません。目を見張るような速度と適切な配布が必要であるが、セキュリティのふりをしたくない場合は、MurmurHash の 64 ビット バージョンを試すことができます。詳細とコードについては、http://en.wikipedia.org/wiki/MurmurHashを参照してください。
私が見たところ、次の要件を持つハッシュ関数が必要です。
このハッシュ関数調査は、自分に最も適した関数にドリルダウンするのに役立つ場合があります。
ここから複数の関数を試して、可能性の高い入力セットに合わせて特徴付けることをお勧めします (表示されると思われる数十億の URL を選択してください)。
このテスト調査のような別の列をテスト URL リスト用に実際に生成して、既存または新しいハッシュ関数 (そのテーブル内のより多くの行) を特徴付け、選択することができます。最初に MSVC++ ソース コードがあります ( ZIP リンクへの参照)。
出力幅 (64 ビット) に合わせてハッシュ関数を変更すると、アプリケーションの特性がより正確になります。
あなたはこれを「誕生日のパラドックス」とタグ付けしました。あなたはすでに答えを知っていると思います.
P(Collision) = 1 - (2^64)!/((2^64)^n (1 - n)!)
ここで、あなたの場合、n は 10 億です。
MD5には実際的な共謀の問題があるため、MD5以外のものを使用すると少し良くなります。
2^n 個のハッシュの可能性がある場合、2^(n/2) 個のアイテムがある場合、衝突の可能性は 50% を超えます。
たとえば、ハッシュが 64 ビットの場合、2^64 ハッシュの可能性があり、コレクションに 2^32 アイテムがある場合、衝突の可能性は 50% になります。
ハッシュを使用するだけでは、常に衝突の可能性があります。また、URL のリストで衝突が 1 回または 2 回発生するか、あるいは数百回または数千回発生するかは事前にわかりません。
確率はあくまでも確率です。サイコロを 10 回または 100 回投げるようなもので、すべて 6 が出る確率はどのくらいですか? 確率は低いと言われていますが、それでも発生する可能性があります。もしかしたら連続で何度も…
したがって、誕生日のパラドックスは確率を計算する方法を示していますが、それでも衝突が許容できるかどうかを判断する必要があります。
...そして衝突は許容され、ハッシュは依然として正しい方法です。適切なディストリビューションを持つ "half-a-MD5" に依存する代わりに、64 ビットのハッシュ アルゴリズムを見つけます。(多分あるけど…)