Introduction

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.

Try It

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">A Bloom filter with <b>m = 24 bits</b> and <b>k = 3 hash functions</b>.
    Add a word to set its three bits. Query a word to check whether all three are already
    set. It <b>never</b> misses a word you added, but as the array fills it may answer
    "maybe" for a word you never added — a <b>false positive</b>.</p>
<div class="row">
  <input id="word" type="text" placeholder="type a word…" autocomplete="off" />
  <button id="add" type="button">Add</button>
  <button id="query" type="button" class="ghost">Query</button>
</div>
<div class="status" id="status">Add a few words, then query.</div>
<div id="bits" class="bits"></div>
<div class="stats">
  <span>Items added: <b id="nAdded">0</b></span>
  <span>Bits set: <b id="nSet">0</b> / 24</span>
  <span>Est. false-positive rate: <b id="fpr">0%</b></span>
</div>
<div class="row">
  <button id="demo" type="button">Fill with 8 sample words</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// A Bloom filter: m bits, k hash functions. add(x) sets k bits; has(x) is true
// iff all k bits are set. Members are NEVER missed (no false negatives), but a
// non-member can collide on all k bits once the array fills (a false positive).
// False-positive estimate: (1 - e^(-k*n/m))^k  (Bloom, 1970).
const M = 24, K = 3;
let bits = new Array(M).fill(false);
let added = new Set();   // ground truth, only to detect false positives
let nAdded = 0;

// k independent hashes of a string into [0, M). Simple deterministic mixers.
function hashes(s){
  s = s.toLowerCase().trim();
  const out = [];
  for(let i=0;i<K;i++){
    let h = 2166136261 ^ (i*0x9e3779b1);   // distinct seed per hash function
    for(let c=0;c<s.length;c++){
      h ^= s.charCodeAt(c);
      h = Math.imul(h, 16777619);
    }
    out.push(((h>>>0) % M));
  }
  return out;
}

function renderBits(hit){
  const el = document.getElementById('bits'); el.innerHTML='';
  const hitSet = new Set(hit||[]);
  for(let i=0;i<M;i++){
    const d=document.createElement('div');
    d.className='bit'+(bits[i]?' on':'')+(hitSet.has(i)?' hit':'');
    d.textContent=i;
    el.appendChild(d);
  }
}
function nSet(){ return bits.filter(Boolean).length; }
function fpr(){
  // theoretical estimate from m, k and items inserted n
  const n = nAdded;
  const p = Math.pow(1 - Math.exp(-K*n/M), K);
  return (p*100);
}
function refreshStats(){
  document.getElementById('nAdded').textContent = nAdded;
  document.getElementById('nSet').textContent = nSet();
  document.getElementById('fpr').textContent = fpr().toFixed(1)+'%';
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

function add(w){
  w = w.toLowerCase().trim(); if(!w) return;
  const idx = hashes(w);
  idx.forEach(i=> bits[i]=true);
  if(!added.has(w)){ added.add(w); nAdded++; }
  renderBits(idx); refreshStats();
  setStatus(fmt('Added "%w%" — set bits %idx%.', { w: w, idx: idx.join(', ') }),'ok');
}
function query(w){
  w = w.toLowerCase().trim(); if(!w){ setStatus('Type a word to query.','warn'); return; }
  const idx = hashes(w);
  const present = idx.every(i=> bits[i]);
  renderBits(idx);
  if(!present){
    setStatus(fmt('"%w%": definitely NOT in the set (a bit is 0).', { w: w }),'ok');
  } else if(added.has(w)){
    setStatus(fmt('"%w%": maybe present — and it really was added. ✓', { w: w }),'ok');
  } else {
    setStatus(fmt('"%w%": maybe present — but it was NEVER added. FALSE POSITIVE!', { w: w }),'bad');
  }
}

document.getElementById('add').addEventListener('click',()=>{ add(document.getElementById('word').value); document.getElementById('word').value=''; });
document.getElementById('query').addEventListener('click',()=> query(document.getElementById('word').value));
document.getElementById('word').addEventListener('keydown',e=>{ if(e.key==='Enter') document.getElementById('add').click(); });
document.getElementById('demo').addEventListener('click',()=>{
  ['apple','banana','cherry','dragon','eagle','falcon','grape','hazel'].forEach(add);
  setStatus('Filled with 8 words. Now query something new and watch for false positives.','warn');
});
document.getElementById('reset').addEventListener('click',()=>{
  bits=new Array(M).fill(false); added=new Set(); nAdded=0; renderBits(); refreshStats();
  setStatus('Cleared. Add a few words, then query.','');
});
renderBits(); refreshStats();
Result
Console

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.

The Real Trade-off

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)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/me^{-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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/bloom-filters/Content licensed under CC BY-NC 4.0.