FNVハッシュ関数

FNVハッシュ関数は簡単に実装できるハッシュ関数です。
Twitterで見かけたので忘れないうちにメモ。

FNV-1 hash

hash=offset_basis
for each octet_of_data to be hashed
  hash=hash*FNV_prime
  hash=hash xor octet_of_data
return hash

octet_of_dataは変換元データから8bitずつ取り出した物を表します。変換元データがアルファベットだけから成る文字列なら、一文字ずつ取り出すのと同じです。
offset_basisとFNV_primeについては後述します。

FNV-1a hash

XORを先にするだけです。変換元のデータが32bitよりも小さい場合はハッシュ値の分散度合いが良くなります。

hash=offset_basis
for each octet_of_data to be hashed
  hash=hash xor octet_of_data
  hash=hash*FNV_prime
return hash

offset_basis

hashのビット幅に応じて次の物を使います

• 32bit 2166136261
• 64bit 14695981039346656037
• 128bit 144066263297769815596495629667062367629
• 以下略

FNV_prime

hashのビット幅に応じて次の物を使います

• 32bit 16777619
• 64bit 1099511628211
• 128bit 309485009821345068724781371
• 以下略

例

#include <stdio.h>

int main() {
 char *s="abcde";
 unsigned int hash=2166136261UL;

  while (*s) {
    hash*=16777619UL;
    hash^=*(s++);
  }
  printf("%u\n",hash);
  return 0;
}