私はMurmurHashが何をするのかを高レベルで理解しようとしてきました。
私は基本的な説明を読みましたが、それをいつ使用するのか、そしてその理由についての良い説明をまだ見つけていません。私はその非常に速いことを知っていますが、もう少し知りたいです。
UUIDをRedisビットセットに適合させる方法について関連する質問をしました。誰かがMurmurHashの使用を提案しました。それは機能しますが、リスク/メリットを理解したいと思います。
質問する
55382 次
2 に答える
118
Murmur は、非暗号化の使用に適した、優れた汎用ハッシュ関数のファミリーです。Austin Appleby が述べているように、MurmHash には次の利点があります。
- シンプル（生成されたアセンブリ命令の数に関して）。
- 良好な分布 (実質的にすべてのキーセットとバケット サイズのカイ 2 乗テストに合格。
- 良好な雪崩挙動 (最大バイアス 0.5%)。
- 良好な衝突耐性 (Bob Jenkin の frog.c torture-test に合格。4 バイト キーの衝突はありえず、小さい (1 ～ 7 ビット) 差分はありません)。
- Intel/AMD ハードウェアで優れたパフォーマンスを発揮し、ハッシュ品質と CPU 消費の間の適切なトレードオフを実現します。
もちろん、UUID をハッシュするために使用できます (他の高度なハッシュ関数と同様に: CityHash、Jenkins、Paul Hsieh など...)。現在、Redis ビットセットは 4 GB ビット (512 MB) に制限されています。したがって、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/
于 2012-08-10T12:25:22.263 に答える