Command Palette

Search for a command to run...

Hectal
Phase 2Intermediate3 of 12 in Bloom Filters

Hash Functions

What a Bloom filter needs from its hashes, why production filters use double hashing from one 128-bit hash, and how to detect and fix bad distribution.

The false-positive formula assumes perfect, independent hashes. Real implementations get very close to that with fast non-cryptographic hashes and a trick that derives all k positions from two values. Get hashing wrong and the filter quietly performs far worse than its maths says.

0/3 · 0%
3 topics ~22 min 3 code blocks & diagrams
Start with the first topic
1
2.1

What a Bloom Filter Needs from a Hash

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.

8 min 1 code practice

2
2.2

Double Hashing: k Positions from Two Hashes

Computing k independent hashes is slow. Kirsch and Mitzenmacher showed that positions g_i(x) = h1(x) + i·h2(x) mod m, from just two hash values, give the same asymptotic false-positive rate. Most production filters take h1 and h2 from one 128-bit MurmurHash3 call.

7 min 1 code practice

3
2.3

Detecting and Fixing Bad Distribution

You can check hash quality empirically: bit density should be uniform across regions of the array, measured FPR on known non-members should match (1 − e^(−kn/m))^k, and the estimated count from the fill ratio should match the real count. Deviations point to weak hashes, bugs in index arithmetic or skewed keys.

7 min 1 code practice