FNV Hash

Algorithms/Data Structures
Updated on:
September 17, 2024

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:

Related Entries

xxHash

xxHash is an extremely fast non-cryptographic hash algorithm focused on speed and efficiency for checksums and hash tables.

Read more ->
MurmurHash

MurmurHash is a series of fast non-cryptographic hash functions optimized for hash tables and CPU cache performance.

Read more ->
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.

Read more ->

Get early access to AI-native data infrastructure