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