The hash table page's whole method needs to keep every key it was ever given — hash it, land in a bucket, and the bucket has to actually hold the key so a later lookup has something to compare against. A Bloom filter throws that away. It answers one narrower question — "have I seen this before?" — using nothing but a fixed-size array of bits and no stored keys at all, and it answers in a fixed amount of memory no matter how many items go in.
Adding an item runs it through k different hash functions, each producing an index into an m-bit array, and sets all k of those bits to 1. Checking an item runs the same k hash functions and looks at the same k bits: if any of them is still 0, the item was definitely never added — no combination of other insertions could have set every one of its bits without setting all of them, so a single 0 is proof. If all k bits are 1, the item is reported as possibly added — every bit it needs happens to be set, but not necessarily because this exact item set them.
That "possibly" is the whole trade. Finitely many bits, infinitely many possible items — the same pigeonhole argument the Rabin-Karp page's hash collisions rest on — so two different items can easily set the same k bits between them, and a third item that was never added but happens to need exactly that combination will read back as present. A Bloom filter can lie and say yes to something absent (a false positive), but it can never lie and say no to something present (no false negative) — bits only ever get set, never cleared, so any bit a real member needs is guaranteed to still be 1 whenever it's checked again later.
Add an item and watch which of the 32 bits light up. Query an item and watch which bits get checked: a plain outline means "checked, was already 1, didn't decide anything by itself"; green means "all k were 1 — might contain"; a dashed red outline marks the one bit that was still 0 and settled the answer as "definitely not."
Six words are preloaded (m = 32 bits, k = 3 hash functions).
Query cat first — genuinely added, reports present. Then query
doe — never added, but every bit it needs happens to already be set by the
others, so it reports present anyway: a real false positive, not a staged one. Then query
duck — also never added, and this time at least one of its bits is still 0, so
it correctly reports absent.
Switch the mode dropdown to counting to turn every slot from a single bit into a small counter, which is enough to make delete sound — usually. Delete cat first: its counters drop, cat correctly reports absent afterward, and fish (which shares one of cat's three slots) is untouched because its own counter is still above zero. Then reload the sample and delete doe instead — the exact false positive from the standard-mode demo above, never really added. The filter has no way to know that: it decrements doe's slots same as it would for any real member, and because doe's three slots are exactly the three slots hog owns, hog now incorrectly reports absent too. A real member, silently broken, by deleting something that was never actually there. See Pitfalls for why this isn't a bug in this demo but an inherent hazard of counting filters.
bits[idx] = 1 at each one. O(k), independent of how many items are
already in the filter.false the moment any bit is 0 (definitely absent), otherwise return
true (possibly present). Also O(k).counts[idx] at each of the k indices instead of clearing a bit.
Still O(k).function fnv1a(s) {
let h = 0x811c9dc5;
for (let i = 0; i < s.length; i++) {
h ^= s.charCodeAt(i);
h = Math.imul(h, 0x01000193);
}
return h >>> 0;
}
function djb2(s) {
let h = 5381;
for (let i = 0; i < s.length; i++) {
h = (Math.imul(h, 33) + s.charCodeAt(i)) >>> 0;
}
return h >>> 0;
}
class BloomFilter {
#bits;
#k;
constructor(m, k) {
this.#bits = new Uint8Array(m);
this.#k = k;
}
// derive k indices from just 2 real hash functions (Kirsch-Mitzenmacher)
#indices(item) {
const s = String(item);
const h1 = fnv1a(s);
const h2 = djb2(s);
const idxs = [];
for (let i = 0; i < this.#k; i++) {
idxs.push(((h1 + i * h2) >>> 0) % this.#bits.length);
}
return idxs;
}
add(item) {
for (const idx of this.#indices(item)) this.#bits[idx] = 1;
}
mightContain(item) {
return this.#indices(item).every(idx => this.#bits[idx] === 1);
}
}
class CountingBloomFilter {
#counts;
#k;
constructor(m, k) {
this.#counts = new Uint8Array(m); // small per-slot counter, not a single bit
this.#k = k;
}
#indices(item) {
const s = String(item);
const h1 = fnv1a(s);
const h2 = djb2(s);
const idxs = [];
for (let i = 0; i < this.#k; i++) {
idxs.push(((h1 + i * h2) >>> 0) % this.#counts.length);
}
return idxs;
}
add(item) {
for (const idx of this.#indices(item)) this.#counts[idx]++;
}
// caller's responsibility to only call this on items truly added — see Pitfalls
remove(item) {
for (const idx of this.#indices(item)) this.#counts[idx] = Math.max(0, this.#counts[idx] - 1);
}
mightContain(item) {
return this.#indices(item).every(idx => this.#counts[idx] > 0);
}
}Only two real hash functions (fnv1a, djb2) generate all
k indices, via h1 + i·h2 for i = 0..k-1 — the standard
trick (Kirsch & Mitzenmacher) for avoiding k genuinely independent hash implementations.
Verified two ways: (1) a from-scratch invariant check — across 16,188 randomized trials varying
m (16-63), k (1-6), and the set of added items, every single added
item reported mightContain === true immediately after being added, zero false
negatives; (2) an empirical false-positive measurement for this exact demo's configuration
(m=32, k=3, the 6 preloaded words) — 200,000 random 3-6 letter lowercase probe
words that weren't in the preloaded six came back true about 4.8% of the time,
broadly in line with (if somewhat under) the standard theoretical estimate
(1 - e^(-kn/m))^k ≈ 8% for n=6 items at this m, k — see
Pitfalls for why this construction runs a bit under that formula's assumption of fully
independent hashes. See /tmp/bloom/ref.js and /tmp/bloom/search.js,
scratch, not committed.
CountingBloomFilter verified two more ways: (1) across 20,000 randomized trials
(m 16-63, k 1-6, random item sets from a 500-word pool), every added
item read back mightContain === true immediately (89,778 individual checks, zero
false negatives) and, separately, adding then removing the same item once always restored the
counter array to exactly its pre-add state (20,000 symmetry checks, zero mismatches); (2) the
two Try It scenarios above — deleting a real member (cat) safely, and deleting a
false positive (doe) that corrupts a real member (hog) — checked
against the exact indices this demo's own words hash to (doe's three slots are the
same set as hog's three slots, verified directly, which is why deleting one
corrupts the other). See /tmp/bloomcount/verify.js and
/tmp/bloomcount/symmetry.js, scratch, not committed.
False positives are inherent, not a bug to fix. Same pigeonhole logic as
Rabin-Karp's hash collisions: with a fixed m-bit array there are only
2^m possible bit patterns, and unboundedly many possible items, so eventually some
never-added item's k bits are all going to already be set by the union of everything else
that's been added. Choosing bigger m or more hash functions k lowers
the false-positive rate, but can't make it zero while keeping the whole point of using
less-than-one-bit-per-key-times-length memory.
No false negatives, but also no delete — in the standard form. Unsetting a bit to "remove" an item would be unsound: that same bit is very likely shared with other items that are still supposed to be present, and clearing it would silently turn one of their bits back to 0 — a real false negative, which is exactly the guarantee this structure exists to never break. Standard Bloom filters simply don't support delete.
The counting variant's delete is only sound if you know the item was really
added. The counting mode above (each slot a small counter,
incremented on add and decremented on delete, absent only once its counter hits 0) fixes the
false-negative-on-delete problem for real members — but it can't fix the deeper issue,
because a Bloom filter still never stores which items are actually present. Deleting
doe in the live demo — a false positive, reporting present but never truly added —
decrements the same three counters a genuine add would have, and those three counters happen to
be exactly the three hog owns: hog, a real, never-deleted member, then
reads back as absent. A counting filter only trades "delete is impossible" for "delete is safe
if and only if you're certain the item is a true member" — and a Bloom filter, by construction,
can never give you that certainty about anything (a mightContain of
true is never proof). In practice this means: only ever call remove
from a caller that tracks true membership somewhere else (like the "added so far" list in this
demo, which a real deployment wouldn't have) — never in response to a bare
mightContain check.
The 2-hash trick can quietly collapse for specific items. Deriving k indices
from just h1 + i·h2 assumes h2(item) mod m isn't 0 — if it is, every
one of that item's k probes lands on the exact same index, and its effective k drops to 1 for
the purpose of discriminating it from other items (it still gets added and still reports present
correctly, no false negative — it just contributes far less spread than the other five items
do). This isn't hypothetical: in the demo's own preloaded data, "crow" has
djb2("crow") mod 32 === 0, verified directly — add it and watch all three of its
probe bits land on the same single index instead of three different ones.
m and k have to be picked ahead of time. Both
depend on how many items you expect to add (n) — the standard formula picks
k = (m/n)·ln 2 to minimize the false-positive rate for a given m and
n. Unlike the hash table's
resize-on-the-fly, a Bloom filter can't grow m after the fact without
re-adding every item from scratch against the new size — which requires still having every item
around somewhere, undercutting the reason to use one in the first place.
Time: both add and mightContain are
O(k), flat — unlike the hash table's O(1) average, which
still depends on chain length staying short, a Bloom filter's cost never grows with how many
items are already in it. Space: a fixed O(m) bits, chosen once up
front from the expected item count and tolerable false-positive rate — independent of the size
of the items themselves and, unlike a hash table's O(n), independent of how many
items actually get added (up to the point where the false-positive rate stops being acceptable).
That fixed, key-free footprint is the entire trade for giving up exactness.
This site's guide, Choosing a Probabilistic Structure, compares this entry against Cuckoo Filter, HyperLogLog, Count-Min Sketch, and Reservoir Sampling — the site's Probabilistic category's fixed-memory unbounded-stream structures — side by side, despite this entry being filed under Hash-Based itself.
This site's other guide, Choosing a Hash Table Collision Strategy, sets this entry aside from the four it actually compares for a different reason again: a Bloom filter never stores a key at all, only a fixed number of bits per possible member, so there's no collision to resolve in the sense that guide means — two keys setting the same bit is the entire mechanism, not a conflict to break.