Bloom filters, and when a probabilistic set is the right call

A Bloom filter answers one question — “have I possibly seen this?” — using a bit array and a few hash functions. It can say definitely no or probably yes, never a false negative. For a surprising number of systems that’s exactly the question worth answering cheaply.

How it works

add(x):    for i in 1..k: bits[ hash_i(x) % m ] = 1
maybe(x):  for i in 1..k: if bits[ hash_i(x) % m ] == 0: return NO
           return MAYBE

m bits, k hashes. A missing bit proves absence. All bits present means probably present — some other elements may have set those same bits.

The one formula worth remembering

For n items and m bits, the optimal number of hashes is k = (m/n) ln 2, giving a false-positive rate around 0.6185^(m/n). In plain terms: about 10 bits per element buys you a ~1% false-positive rate. That’s it — ten bits, not a record, to filter out most misses.

Where it earns its keep

LSM-tree databases (RocksDB, Cassandra) put a Bloom filter in front of each on-disk table: before doing an expensive read to check whether a key is there, ask the filter. Most “key not present” lookups never touch disk. Same trick for CDN cache admission and for skipping network round-trips. You spend a few bits of RAM to avoid a millisecond of I/O — almost always a good trade.