One of FNV's key advantages is that it is very simple to implement. Start with an initial hash value of
FNV offset basis. For each byte in the input,
multiply hash by the
FNV prime, then
XOR it with the byte from the input. The alternate algorithm, FNV-1a, reverses the multiply and XOR steps.
FNV-1 hash The FNV-1 hash algorithm is as follows:
algorithm fnv-1
is hash :=
FNV_offset_basis for each byte_of_data to be hashed
do hash :=
hash ×
FNV_prime hash :=
hash XOR byte_of_data return hash In the above
pseudocode, all variables are
unsigned integers. All variables, except for
byte_of_data, have the same number of
bits as the FNV hash. The variable,
byte_of_data, is an 8-
bit unsigned
integer. As an example, consider the 64-
bit FNV-1 hash: • All variables, except for
byte_of_data, are 64-
bit unsigned
integers. • The variable,
byte_of_data, is an 8-
bit unsigned
integer. • The
FNV_offset_basis is the 64-
bit value: 14695981039346656037 (in hex, 0xcbf29ce484222325). • The
FNV_prime is the 64-
bit value 1099511628211 (in hex, 0x100000001b3). • The
multiply returns the lower 64
bits of the
product. • The
XOR is an 8-
bit operation that modifies only the lower 8-
bits of the hash value. • The
hash value returned is a 64-
bit unsigned integer.
FNV-1a hash The FNV-1a hash differs from the FNV-1 hash only by the order in which the
multiply and
XOR is performed:
algorithm fnv-1a
is hash :=
FNV_offset_basis for each byte_of_data to be hashed
do hash :=
hash XOR byte_of_data hash :=
hash ×
FNV_prime return hash The above pseudocode has the same assumptions that were noted for the FNV-1 pseudocode. The change in order leads to slightly better
avalanche characteristics.
FNV-0 hash (deprecated) The FNV-0 hash differs from the FNV-1 hash only by the initialisation value of the
hash variable:
algorithm fnv-0
is hash := 0
for each byte_of_data to be hashed
do hash :=
hash ×
FNV_prime hash :=
hash XOR byte_of_data return hash The above pseudocode has the same assumptions that were noted for the FNV-1 pseudocode. A consequence of the initialisation of the hash to 0 is that empty messages and all messages consisting of only the byte 0, regardless of their length, hash to 0. For a given integer such that , let and ; then the -
bit FNV prime is the smallest
prime number that is of the form :256^t + 2^8 + \mathrm{b}\, such that: :* , :* the number of one-bits in the
binary representation of is either 4 or 5, and :* . Experimentally, FNV primes matching the above constraints tend to have better dispersion properties. They improve the polynomial feedback characteristic when an FNV prime multiplies an intermediate hash value. As such, the hash values produced are more scattered throughout the -
bit hash space.
FNV hash parameters The above FNV prime constraints and the definition of the FNV offset basis yield the following table of FNV hash parameters: ==Non-cryptographic hash==