Etikettarkiv: source

FNV-Hash

Recently I needed a fast an reliable hash function with good statistics on distribution and I came across what is commonly known as the FNV-hash function. FNV is short for Fowler / Noll / Vo the last names of the three most prominent people contributing to the hashing function.

Basically the FNV algorithm is a very simple one but it is effective and yields astonishingly well differentiated hashes. It has been used in many different codes and both the algoritm itself and a standard source coude has been released into the public domain.

Pseudo code

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

The above is called the FNV-1 algorithm. If the multiplication and the XOR change place we get a variant called the FNV-1a which is very similar in all aspects of the first one. I decided to implement both and hash both as 32 bit numbers and then put them together into one 64 bit number creating a very fast and even spread of hashed numbers.

Prime and offsets

32 bit
Prime: 16777619 offset: 2166136261
64 bit
Prime: 1099511628211 offset: 14695981039346656037

Here is a page on FNV that is a good source of information.