1 つの 64 ビット数値で URL を一意に識別する

StackOverflow https://stackoverflow.com/questions/1096558

質問

これは基本的には数学の問題ですが、非常にプログラミングに関連しています。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 のを参照してください。

他のヒント

私が見たところ、次の要件を持つハッシュ関数が必要です。

  1. 任意の長さの文字列を 64 ビット値にハッシュします
    • 善意を持って -- 衝突を避けてください
    • 必ずしも一方通行ではない（セキュリティは必要ない）
    • できれば高速 -- セキュリティ以外のアプリケーションには必要な特性です

これ ハッシュ関数調査 最適な機能をドリルダウンするのに役立つ場合があります。
ここから複数の関数を試し、おそらく入力セットに合わせてそれらの関数を特徴付けることをお勧めします (表示されると思われる数十億の URL を選択してください)。

実際に生成することもできます このテストアンケートのような別のコラム テスト URL リストで特徴を明らかにし、チェックしたい既存のハッシュ関数または新しいハッシュ関数 (テーブル内のさらに多くの行) から選択します。彼らには () で始まる MSVC++ ソース コードがあります。ZIP リンクへの参照).

出力幅 (64 ビット) に合わせてハッシュ関数を変更すると、アプリケーションのより正確な特性評価が得られます。

あなたは2 ^ n個のハッシュの可能性を持っている場合は、2 ^（N / 2）の項目がある場合、衝突の50％の確率の上にあります。

例えば。あなたのハッシュが64ビットである場合は、コレクションで2 ^ 32のアイテムを持っている場合、あなたは2 ^ 64のハッシュの可能性を持っている、あなたは衝突の50％のチャンスがあると思います。

ただ、ハッシュを使用することにより、衝突の可能性は常にあります。そして、あなたは衝突がURLのリストに一度か二度、あるいは数百回または数千が起こるのだろう天気を事前に知っていません。

確率は、まだ単なる確率です。そのサイコロ10または100回を投げるように、すべてのシックスを得ることのチャンスは何ですか？確率はそれが低いと言うが、それはまだ発生する可能性があります。行の多分何回も...

、あなたはまだする必要がありますが、確率を計算する方法を示しの誕生日のパラドックスつつ衝突は許容されているかどうかを決めます。

...と衝突が許容され、ハッシュはまだ行くための正しい方法です。代わりに、良好な分布を有する「半-MD5」に頼るの64ビットのハッシュアルゴリズムを見つけます。 （それはおそらく持っていますが...）

所属していません StackOverflow
scroll top