Ant colonies recognize their own members by smell — a shared chemical signature every ant in the colony carries, checked constantly at the nest entrance. It’s a fast, cheap test, and it mostly works. But “mostly” is the operative word: certain parasitic ants and their look-alike guests have evolved to chemically mimic that exact signature closely enough to walk straight past the checkpoint, fooling a system that’s been refined by evolution for millions of years¹. The colony’s recognition system isn’t broken — it’s making a real trade-off, and something has found the seam in it.

A Bloom filter makes the same trade on purpose, in software, and — unlike the ants — tells you up front exactly how often it’ll be fooled.

The one-line version

A Bloom filter answers “have I seen this before?” using a small, fixed amount of memory. It can say “definitely not” and be completely correct, or say “probably yes” and occasionally be wrong. It can never do the reverse — it will never tell you “definitely not” about something it actually has seen. That asymmetry is the entire design.

How it works

Picture a strip of a thousand light bulbs, all switched off. To record something, you don’t store what it was — you run it through a handful of different hash functions, each one pointing at a bulb, and switch those bulbs on.

To check whether you’ve seen something before, you hash it the same way and look at the same bulbs. If even one of them is off, you know for certain you’ve never recorded it — if you had, all its bulbs would already be lit, no exceptions. If they’re all on, you’ve probably recorded it. Or, less likely, a few different things happened to light up that exact combination between them, purely by coincidence. That coincidence is the only way this can ever be wrong, and it only ever errs toward “maybe,” never toward “no.”

Nothing is ever stored except the bitmap and the hash functions themselves. There’s no list of what went in, no way to enumerate it later, no way to delete a single entry without risking corrupting some other entry that happens to share a bulb. That’s the whole structure: a strip of bits, and nothing else.

The maths

Start with the simplest possible version of this problem and add complexity only when forced to.

Say the filter has m bits, all off, and one item gets inserted using a single hash function. That function picks one bit, uniformly at random out of m, and switches it on. Now pick any other specific bit — one that insertion didn’t touch. What’s the chance it happens to be the one that got hit? 1/m. So the chance it’s still off is 1 - 1/m.

Insert a second item, same lone hash function. Same logic, independently: the chance our specific bit survives this insertion too is another factor of 1 - 1/m. After n items, each flipping one random bit, the chance that one particular bit is still off is:

(1 - 1/m)^n

Only the first of those two counted so far, for the one-hash-function case. Now generalize to k hash functions per item instead of one, each independently choosing a bit to flip. Every insertion now flips k bits instead of 1, so across n items there are kn total bit-flip attempts, each still landing on our specific bit with probability 1/m. Same reasoning, just more attempts:

(1 - 1/m)^(kn)

That’s the probability one specific bit is still off, after every item has been inserted. There’s a useful simplification available here: for large m, (1 - 1/m)^m behaves like 1/e — the same limit that defines e in the first place, the one calculus courses introduce through compound interest approaching continuous growth. Since the exponent here is kn, rewrite it as m-sized steps repeated kn/m times:

(1 - 1/m)^(kn) = [(1 - 1/m)^m]^(kn/m) ≈ (1/e)^(kn/m) = e^(-kn/m)

So: the probability a specific bit is still off after everything’s inserted comes out to approximately e^(-kn/m). Flip it around — the probability that bit ended up ON is 1 - e^(-kn/m).

Now ask the question that actually matters: what’s the chance of a false positive — a brand-new item, never inserted, whose k hash positions all happen to already be lit by coincidence? Treating each of those k positions as independently lit with probability 1 - e^(-kn/m) — not perfectly true in a real filter, since the same bits get reused across items, but close enough to be useful — the chance all k of them are lit at once is that probability raised to the k-th power:

p ≈ (1 - e^(-kn/m))^k

Nobody handed that down. It’s “one bit stays off,” generalized to k bits per insert, generalized across n inserts, tidied up with a limit, then raised to the power of however many bits have to align for a false hit.

