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?

• Extremely simple algorithm
• Very fast performance across platforms
• No external dependencies
• Public domain license

What are the disadvantages of the FNV hash?

• Not suitable for cryptographic use cases
• Slightly worse distribution than more complex hashes
• No customization or parameters

What are some examples of FNV usage?

• Checksums in network protocols
• Simple hash tables
• Data fingerprints and dispersion
• Fast non-cryptographic uniqueness checks

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:

• [Book] Designing Data-Intensive Applications
• [Article] A Survey on Transactional Stream Processing
• [Article] The Dataflow Model: A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale, Unbounded, Out-of-Order Data Processing
• [Post] Sliding Window Hash Join: Efficiently Joining Infinite Streams with Order Preservation
• [Post] General-purpose Stream Joins via Pruning Symmetric Hash Joins