FNV-1a

ハッシュ関数の実装。

キー値のそれぞれのバイトに対して、排他的論理和と乗算を1回ずつ行い、ハッシュ値を求めるアルゴリズム。

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とFNV_primeは値を変える。

offset_basis

  • 32bit 2166136261
  • 64bit 14695981039346656037
  • 128bit 144066263297769815596495629667062367629
  • 256bit 100029257958052580907070968620625704837092796014241193945225284501741471925557

FNV_prime

  • 32bit $2^{24} + 2^8 + 0x93 = 16777619$
  • 64bit $2^{40} + 2^8 + 0xb3 = 1099511628211$
  • 128bit $2^{88} + 2^8 + 0x3b = 309485009821345068724781371$
  • 256bit $2^{168} + 2^8 + 0x63 = 374144419156711147060143317175368453031918731002211$

実装(golang)

const offset32 = 2166136261
const prime32 = 16777619

func FNV32a(data []byte) uint32 {
	var hash uint32 = offset32
	for _, c := range data {
		hash ^= uint32(c)
		hash *= prime32
	}
	return hash
}

参考

http://www.isthe.com/chongo/tech/comp/fnv/