What a Bloom Filter Needs from a Hash

In one line

Bloom filter hashes must be deterministic, fast, uniformly distributed with good avalanche behaviour, and (approximately) independent across the k probes. Cryptographic strength is usually unnecessary; MurmurHash3, xxHash and similar fast hashes are the norm, unless attackers can choose inputs.

0/3 · 0%

Think of it like this

Dealing cards for a fair game. The shuffle has to spread cards evenly (uniform), look the same every time you replay the same deck order (deterministic), and be quick enough that the table isn't waiting (fast). It doesn't need to be secret from the players unless someone is cheating.

Key ideas

01
Deterministic: the same item must always map to the same positions, across processes, restarts and languages, or lookups miss their own bits (false negatives). That rules out language default hashes that are randomised per process (Python's hash() for strings, for example).
02
Uniform with good avalanche: changing one input bit should flip about half the output bits, so similar keys (user1, user2) don't cluster into the same positions.
03
Independence: the k probe positions should behave like independent draws. Using k unrelated hash functions is expensive; double hashing from one strong hash is standard and provably as good asymptotically.
04
Speed: hashing is most of a lookup's CPU. Non-cryptographic hashes (MurmurHash3, xxHash3, CityHash) are much faster than SHA-256.
05
Adversarial input: if attackers can choose keys and see results, they could craft keys that collide in a known hash function. Use a keyed hash (SipHash) or a secret seed when that matters (Phase 9).

Code & diagrams

hash-choices.txttext

Hash              Speed       Distribution   Keyed/seeded   Typical Bloom use
MurmurHash3 128   very fast   excellent      seed           Guava, many libraries
xxHash64 / XXH3   fastest     excellent      seed           RocksDB-style filters, custom
SipHash-2-4       fast        excellent      secret key     adversarial inputs
SHA-256           slow        excellent      (HMAC)         rarely; overkill
String.hashCode   fast        poor (32-bit)  no             never for Bloom filters
Python hash()     fast        good           random/process never: not stable across runs

Interview problem

The problem

Poorly distributed positions

A team built a Bloom filter using String.hashCode() and % m for the first position and hashCode * 31 for the others. Measured FPR is 6% where the maths says 1%. Explain the effects of poor distribution on collisions, bits set, false positives and performance.

When it breaks

Using a per-process randomised hash (for example Python hash() on strings)

What you see

Filters built in one process and checked in another (or after restart) use different positions, producing false negatives: items that were inserted appear absent.

Fix & prevent

Use a stable hash with a fixed seed recorded in the filter's metadata.

Explain it without notes

Why does a Bloom filter usually not need a cryptographic hash?

Practice

Fill two filters (same m, k, n) with sequential IDs user1..userN, one using hashCode-based positions and one using MurmurHash3 double hashing, and compare measured FPR.

Trade-offs

↔
Keyed cryptographic hashes resist adversarial inputs but cost CPU; fast non-cryptographic hashes are fine for trusted inputs.

Done when you can

I can list the hash requirements and choose a hash for trusted and adversarial workloads.

Command Palette