軽量ハッシュアルゴリズム

お久しぶりです。吉村です。

今回はハッシュアルゴリズムについて少し触れてみたいと思います。

既存のハッシュアルゴリズムはどういうものがあるでしょうか?
SHA-1, MD5等が浮かんだ方も多いと思います。

「じゃあそれでいいじゃん」

・・・ちょっと待ってください。
SHA-1, MD5というものは、暗号化のためのハッシュアルゴリズムです。
もし用途が単純なファイル比較等であれば、ここまで大げさなハッシュは冗長で高負荷低速であると言えます。
適切なアルゴリズムは状況によって適切に選びたいところです。

そこで今回は単純なファイル比較等に使用できる、簡単&軽量なハッシュアルゴリズムの

FNV-1

というアルゴリズムを紹介します。
C言語の実装は以下のようになります。
用途に応じて32, 64bitを切り替えましょう。
それ以上の精度が必要なら、
http://www.isthe.com/chongo/tech/comp/fnv/#FNV-param
こちらの定数と、適切なサイズの変数を使いましょう。


見て分かる通り、乗算が1回と排他的論理和が1回を、それぞれのバイトに対して行う、
非常に単純かつ明快なアルゴリズムです。
是非使ってみてください。