Bloom Filters

Imagine you run a giant web service and, before every slow database lookup, you want to ask one quick question: "Have I ever seen this item before?" Storing every item you have ever seen would cost a fortune in memory. So you cheat — cleverly.

A Bloom filter, invented by Burton H. Bloom in 1970, answers that question using a tiny array of bits. It can hold the memory of millions of items in kilobytes. The price for this magic is a peculiar kind of honesty: when it says "no, never seen it," it is always right. When it says "yes, probably seen it," it might be wrong — a false positive.

That one-sided error is not a bug. It is the whole design. A structure that is allowed to occasionally say a confident, harmless "yes" can be astonishingly small — and that trade between space and certainty is one of the most useful bargains in computing.

Below is a Bloom filter with a small bit array and three hash functions. Add a word and watch three bits light up. Query a word and the filter checks whether all three of its bits are already set — if so, it answers "maybe present."

<p class="hint">{{hint}}</p>
<div class="row">
  <input id="word" type="text" placeholder="{{placeholder}}" autocomplete="off" />
  <button id="add" type="button">{{btn_add}}</button>
  <button id="query" type="button" class="ghost">{{btn_query}}</button>
</div>
<div class="status" id="status">{{status_initial}}</div>
<div id="bits" class="bits"></div>
<div class="stats">
  <span>{{label_items_added}}: <b id="nAdded">0</b></span>
  <span>{{label_bits_set}}: <b id="nSet">0</b> / 24</span>
  <span>{{label_fpr}}: <b id="fpr">0%</b></span>
</div>
<div class="row">
  <button id="demo" type="button">{{btn_demo}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.row { display: flex; gap: .5rem; flex-wrap: wrap; margin: .5rem 0; }
input { flex: 1 1 160px; min-width: 140px; font: 500 14px system-ui, sans-serif;
        padding: .45rem .6rem; border: 1px solid #adb1b8; border-radius: 8px; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.warn { color: #b8860b; }
.bits { display: grid; grid-template-columns: repeat(12, 1fr); gap: 4px; margin: .6rem 0; }
.bit { aspect-ratio: 1; display: flex; align-items: center; justify-content: center;
       font: 700 11px ui-monospace, monospace; border-radius: 6px;
       background: #e8eef3; color: #9aa7b3; border: 1px solid #cdd9e3; transition: all .15s; }
.bit.on { background: #1d3557; color: #fff; border-color: #14253d; }
.bit.hit { box-shadow: 0 0 0 3px #ffd34d; }
.stats { display: flex; gap: 1rem; flex-wrap: wrap; font-size: .88rem; color: #444; margin: .4rem 0; }
.stats b { color: #1d3557; }

// Code not found

Notice the asymmetry. If a word was truly added, its bits are guaranteed to be set, so the filter never misses it — no false negatives. But as you keep adding words, more and more bits turn on, and eventually a word you never added can have all three of its bits already lit by other words. That is a false positive, and the demo tracks how its likelihood rises as the array fills.

What does a Bloom filter actually cost, and what does it buy?

• Speed. Both adding and querying take a fixed number of hash computations — $O(k)$ time, independent of how many items are stored. There is no list to scan.
• Space. Instead of storing the items, you store m bits. A well-tuned filter needs only about 10 bits per item for a 1% error rate — orders of magnitude less than the items themselves.
• One-sided error. A query for a stored item is always correct ("maybe present"). A query for a missing item is usually correct ("definitely absent") but can mistakenly say "maybe present." No false negatives, some false positives.
• The formula. With m bits, k hash functions and n inserted items, the false-positive probability is about (1 − $e^{-kn/m}$)ᵏ. It climbs as n grows — the fuller the array, the more often unrelated items collide on all k bits.

That last point is the heart of it: a Bloom filter never forgets something it stored, but its confidence in "no" erodes gracefully as it fills. You choose m and k up front to keep the error wherever you can tolerate it — a deliberate, tunable bargain rather than a flaw.

"Skip the expensive check when the answer is almost certainly no" is a pattern that shows up everywhere, and the Bloom filter is its workhorse:

• Databases. Systems like Cassandra and Bigtable keep a Bloom filter per data file so a query can avoid touching files that definitely don't contain the key — turning many disk reads into none.
• Web caches and CDNs. A filter quickly rules out URLs that have never been cached, avoiding a slow lookup for content that isn't there.
• Spell-checkers and password screening. A compact filter of "known words" or "leaked passwords" answers membership instantly, in memory.
• Networking and cryptocurrencies. Routers and lightweight Bitcoin clients use Bloom filters to decide which packets or transactions might be relevant without storing the whole set.

Understand the Bloom filter and you've grasped the broader art of approximate answers — the same spirit that lets hashing and randomized algorithms beat problems that exact methods, like P vs NP, find punishing.

The Bloom filter hides an elegant idea: you don't always need to store something to remember it. A handful of hash functions and a strip of bits can recall the gist of an enormous set — never forgetting a true member, and admitting only a rare, controllable false alarm.

So the next time a system answers "I've definitely never seen that" in an instant, or shrugs "I might have — let me check properly," you'll know the bargain underneath. It isn't being careless; it's spending a sliver of certainty to buy a mountain of memory, and doing the arithmetic to know exactly how much.