Quick tangent, since coincidences are the whole game here: this is the same reasoning underneath the birthday paradox — the well-known surprise that in a room of just 23 people, there’s better than even odds that two of them share a birthday, despite 365 possible days to choose from. It feels wrong because intuition compares 23 to 365. The real comparison is the number of pairs of people, not the headcount — 23 people produce 253 distinct pairs, and every pair is an independent shot at a match. A Bloom filter runs the identical trick against itself: what actually drives collisions is the number of bit-set attempts (kn of them) landing across m slots, not simply how many items went in. Coincidences pile up faster than headcounts suggest, in both rooms and bit arrays.

Finding the best number of hash functions

With p written as a function of k — holding the filter size m and item count n fixed — two things pull against each other as k grows. More hash functions per item means a false item needs more independent coincidences to line up at once, which makes false positives harder to trigger. But more hash functions also means every true insertion lights up more bits, filling the table faster and raising the baseline chance any given bit is already on. Somewhere between “too few hash functions, too easy to fake a match” and “too many hash functions, table’s already half-lit before you’ve inserted much,” there’s a sweet spot.

Finding it is a calculus problem — differentiate p with respect to k, set the result to zero, solve for k. The algebra is tedious but not deep, and it lands on a clean answer:

k = (m/n) × ln(2) ≈ 0.693 × (m/n)

The ideal hash-function count is just under 70% of however many bits you’ve budgeted per item. Budget 10 bits per item, and the optimum is about 7 hash functions — not by coincidence, that’s RocksDB’s actual factory default, which is exactly why RocksDB’s out-of-the-box configuration lands close to a 1% false-positive rate². The formula and the shipped default agree because the default is the formula, rounded to a whole number of hash functions.

One more thing falls out of this for free, and it’s satisfying enough to be worth showing. Plug that optimal k back into the bit-lit probability from a few steps ago: at k = (m/n) ln(2), the exponent kn/m works out to exactly ln(2), so e^(-kn/m) = e^(-ln 2) = 1/2. Which means at the optimal hash-function count, every bit in the filter has exactly a 50/50 chance of being on — regardless of the target error rate you designed for. A well-tuned Bloom filter is, structurally, a coin flip at the bit level; the error rate comes entirely from how many of those coin flips have to land the same way at once, not from any single bit being more or less likely to be lit.

Substituting that same 1/2 back into p ≈ (1 - e^(-kn/m))^k collapses it to p ≈ (1/2)^k = 2^(-k), and since k = (m/n) ln(2), a little rearranging gives the bits-per-item budget needed for any target error rate:

m/n ≈ -log2(p) / ln(2) ≈ 1.44 × log2(1/p)

Tracing that through a few common targets:

Target false-positive rate	Bits per item	Optimal hash functions (k)
1% (1 in 100)	≈ 9.6	≈ 7
0.1% (1 in 1,000)	≈ 14.4	≈ 10
0.01% (1 in 10,000)	≈ 19.2	≈ 13
0.001% (1 in 100,000)	≈ 24.0	≈ 17

Notice what doesn’t appear anywhere in that table: the size of the item itself. Whether the items are 16-byte UUIDs or full URLs, the bit cost is identical, because nothing about the item is ever stored — only its hash outputs briefly enter the calculation, just long enough to decide which bits to flip. That’s the whole reason a Bloom filter can be dramatically smaller than the set it summarizes: it isn’t a compressed copy of the data, it’s a fixed-size fingerprint of a decision boundary, and drawing that boundary costs the same no matter what’s sitting on either side of it.

Sitting with the asymmetry one more time now that the derivation is in view: every p above describes one specific kind of error only. There’s no equivalent term anywhere in this math for the opposite mistake — a real member of the set testing as absent — because the construction rules that outcome out structurally. Once an item’s bits are set, they stay set forever; nothing that happens afterward can turn one back off. That’s not a rare event the math happens to make unlikely. It’s excluded by how the bits combine, full stop.

Where the idea actually came from

This isn’t a recent trick. Burton Bloom described the structure in 1970³, and his original motivating example had nothing to do with databases or networks — it was hyphenation. Word processors of the era needed to know whether a word could be broken at a given point, and looking that up in a full dictionary for every word in every document was slow and required more memory than was practical at the time. Bloom’s method cut the memory needed for that lookup dramatically — allowing what would have needed a large disk-resident dictionary to instead fit in fast, limited core memory, with a small and tunable chance of getting an answer wrong³. The exact use case is a period piece now, but the trade it made — tolerate rare errors, save most of the space — is the same one every modern use case below is still making.

