これは基本的には数学的な問題ですが、非常にプログラムに関するものです：URLが10億文字含まれていて、それぞれのMD5ハッシュの最初の64ビットを取ると、衝突の頻度の種類私は期待する必要がありますか？1つの64ビット番号を持つURLを一意に識別する
1億のURLしかない場合、どのように答えが変わるのですか？
衝突は非常に稀ですが、これらのことは混乱する傾向があります。
私は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を参照してください。
あなたが "誕生日・パラドックス" としてこれをタグ付けしている、私はあなたknow the answer alreadyと思います。
P(Collision) = 1 - (2^64)!/((2^64)^n (1 - n)!)
あなたの場合、nは10億です。
MD5にはpratical collusion problemがあるので、MD5以外のものを使用すると少し良くなります。
私が見たものから、あなたは、64ビットの値
このhash function surveyは、あなたにとって最適な機能をドリルダウンするのに役立ちます。
私は、ここから複数の機能を試してみようと思っています。
実際には、テストするURLリストのために、確認したい既存のハッシュ関数（そのテーブル内の他の行）を特性化して選択するためのanother column like this test surveyを生成することができます。彼らは（reference to ZIP link）で始まるMSVC++ソースコードを持っています。
出力幅（64ビット）に合わせてハッシュ関数を変更すると、アプリケーションの特性をより正確に把握できます。
ハッシュを使用するだけで、常に衝突する可能性があります。そしてあなたは、あなたのリストの1〜2回、または数百回または数千回の衝突が事前に起こることを事前に知っていません。
確率はまだ確率です。 10倍から100倍のサイコロを投げているような気がしますが、すべての6本を得るチャンスは何ですか？確率は低いと言っていますが、それでもなお起こります。多分何度も何度も...
したがって、birthday paradoxは確率を計算する方法を示していますが、依然として衝突が許容できるかどうかを判断する必要があります。
...衝突が許容され、ハッシュはまだ正しい方法です。良好な分布を持つ「ハーフ・ア・MD5」に頼るのではなく、64ビット・ハッシング・アルゴリズムを見つける。 （おそらく... ...）
2^nハッシュの可能性がある場合、2 ^（n/2）個のアイテムがある場合、衝突確率は50％を超えます。
E.G.あなたのハッシュが64ビットであれば、2^64のハッシュ可能性があります。コレクションに2^32個のアイテムがある場合、衝突する可能性は50％です。
2^32（18,446,744,073,709,551,616）のところで、2^32と言った2^64を意味しますか？質問は64ビットについて話しますが、32ではなくです。 – unwind
いいえ、彼は2^32を意味します。つまり、100M URLの場合、1回の衝突確率は1％未満です。私はそれを取ると思う。 – itsadok
それは正しい、itsadok、私は2^32ではなく、2^64を意味する。それは誕生日のパラドックスの全体のポイントです。お互いに一致する任意の2つのランダムな値が1つのターゲットに一致する任意の1つのランダムな値のチャンスよりもはるかに高い確率 –