[解決済み] MurmurHash - それは何ですか？

質問

を高いレベルで理解しようとしてきました。 ムルムルハッシュ が行います。

基本的な説明は読みましたが、どのような時になぜ使うのか、良い説明がまだ見つかっていません。非常に高速であることは知っていますが、もう少し詳しく知りたいのです。

関連する質問をしました。 質問 という質問に対して、MurmurHashを使うことを提案した人がいました。それはうまくいくのですが、私はリスクと利点を理解したいと思います。

どのように解決するのですか？

Murmurは、非暗号化用途に適した汎用ハッシュ関数群です。Austin Appleby氏が述べたように、MurmurHashは以下のような利点を備えています。

• シンプルである（生成されるアセンブリ命令の数において）。
• 分布が良い（実質的にすべてのキーセットとampでカイ二乗検定をパスする）。
• 良い アバランシェ の動作に影響を与えます（最大0.5%の偏り）。
• 耐衝突性が良い（Bob Jenkinのfrog.c torture-testをパス。4バイトのキーでは衝突は起こりえないし、小さな（1〜7ビットの）差分もない)。
• Intel/AMDハードウェアで優れた性能を発揮し、ハッシュ品質とCPU消費量のトレードオフを実現します。

UUIDのハッシュ化には確かに使えます（他の高度なハッシュ化関数と同じように）。CityHash、Jenkins、Paul Hsiehのものなど...）。さて、Redisのビットセットは4GBビット(512MB)に制限されています。つまり、128ビットのデータ（UUID）を32ビット（ハッシュ値）にする必要があるわけです。ハッシュ化関数の品質がどうであれ、衝突は発生します。

Murmurのような工学的なハッシュ関数を使えば、分布の質を最大にし、衝突の数を最小にすることができますが、それ以外の保証はありません。

汎用のハッシュ関数の品質を比較したリンクです。

http://www.azillionmonkeys.com/qed/hash.html

http://www.strchr.com/hash_functions

<ストライク http://blog.aggregateknowledge.com/2011/12/05/choosing-a-good-hash-function-part-1/

<ストライク http://blog.aggregateknowledge.com/2011/12/29/choosing-a-good-hash-function-part-2/

<ストライク http://blog.aggregateknowledge.com/2012/02/02/choosing-a-good-hash-function-part-3/