User Tools

Site Tools


Fowler Noll Vo hash function

Fowler–Noll–Vo is a non-cryptographic hash function created by Glenn Fowler, Landon Curt Noll, and Phong Vo.

It is very simple to implement, and very fast. The FNV hash can come in several different sizes, 32-, 64-, 128-bit etc. See [http://www.isthe.com/chongo/tech/comp/fnv/index.html] for more information.

There are two versions of the hash, FNV-1 and FNV-1a. For all purposes the FNV-1a hash is recommended.

The basic algorithm of the FNV-1a hash is:

  1. hash = FNV_offset_basis
  2. for each octet_of_data to be hashed
    1. hash = hash XOR octet_of_data
    2. hash = hash $\times$ FNV_prime
  3. return hash

Javascript

Javascript makes implementation trickier by only providing math via floating point doubles. However 32-bit integers can be represented without data loss. Another aspect of Javascript to watch out for is that String.charCodeAt returns a 16-bit value and so has to be treated as two octets/bytes of data.

This implementation is the 32-bit FNV-1a hash.

λ Fowler_Noll_Vo_hash-string

fowler_noll_vo_hash_function.txt · Last modified: 2015/02/02 08:28 (external edit)