A Structure That Is Allowed to Be Wrong, in One Direction Only
Every structure in this cluster so far has been exactly right. A hash table finds your key or tells you it is absent; a search tree either holds the value or does not. This one is different: it is allowed to be wrong, and the shape of its wrongness is the entire design.
A Bloom filter answers have I seen this before? without storing anything it has seen. It keeps a row of bits. Each item switches on a few of them, chosen by hashing. To check an item you hash it again and look at those bits: if any is still zero it was definitely never added; if all of them are on it was probably added.
Try to break it
Ten fruits are stored. Twelve others are not. Make it say yes to one of the twelve.
A Bloom filter answers have I seen this before? without storing anything it has seen. It keeps a row of bits; each item switches on a few of them, chosen by hashing. To check an item you hash it again and look: if any of its bits is still zero it was definitely never added, and if all of them are on it was probably added.
That word probably is the whole design. With 10 fruits stored in 32 bits using 2 hashes, the filter answers yes to 5 of 12 words that were never inserted — a 42% false-positive rate. Give it 256 bits and that falls to 0%. It never once gets a stored word wrong, at any setting.
More hashes is not simply better, which surprises most people: at 32 bits, one hash gives 17% false positives and two gives 42%, because each extra hash sets another bit and a small table saturates.
These ten are stored: apple, banana, cherry, date, elderberry, fig, grape, honeydew, kiwi, lemon. Below are twelve that are not. Query them and try to make the filter say yes to one — then look at which bits caused it.
Ask about a word that was never inserted
- Bits set
- 0
- False positive rate
- 0%
- You have found
- 0/0
- False negatives
- 0
The same filter, as text
Stored
Last query
False positives here
When you find one, look at the grid — every bit that word hashes to was already switched on by somebody else. Nothing is corrupted; the filter simply cannot tell whose bits they are.
That is a false positive, and it is not a bug. The filter never stored the word — it stored nothing
at all. Some combination of the ten fruits happened to light up every bit that orange also hashes
to, and from the filter’s point of view those two situations are identical.
Now try a word that comes back no. That answer is not probabilistic. At least one of its bits is still zero, and no stored item could have left it that way, so the word is definitely absent.
The asymmetry, measured
def hashes(item, k, bits):
"""k independent-ish positions from one string, by seeding a simple polynomial hash."""
out = []
for seed in range(k):
h = seed * 31 + 7
for ch in item:
h = (h * 31 + ord(ch)) % 4294967296
out.append(h % bits)
return out
def build(items, k, bits):
table = [0] * bits
for item in items:
for pos in hashes(item, k, bits):
table[pos] = 1
return table
def probably_contains(table, item, k, bits):
return all(table[pos] for pos in hashes(item, k, bits))
STORED = ["apple", "banana", "cherry", "date", "elderberry",
"fig", "grape", "honeydew", "kiwi", "lemon"]
# Words that were never inserted. Any "yes" for one of these is a false positive.
ABSENT = ["mango", "nectarine", "orange", "papaya", "quince", "raspberry",
"starfruit", "tangerine", "ugli", "vanilla", "watermelon", "yuzu"]
print(f"{'bits':>5} {'hashes':>7} {'set bits':>9} {'false positives':>16} {'rate':>7} never a false negative")
for bits in (32, 64, 128, 256):
for k in (1, 2, 3):
table = build(STORED, k, bits)
# The guarantee: everything actually stored must still answer yes.
all_found = all(probably_contains(table, w, k, bits) for w in STORED)
fp = sum(1 for w in ABSENT if probably_contains(table, w, k, bits))
used = sum(table)
print(f"{bits:>5} {k:>7} {used:>9} {fp:>16} {fp / len(ABSENT):>6.0%} {all_found}")bits hashes set bits false positives rate never a false negative 32 1 8 2 17% True 32 2 17 5 42% True 32 3 21 4 33% True 64 1 10 1 8% True 64 2 20 2 17% True 64 3 26 2 17% True 128 1 10 0 0% True 128 2 20 0 0% True 128 3 28 1 8% True 256 1 10 0 0% True 256 2 20 0 0% True 256 3 28 0 0% True
The last column is True on every row. That is not a coincidence of these inputs — it cannot be otherwise. Adding an item only ever turns bits on, and nothing ever turns them off, so a bit that a stored item set stays set forever. A stored item can never fail its own check.
The false-positive column is a dial, not a defect. Thirty-two bits for ten words is 42% wrong; 256 bits is 0%. You choose the rate by choosing the memory, and the interesting part is how little memory buys a usable rate — this filter holds ten words in 256 bits, where storing the words themselves takes about 60 bytes.
More hashes is not monotonically better, which the usual formula-first explanation hides. At 32 bits, one hash gives 17% and two gives 42% — worse, because every extra hash sets another bit and a small table saturates. At 128 bits the ordering flips again: one and two hashes are perfect and three is not. There is an optimum, and it depends on the ratio of bits to items rather than on hashing being good in itself.
Why “definitely no” is worth so much
An answer you can trust in one direction turns out to be enough for a lot of real systems, because of how they use it: the filter goes in front of something expensive, and only the no is acted on.
- A database checks a Bloom filter before reading a disk block. No means skip the read entirely. Yes means do the read, which would have happened anyway.
- A CDN checks one before fetching from origin. A false positive costs one wasted fetch; a false negative would serve wrong content, and cannot happen.
- A browser checks a compact filter of known-malicious URLs before making a network call.
In every case a false positive costs work that was already the fallback, and the guarantee that matters — never wrongly skipping — is the one the structure actually provides. That is the pattern worth taking away: a structure with a one-sided error is useful exactly when one side of the error is cheap.
What this page simplifies
- The hashes are not independent. Real implementations derive k positions properly, often from two good hashes combined. Seeding one polynomial hash k times, as here, correlates the positions and makes the rates slightly worse than theory predicts — which is why the page measures rather than quotes the formula.
- Twelve absent words is not a rate. The percentages are exact for this set and illustrate the trend. A real false-positive rate is measured over a large sample or derived analytically.
- Nothing can be removed. Turning a bit off would break the guarantee for every other item sharing it. Deleting needs a counting Bloom filter, which stores small counters instead of bits and costs several times the memory.
- No resizing. The bit count is fixed when you create it, so you have to estimate the item count in advance. Getting that wrong is the usual way these go bad in production — the rate degrades quietly as more items arrive.