Appearance
Bloom Filters
A Bloom filter answers "have I seen this before?" using a few bits per item, no matter how big the items are. The price is that it sometimes says "maybe" when the true answer is "no", but it never says "no" by mistake.
The idea
In short: keep a row of bits. Adding an item sets a few of them; checking an item looks at the same few.
Say you run a website and want to know whether a username is taken. Storing every username takes memory, and looking one up may need a database call. Instead, keep a row of bits, all starting at zero.
To add a name, run it through a few different hash functions. Each one turns the name into a position in the row. Set those bits to one. To check a name, compute the same positions and look at the bits:
- If any of them is zero, this name was never added. That answer is certain.
- If all of them are one, the name was probably added. Other names may have set those bits by chance.
That row of bits, plus the fixed set of hash functions, is a Bloom filter. The wrong "probably yes" is a false positive. A wrong "no" (a false negative) cannot happen, because adding only ever turns bits on.
How wrong it gets
In short: about 10 bits per item gives roughly a 1% false positive rate. Each extra 5 bits per item cuts the rate about tenfold.
The false positive rate depends on how full the row is. More bits per item means fewer collisions. The number of hash functions is a balance: more of them means more bits to check, but also fills the row faster.
| Bits per item | Best number of hashes | False positive rate |
|---|---|---|
| 5 | 3–4 | about 10% |
| 10 | 7 | about 1% |
| 15 | 10 | about 0.1% |
Compare that with storing the items. A set of 100 million 20-byte keys needs about 2 GB. A Bloom filter for them at 1% needs about 120 MB, whatever the key size.
Going deeper: the formula
With m bits, n items and k hash functions, the false positive rate is about (1 − e^(−kn/m))^k. It is lowest when k = (m/n) · ln 2, which leaves about half the bits set. At that point, the rate is about 0.6185^(m/n), which is where "10 bits per item for 1%" comes from (9.6 bits, to be exact).
You do not need k truly independent hash functions. Computing two hashes and combining them as h1 + i · h2 for i = 0…k−1 works as well in practice (Kirsch and Mitzenmacher, 2006).
Where it is used
In short: in front of anything slow, to skip lookups for things that are not there.
- Databases built on sorted files on disk (Bigtable, Cassandra, RocksDB, and others). Each file keeps a Bloom filter of its keys in memory. A read checks the filter first and skips files that cannot hold the key, which saves most disk reads for missing keys.
- Caches and CDNs. A filter of "URLs requested before" can stop one-off requests from filling the cache: only cache an item the second time it is asked for.
- Network and security tools. Checking a stream of items against a large blocklist, where a "maybe" is followed by an exact check.
The pattern is always the same: a cheap, in-memory "definitely not" that saves an expensive step. A "maybe" falls through to the real check, so false positives cost time, not correctness.
Limits
In short: you cannot delete, you cannot list what is inside, and you must size it up front.
- No delete. Clearing a bit might erase it for other items too. A counting Bloom filter stores a small counter per position instead of a bit, at about 4 times the memory.
- Fixed size. As you add more items than planned, the false positive rate climbs. You rebuild a bigger filter, or chain new filters as old ones fill (a "scalable" Bloom filter).
- No listing. The filter cannot tell you what it contains, only answer about a given item.
If you need deletes, a cuckoo filter (Fan et al., 2014) stores short fingerprints of items instead of bits, supports removal, and uses less space than a Bloom filter at low false positive rates.
Key takeaways
- "No" is certain; "yes" means "probably". Use it to skip work, never as the final answer.
- About 10 bits per item for 1% false positives, independent of item size.
- No deletes and fixed capacity; reach for counting or cuckoo filters if you need more.