Bloom Filters

A market-data cache needs to check, millions of times a second, whether a given order ID has already been processed, but storing every order ID ever seen, forever, in a hash set eats memory that grows without bound. A Bloom filter answers "have I definitely not seen this, or possibly seen this?" using a fixed, small block of memory, trading a small, tunable false-positive rate for that saved space.

How it works

Start with a bit array of size $m$, all zeros, and $k$ independent hash functions, each mapping an item to a position in that array.

To add an item: compute its $k$ hash values, and set the bit at each of those $k$ positions to 1.

To check an item: compute the same $k$ hash values. If any of those bits is 0, the item was definitely never added, a bit that's still 0 could only mean nothing ever touched it. If all $k$ bits are 1, the item is probably in the set, but those bits could have all been set by other items' overlapping hashes, so it might be a false positive.

Worked example

Take $m = 100$ bits and $k = 3$ hash functions, with 10 items already inserted. The fraction of bits still 0 is about $e^{-kn/m} = e^{-0.3} \approx 74\%$. The false-positive rate, probability all $k$ bits for a never-inserted item are 1, is roughly $(1 - e^{-kn/m})^k \approx (0.26)^3 \approx 1.7\%$. Doubling $m$ to 200 bits drops that to about $0.34\%$: more bits, fewer accidental collisions.

What this means in practice

Bloom filters guard expensive lookups: a database checks one before touching disk to see if a key might exist, LevelDB and Cassandra use them to skip SSTables that can't contain a queried key, and a trading system might use one to filter "have I already routed this order ID" before a slower, authoritative check. The false-positive rate is tunable via $m$ and $k$; no tuning removes it entirely, only shrinks it.