What is the FNV hash?
The FNV hash, short for Fowler–Noll–Vo hashes, are a family of fast non-cryptographic hash functions that use simple mathematical operations to map data to pseudo-random values with good distribution.
They are among the simplest high-performance hash algorithms, using just a few arithmetic and bitwise operations on the input bits and multiplier primes. Versions for 32, 64, 128, 256, 512, and 1024 bit hashes exist.
Despite their simplicity, FNV hashes provide excellent speed and distribution across many different data types. Their efficiency makes them popular general-purpose hashes for non-cryptographic uses like hash tables.
FNV competes with other very fast hashes like xxHash and MurmurHash which build on similar arithmetic mixing principles. It also inspired the design of consistent hashing algorithms.
How does the FNV hash work?
The FNV algorithm initializes an offset basis value and iteratively combines each input byte using XOR and multiplication by a large prime number modulo 2^N where N is the hash bit width.
This combines additive and multiplicative behavior to provide good dispersion across output space.
Why is the FNV hash important? Where is it used?
Despite its simplicity, FNV provides reasonably high performance and quality hashes suitable for general-purpose use in hash tables, network protocols, checksums, fingerprinting, and data dispersion.
The simplicity and public domain licensing also make FNV an easy default choice in many applications needing a basic quality hash function without cryptographic properties.
FAQ
What are the main advantages of the FNV hash?
What are the disadvantages of the FNV hash?
What are some examples of FNV usage?
How does FNV contrast with other hash algorithms?
It trades slightly lower quality for extreme simplicity and speed compared to more complex options like MurmurHash and xxHash.
References:
Related Topics
xxHash
xxHash is an extremely fast non-cryptographic hash algorithm focused on speed and efficiency for checksums and hash tables.
MurmurHash
MurmurHash is a series of fast non-cryptographic hash functions optimized for hash tables and CPU cache performance.
Consistent Hashing
Consistent hashing is a distributed hash technique that minimizes redistribution of keys when servers are added or removed, used in systems needing scalability and high availability.