Where it actually lives today

The most common serious use today is databases skipping disk reads that would come back empty. Storage engines built on LSM-trees — RocksDB, Cassandra, HBase, LevelDB — write data in layered, sorted, immutable files on disk, and a read for a key that doesn’t exist in a given file would otherwise mean an actual disk read that returns nothing. RocksDB attaches a Bloom filter to each of these files specifically so that most “definitely not here” answers get resolved from memory, skipping the disk read for files that provably don’t contain the key².

CDNs use the same trick to decide what’s worth caching in the first place. Akamai found that roughly three-quarters of the objects flowing through its content delivery network were only ever requested once — “one-hit wonders” that took up cache space and disk I/O without ever paying that cost back on a second hit. Their fix, described directly by Akamai’s own engineers, was a Bloom filter tracking which objects had already been seen: an object only gets cached on its second request, not its first, which is enough on its own to keep one-hit content from displacing genuinely popular content⁴.

Idempotence and deduplication are close to the textbook case. Tracking event IDs, request IDs, or message IDs a system has already processed — so retries or duplicate deliveries don’t get handled twice — fits almost perfectly, since the set of seen IDs only grows, gets checked far more often than it gets appended to, and treating an occasional false positive as “already handled” is usually a much smaller problem than storing every ID forever.

Search and spell-check were some of the earliest uses beyond Bloom’s own hyphenation problem: checking whether a typed word is possibly valid before falling back to a real dictionary lookup for the ambiguous cases, since a dictionary is exactly the large, rarely-changing set a Bloom filter is built for. And network hardware uses the same idea at wire speed — packet-processing systems answering “have I seen this flow before” without the memory budget for an exact record of every flow passing through.

The pattern underneath all of it

Every example above shares the same three ingredients: a set that’s large or grows without bound, a membership check that happens far more often than an insert, and an expensive operation downstream that can be skipped entirely when the answer is a confident no. The memory numbers are dramatic, but the real saving is avoiding the disk seek, the network call, the full dictionary scan, the cache write, before ever starting it.

Two questions are honestly worth asking before reaching for one, though. What actually happens on a false positive — is it “occasionally do the expensive check anyway” (fine, close to free), or “silently skip something that should have happened” (worth checking whether that’s actually acceptable, since the error rate can be tuned very low but never to exactly zero)? And do you need to remove something later — because a plain Bloom filter can’t safely unset a single bit, since that bit might be load-bearing for some other entry sharing it. If deletion matters, a counting Bloom filter or a Cuckoo filter solves that, at a modest extra cost in space.

“What happens on a false positive” isn’t just a database concern — plenty of systems outside computing run on the exact same fuzzy-matching logic, with real consequences attached. In 2004, U.S. Senator Ted Kennedy was repeatedly stopped and questioned at airports because his name was too close a match to an alias used by an actual suspect on a federal watchlist — a real, named, well-known person, and it still took his staff and the Department of Homeland Security more than three weeks to sort out the false match⁵. A senator eventually got it fixed with a phone call. Most people flagged by the same kind of fuzzy match don’t have that option — which is exactly the sort of asymmetry worth thinking through before deciding a false positive rate of 1% or 0.1% is “close enough” for whatever you’re building.

References

1. Lenoir, A. et al., “Chemical deception among ant social parasites,” Current Zoology, Oxford Academic — academic.oup.com ↩
2. Facebook/RocksDB Wiki, “RocksDB Bloom Filter” — github.com ↩ ↩
3. Bloom, B.H., “Space/Time Trade-offs in Hash Coding with Allowable Errors,” Communications of the ACM, 13(7), 1970 — dl.acm.org ↩ ↩
4. Maggs, B.M. and Sitaraman, R.K., “Algorithmic Nuggets in Content Delivery,” ACM SIGCOMM Computer Communication Review, 45(3), 2015 — people.cs.umass.edu ↩
5. The Washington Post, “Sen. Kennedy Flagged by No-Fly List” — washingtonpost.com ↩