開発メモ: TCのハッシュ関数を考える

Tokyo Cabinetのハッシュ関数のバリエーションに関する実験。 TCのハッシュ関数の特性 TCのハッシュデータベースに入れるレコードのキーとしてint型（32ビット）のオブジェクトをそのまま与えると、ハッシュのバケット配列の容量をいくら増やしても衝突率が下がらないというのは事実だ。実際にそういう使い方をしたユーザから、「なんでやねん」と質問やクレームをいただくことがあるわけだが、それに対しては、「TCのハッシュ関数は10進数の文字列に最適化しているので、キーの格納方法を変えてみてね」と答えるようにしている。 どういうことかここで整理してみる。TCのハッシュ関数は非常にナイーブな実装で、擬似コードで示すと以下のようになる。 hash = 19780211 foreach octets_of_data hash = hash * 37 + octet return hash % cap

[VoQn]

TokyoCabinetのハッシュアルゴリズムのチューニング方向性について。

[mooz]

FNV-1a, MurMurHash