ハッシュ関数ベンチマーク

わけあってハッシュ関数を使ったプログラムを作ることになりました．
入力キーには仕様的に数値的限定をかけて，ゼロから１億程度としました．
ならば，20億入る符号付き32bitで十分なはずです．
そんなに長くない32bitを出してくれるハッシュ関数として，MurMurがあったので，

ベンチマークスーツでその性能を検証してみました．

libmemcachedでは，種類としてはFNV，crc32(?)，hsieh，murmur,jenkins，md5がサポートされてます．
KyotoCabinetではmurmurとfnv．
redisでは入力と出力を64bitに拡張したバージョンのmurmurが使われています．
phpはクライアントとしてはさすがにデフォルトで沢山サポートされてますね．md?，sha?，ripemd?，whirpool，tiger?，snefru，gost，adler32，crc?，haval?等々．
Hadoopのorg.apache.hadoop.util.hashの中には，jenkinsとmurmurがあります．
Cassandraにはorg.apache.cassandra.utils.MurmurHashというクラスがありました．

数値的に1億が目標だったのですが，古いノートPC事情で5000万までが限界だったので，そちらで実験しました．
比較したのは，個人的周囲でよく使われているmd5，sha1とMurMur3，あとlibmemcachedやKyotoCabinetで使われているfnvと，
確信は無いのですが，バーンシュタインハッシュ．Constant DBやdaemontool，postfixのバーンシュタインさんのCubeHashのことかなぁと想像して．
この合計5種類．

結果は以下です．

ハッシュの衝突率．BernsteinとFNVはつねに1％を超えていてダントツ（に悪い），md5/sha1/MurMur3は1%以下でした．

計算時間．sha1とmd5が遅く，MurMur3とFNVは同じくらい（ただし，FNVは衝突率が高いので．．．），Bernsteinは高速ですけど，やはり衝突率が高く．．．

md5/sha1/MurMur3が衝突率がさほど変わらないことを考えると，やはりMurMur3は高速です．

あとは，分散度を見ましょう．

md5は3000くらいの間にありますね．

sha1は広範囲大きな値になっちゃってるのがあるので，ちょっと偏って見えますね．

MurMur3はやっぱり3000くらいの間にありますね．

Bernsteinは凄く綺麗にバラついてますね．でも5000万のキーで5000万→32bitへの衝突率が90%とかいくので，ちょっとダメかな．．．

FNVは，やっぱり3000くらいの間に収まっているようです．でも衝突率が高いのが．．．

やはり総合的には，md5やsha1はファイル配布に使用されるくらいですから，入力シーケンスバイトサイズが大きくても信頼がおけて，BernsteinやFNVは，なにか偏りがあるので怪しく，ちょうど10億や2億の数値を扱うには，MurMurが高速で衝突率も妥当なようです．

バラつきの分散はこんな感じです．

Bernstein以外は似たような値になっています．
Bernsteinは異常に分散が小さく綺麗にバラついているかのようですが，この実験では衝突率が98%くらいいっていて，5000万種類のキーを入れたはずが90万くらいしかデータが入っていないので．．．