Hashing Schemes

Bloom Filter

Test set membership in a handful of bits — it never misses a member, but occasionally cries wolf.

The bit array. Adding an item lights k bits; a query lights its k probes — green if all are set (member / possible member), orange when an absent item collides into a false positive.

What you're seeing

A Bloom filter is a set that stores no elements — only a bit array and a few hash functions. To add an item, hash it k ways and set those k bits. To test membership, hash the query the same k ways and check whether all those bits are set. If any is unset, the item was definitely never added. If all are set, it's probably a member — but it might be a coincidence, with other items' bits happening to cover all k. Watch absent queries occasionally light up entirely (orange): those are the false positives.

The rule

init:    m zero bits, k hash functions
add(x):  for r in 1..k:  bit[ hᵣ(x) ] = 1
test(x): return  bit[h₁(x)] AND … AND bit[hₖ(x)]

No deletions (clearing a bit could erase another item's membership), and no element is ever stored — just m bits, regardless of how big the items are.

The guarantee

Two halves. First a hard, one-sided guarantee: there are no false negatives. Adding x sets all k of its bits, and bits are never cleared, so a later test(x) finds them all set and returns true — always. A "no" is therefore definitive. Second, a predictable false-positive rate. After adding n items, a fraction p of the bits are set; a query for an absent item passes only if all k of its (essentially random) bits happen to fall on set ones, with probability ≈ p^k. Estimating p ≈ 1 − e^(−kn/m) gives the familiar closed form (1 − e^(−kn/m))^k. An honesty note this entry's own test taught us: that closed form is a large-m approximation — it slightly under-counts at small sizes, where the empirical rate tracks the measured-load p^k more closely. Either way: tune m and k to push the false-positive rate as low as you like; the never-miss guarantee is free.

The cost

Bloom filterHash set Spacem bits (≈ 10/item)O(n · item size) add / testO(k)O(1) Answerno-FN, ε false-posexact

The win is space: about 10 bits per item buys a ~1% false-positive rate — independent of how large the items themselves are (URLs, hashes, 100-character keys all cost the same). For a fixed m and n, the false-positive rate is minimized at k = (m/n)·ln 2 bits per item. The trade is the small error rate and the no-deletes restriction (counting Bloom filters relax that by storing small counters instead of bits).

In the wild

Bloom filters are everywhere a cheap "definitely-not / maybe-yes" pre-check saves an expensive lookup: databases like Cassandra, HBase, and Bigtable / LevelDB / RocksDB keep one per SSTable so a read can skip disk when a key is absent; web browsers and Google's Safe Browsing screened URLs against malware lists this way; CDNs and caches avoid storing one-hit-wonders ("don't cache until seen twice"); spell-checkers and network routers use them; and cryptocurrencies (Bitcoin SPV) used them for transaction filtering. The pattern is always the same — a tiny filter in fast memory guards a big, slow, or remote source of truth.

Try this

Shrink Bits (m) or push Items added (n) up and watch the array fill and the false-positive rate climb (more orange queries). Then sweep Hashes (k): too few and collisions are likely; too many and you fill the array too fast — there's a sweet spot, the readout's predicted rate bottoming out around k ≈ (m/n)·ln 2.

References

  1. Bloom, B. H. "Space/time trade-offs in hash coding with allowable errors." Communications of the ACM 13(7):422–426, 1970. The original.
  2. Broder, A. & Mitzenmacher, M. "Network applications of Bloom filters: A survey." Internet Mathematics 1(4):485–509, 2004.
  3. Bose, P. et al. "On the false-positive rate of Bloom filters." Information Processing Letters 108(4):210–213, 2008 — why the classic formula is an approximation.
  4. Andoni, A. Advanced Algorithms (Columbia COMS 4995-8, 2021), hashing lectures. course materials.