Fowler Noll Vo hash
Encyclopedia
Fowler–Noll–Vo is a non-cryptographic
hash function
created by Glenn Fowler, Landon Curt Noll
, and Phong Vo.
The basis of the FNV hash algorithm was taken from an idea sent as reviewer comments to the IEEE POSIX P1003.2 committee by Glenn Fowler and Phong Vo back in 1991. In a subsequent ballot round, Landon Curt Noll improved on their algorithm. Some people tried this hash and found that it worked rather well. In an EMail message to Landon, they named it the ``Fowler/Noll/Vo or FNV hash.
The FNV hash algorithms and sample FNV source code have been released into the public domain.
FNV is not a cryptographic hash.
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.
hash = FNV_offset_basis
for each octet_of_data to be hashed
hash = hash
FNV_prime
hash = hash XOR octet_of_data
return hash
In the above pseudocode
, all variables are unsigned
integers. All variables, except for octet_of_data, have the same number of bits
as the FNV hash. The variable, octet_of_data, is an 8 bit
unsigned integer
.
As an example, consider the 64-bit
FNV-1 hash:
The values for FNV prime and FNV offset basis may be found in this table.
and XOR is performed:
hash = FNV_offset_basis
for each octet_of_data to be hashed
hash = hash XOR octet_of_data
hash = hash
FNV_prime
return hash
The above pseudocode
has the same assumptions that were noted for the FNV-1 pseudocode
. The small change in order leads to much better avalanche characteristics
.
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
hash function
Hash function
A hash function is any algorithm or subroutine that maps large data sets to smaller data sets, called keys. For example, a single integer can serve as an index to an array...
created by Glenn Fowler, Landon Curt Noll
Landon Curt Noll
Landon Curt Noll is an American computer scientist, co-discoverer of the 25th Mersenne prime and discoverer of the 26th, which he found while still enrolled in high school and concurrently at Cal State Hayward....
, and Phong Vo.
The basis of the FNV hash algorithm was taken from an idea sent as reviewer comments to the IEEE POSIX P1003.2 committee by Glenn Fowler and Phong Vo back in 1991. In a subsequent ballot round, Landon Curt Noll improved on their algorithm. Some people tried this hash and found that it worked rather well. In an EMail message to Landon, they named it the ``Fowler/Noll/Vo or FNV hash.
Overview
The current versions are FNV-1 and FNV-1a, which supply a means of creating non-zero FNV offset basis. FNV currently comes in 32-, 64-, 128-, 256-, 512-, and 1024-bit flavors. For pure FNV implementations, this is determined solely by the availability of FNV primes for the desired bit length; however, the FNV webpage discusses methods of adapting one of the above versions to a smaller length that may or may not be a power of two.The FNV hash algorithms and sample FNV source code have been released into the public domain.
FNV is not a cryptographic hash.
The hash
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, multiplyMultiply
Multiply is a social networking service with an emphasis on allowing users to share media – such as photos, videos and blog entries – with their "real-world" network...
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:hash = FNV_offset_basis
for each octet_of_data to be hashed
hash = hash
FNV_primehash = hash XOR octet_of_data
return hash
In the above pseudocode
Pseudocode
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
, all variables are unsigned
Signedness
In computing, signedness is a property of data types representing numbers in computer programs. A numeric variable is signed if it can represent both positive and negative numbers, and unsigned if it can only represent non-negative numbers .As signed numbers can represent negative numbers, they...
integers. All variables, except for octet_of_data, have the same number of bits
BITS
BITS or bits may refer to:* Plural of bit* Background Intelligent Transfer Service, a file transfer protocol* Birla Institute of Technology and Science, a technology school in Pilani, Rajasthan, India, with campuses in Goa, Hyderabad, and Dubai...
as the FNV hash. The variable, octet_of_data, is an 8 bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
unsigned integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
.
As an example, consider the 64-bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
FNV-1 hash:
- All variables, except for octet_of_data, are 64-bitBitA bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
unsigned integers. - The variable, octet_of_data, is an 8 bitBitA bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
unsigned integerIntegerThe integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
. - The FNV_offset_basis is the 64-bitBitA bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
FNV offset basis value: 14695981039346656037. - The FNV_prime is the 64-bitBitA bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
FNV prime value: 1099511628211. - The multiplyMultiplyMultiply is a social networking service with an emphasis on allowing users to share media – such as photos, videos and blog entries – with their "real-world" network...
(indicated by the
symbol) returns the lower 64-bitsBITSBITS or bits may refer to:* Plural of bit* Background Intelligent Transfer Service, a file transfer protocol* Birla Institute of Technology and Science, a technology school in Pilani, Rajasthan, India, with campuses in Goa, Hyderabad, and Dubai...
of the productProduct (mathematics)In mathematics, a product is the result of multiplying, or an expression that identifies factors to be multiplied. The order in which real or complex numbers are multiplied has no bearing on the product; this is known as the commutative law of multiplication...
. - The XOR is an 8-bitBitA bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
operation that modifies only the lower 8-bitsBITSBITS or bits may refer to:* Plural of bit* Background Intelligent Transfer Service, a file transfer protocol* Birla Institute of Technology and Science, a technology school in Pilani, Rajasthan, India, with campuses in Goa, Hyderabad, and Dubai...
of the hash value. - The hash value returned is an 64-bitBitA bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
unsigned integerIntegerThe integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
.
The values for FNV prime and FNV offset basis may be found in this table.
FNV-1a hash
The FNV-1a hash differs from the FNV-1 hash by only the order in which the multiplyMultiply
Multiply is a social networking service with an emphasis on allowing users to share media – such as photos, videos and blog entries – with their "real-world" network...
and XOR is performed:
hash = FNV_offset_basis
for each octet_of_data to be hashed
hash = hash XOR octet_of_data
hash = hash
FNV_primereturn hash
The above pseudocode
Pseudocode
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
has the same assumptions that were noted for the FNV-1 pseudocode
Pseudocode
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
. The small change in order leads to much better avalanche characteristics
Avalanche effect
In cryptography, the avalanche effect refers to a desirable property of cryptographic algorithms, typically block ciphers and cryptographic hash functions. The avalanche effect is evident if, when an input is changed slightly the output changes significantly...
.
See also
- Pearson hashingPearson hashingPearson hashing is a hash function designed for fast execution on processors with 8-bit registers. Given an input consisting of any number of bytes, it produces as output a single byte that is strongly dependent on every byte of the input...
(uses a constant linear permutation instead of a constant prime seed) - Jenkins hash functionJenkins hash functionThe Jenkins hash functions are a collection of hash functions for multi-byte keys designed by Bob Jenkins. They can be used also as checksums to detect accidental data corruption or detect identical records in a database...
- MurmurHashMurmurHashMurmurHash is a non-cryptographic hash function suitable for general hash-based lookup. It was created by Austin Appleby in 2008, and exists in a number of variants, all of which have been released into the public domain.-Variants:...
External links
- Landon Curt Noll's webpage on FNV (with table of base & prime parameters)
- Internet draft by Fowler, Noll, Vo, and Eastlake (2011, work in progress)