hash - urisの効率的なハッシュ関数

Question

文字列の（グローバル）固定サイズIDを構築するためのハッシュ関数を探しています。ほとんどの場合はURIです。

そのはず：

• 速い
• 衝突の可能性が低い
• 〜64ビット
• 可能であれば、URIの構造を利用しますか？

http://murmurhash.googlepages.com/が良い選択でしょうか、それとももっと適したものはありますか？

Answer 1

MD4を試してください。暗号化に関する限り、それは「壊れた」ものですが、セキュリティ上の懸念がないため (64 ビットの出力サイズが必要であり、衝突に対してまともなセキュリティを得るには小さすぎます)、それはすべきではありません。問題。MD4 は 128 ビットの値を生成するため、必要なサイズに切り捨てる必要があります。

暗号化ハッシュ関数は、衝突を構築する際の明示的な試みに対する回復力を目的として設計されています。おそらく、その条件を緩和することでより高速な関数を構築できます (決定的な攻撃者よりもランダムな衝突を打ち負かす方が簡単です)。MurmurHash など、いくつかの関数があります。ただし、実際に速度の違いに気付くには、かなり特殊な設定が必要になる場合があります。私の自宅の PC (2.4 GHz Core2) では、単一の CPU コア (私は 4 つのコアを持っています) を使用して、MD4 で毎秒約 1,000 万の短い文字列をハッシュできます。MurmurHash が無視できない程度に MD4 よりも高速であるためには、1 秒あたり少なくとも 100 万回のハッシュ呼び出しを含むコンテキストで使用する必要があります。そんなことは滅多にありません…。

Answer 2

MurmurHash3 が完成するまでもう少し待ってから、それを使用します。128 ビット バージョンは、誕生日のパラドックスに対する十分な衝突保護を提供するはずです。