MurmurHash

Algorithms/Data Structures
Updated on:
April 16, 2024

What is MurmurHash?

MurmurHash is a set of fast, non-cryptographic hash functions designed for high performance hash table use cases. It optimizes for hash speed on x86 architectures while maintaining good hash distribution qualities.

MurmurHash is focused on computational efficiency and uniform hashes suitable for general-purpose hash tables, lookups, and checksums on modern processors.

It uses multiplication, shifting, and remixing of input bits to generate randomized hashes very quickly. Variants like MurmurHash64 optimize for 64-bit architectures.

MurmurHash provides great speed and quality hashes making it popular for hash tables in databases, caching layers, and other applications where cryptographic security is not required. It competes with other fast hashes like FNV and xxHash while also inspiring the SipHash used in consistent hashing.

How does MurmurHash work?

MurmurHash uses multiplication, shifting, and XOR bitwise operations on input chunks to generate hash values extremely efficiently on x86 CPU architectures. It utilizes local caches well.

The mix of mathematical operations provides good randomness properties while minimizing compute-intensive instructions. Multiple versions accommodate different hash lengths.

Why is MurmurHash important? Where is it used?

MurmurHash provides one of the fastest general-purpose hash table and lookup hash functions on x86 platforms. It is widely adopted in databases, caching layers, data structures, bloom filters and other applications needing high-speed non-cryptographic hashes.

The optimized design makes MurmurHash suitable for any use case where hash performance is critical and cryptographic properties are not required.

FAQ

What are some key properties of MurmurHash?

  • Extremely fast on x86 platforms
  • Good distribution for low collisions
  • Portable C/C++ implementations
  • Public domain license

What are limitations of MurmurHash?

  • Not suitable for security needs
  • Optimized for x86; slower on other platforms
  • No built-in salting or customization
  • Vulnerable to hash flooding denial of service attacks

What are alternative hash options?

  • xxHash - Extremely fast with focus on multi-platform portability
  • CityHash - Hash function tuned for string inputs
  • SipHash - Cryptographic MAC focused on security

What differentiates MurmurHash from cryptographic hashes?

It prioritizes speed over cryptographic properties like collision resistance, one-way security, avalanching effects that slower cryptographic hashes provide.

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 ->
FNV Hash

The FNV hash is a fast, simple non-cryptographic hash function that uses modular arithmetic operations to achieve good distribution.

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