A Bloom filter is a bit array plus a handful of hash functions that tells you whether an item is definitely not in a set or might be in it. It never stores the items themselves, which is why it’s small, and it never says “no” for something you added, which is why it’s useful. The price is a tunable rate of false “maybe” answers.
Interviewers bring it up in two ways. Sometimes they ask you directly how one works. More often it’s buried in a bigger design: “how does Cassandra avoid reading every SSTable on disk?”, “how would a crawler skip URLs it has already fetched?”, “how do you check username availability without hitting the database on every keystroke?” If you can recognise the shape (a cheap membership test in front of an expensive lookup) and size the filter on the whiteboard, you’re ahead of most candidates.
How the bits work
Start with an array of m bits, all zero, and pick k hash functions. To add an item, hash it k times, take each result modulo m, and set those k bits to one. To query, hash the same way and check the same k positions. If any of them is zero, the item was never added, because adding it would have set that bit. If all of them are one, the item was probably added, but those bits could also have been set by a mix of other items. That collision is the false positive.
Two consequences follow, and interviewers listen for both:
- No false negatives. A filter built correctly can’t forget an item. Saying “it can give false negatives sometimes” is a red flag answer.
- No deletes. Clearing a bit might also clear it for another item that shares the position, which would create a false negative. If you need deletion, you want a counting Bloom filter (small counters instead of bits, four times the memory or more) or a cuckoo filter.
You also can’t list what’s in the filter or count the items exactly. It’s a summary, not a set.
In practice you don’t compute k independent hashes. The usual trick (Kirsch and Mitzenmacher’s double hashing) computes two hashes h1 and h2 once and derives the others as h1 + i * h2. That keeps insert and lookup cost at roughly one hash computation plus k memory reads.
Sizing a filter on the whiteboard
You need two inputs: n, the number of items you expect, and p, the false-positive rate you can tolerate. The standard results are:
- bits:
m = -n * ln(p) / (ln 2)^2 - hash functions:
k = (m / n) * ln 2
A handy shortcut: each tenfold reduction in p costs about 4.8 more bits per item. For 1% you need about 9.6 bits per item and 7 hashes; for 0.1%, about 14.4 bits and 10 hashes. Running the formulas in Node 22 for ten million items gives:
n=10M p=0.01 { m: 95850584, k: 7, bitsPerItem: 9.59, MiB: 11.4 }
n=10M p=0.001 { m: 143775876, k: 10, bitsPerItem: 14.38, MiB: 17.1 }So 11.4 MiB answers “is this one of our ten million usernames?” with a 1% error rate. Storing the usernames themselves in a hash set would take hundreds of megabytes once you count string headers and pointers. That gap is the whole argument for the structure.
A worked example: checking it against reality
Formulas are easy to recite, so it’s worth seeing a filter behave. This is a small implementation using SHA-256 and double hashing. It inserts 100,000 keys into a filter sized for 1%, checks every inserted key, then queries 200,000 keys that were never added.
import { createHash } from 'node:crypto';
function size(n, p) {
const m = Math.ceil(-n * Math.log(p) / (Math.LN2 ** 2));
return { m, k: Math.round((m / n) * Math.LN2) };
}
class Bloom {
constructor(m, k) { this.m = m; this.k = k; this.bits = new Uint8Array(Math.ceil(m / 8)); }
idx(s) {
const h = createHash('sha256').update(s).digest();
const h1 = h.readUInt32BE(0);
const h2 = (h.readUInt32BE(4) | 1) >>> 0; // keep it unsigned
const out = [];
for (let i = 0; i < this.k; i++) out.push((h1 + i * h2) % this.m);
return out;
}
add(s) { for (const i of this.idx(s)) this.bits[i >> 3] |= 1 << (i & 7); }
has(s) { return this.idx(s).every((i) => this.bits[i >> 3] & (1 << (i & 7))); }
}
const n = 100_000, { m, k } = size(n, 0.01);
const b = new Bloom(m, k);
for (let i = 0; i < n; i++) b.add('user:' + i);
let fn = 0; for (let i = 0; i < n; i++) if (!b.has('user:' + i)) fn++;
let fp = 0; const trials = 200_000;
for (let i = 0; i < trials; i++) if (b.has('other:' + i)) fp++;
console.log({ n, m, k, falseNegatives: fn, falsePositiveRate: (fp / trials * 100).toFixed(3) + '%' });Output:
{ n: 100000, m: 958506, k: 7, falseNegatives: 0, falsePositiveRate: '1.004%' }Zero false negatives and a measured 1.004% false-positive rate, right where the formula said it would be. One detail in that code is worth a sentence in an interview: the >>> 0. Without it, JavaScript’s | produces a signed 32-bit integer, so about half the time h2 is negative and the modulo produces negative indexes. A run with that line removed reported 41,594 false negatives out of 100,000. A filter that “sometimes misses items” is almost always a bug like this, not a property of the data structure.
Next, keep adding keys until the filter held 300,000 items, three times what it was sized for, and rerun the same 200,000 negative queries:
after inserting 3x planned items, FP rate 43.56%The false-positive rate didn’t triple, it went from 1% to almost 44%. As the bit array fills, the chance that all k positions are already set rises steeply. This is the most common production failure: someone sizes the filter for launch traffic, the data grows, and the filter quietly stops filtering. Every “maybe” becomes a disk read, and latency climbs with no error anywhere. Track the fill ratio (fraction of bits set) and rebuild or switch to a scalable Bloom filter, which chains new, larger filters as the old one fills.
Where it fits in a design, and where it doesn’t
The pattern is always the same: the filter sits in front of something authoritative and expensive.
LSM-tree storage engines. Cassandra, RocksDB and HBase write data into immutable sorted files. A read for one key might otherwise have to check every file. Each file keeps a Bloom filter of its keys in memory, so the engine skips files that definitely don’t contain the key. Cassandra exposes this as the per-table bloom_filter_fp_chance setting; lowering it buys fewer wasted disk reads for more memory.
Avoiding pointless cache or database misses. If most lookups are for keys that don’t exist (bots probing random IDs, for example), a filter of valid IDs stops them before they reach the database. It’s one defence against cache penetration, where every miss falls through to storage.
Crawlers and “already seen” checks. A crawler with billions of URLs can keep a filter of visited ones. A false positive means skipping a URL you hadn’t fetched, which is acceptable for a crawler and unacceptable for, say, a billing system.
That last point is how you decide. Ask what a false positive costs:
- If a “maybe” just triggers the expensive check you’d have done anyway, a false positive costs one extra lookup. Fine.
- If a “maybe” causes you to skip work (don’t send the email, don’t crawl the page), you’re accepting that some items are wrongly skipped. Say so explicitly, and confirm it’s acceptable.
- If you need exact answers, deletes, or the ability to enumerate members, a Bloom filter is the wrong tool. Use a hash set, a database index, or a cuckoo filter if deletes are the only gap.
A distributed wrinkle comes up in follow-ups: where does the filter live? A per-node in-memory filter is fastest but must be rebuilt on restart and kept in sync. Redis offers Bloom filters among its probabilistic data types (BF.ADD, BF.EXISTS), which centralises the filter at the cost of a network round trip. For username availability, the network hop is still far cheaper than a database query, and the database’s unique constraint stays the final word.
Try it: sizing a username filter
You’re designing the “is this username taken?” check for a sign-up form with 50 million existing accounts. The form calls the check on every keystroke after the third character. How would you use a Bloom filter, how big is it, and what happens on a false positive?
Answer, with the reasoning
Keep a Bloom filter of existing usernames (normalised to lowercase) in the API servers or in Redis. On each keystroke, check the filter first. A “definitely not present” answer means the name is free, and you can show a green tick without touching the database. A “maybe” means you do the real lookup against the indexed users.username column.
Size it for growth, not today. If you plan for 100 million names at 1%, that’s about 9.6 bits per item, or about 114 MiB. If 114 MiB per API server is too much, put it in Redis once, or accept 2% for less memory. Each tenfold drop in error rate costs about 4.8 bits per item, so you can show the trade-off with numbers.
A false positive here costs one database query, which is exactly what you’d have done without the filter, so the user never sees a wrong answer. The filter never gives a false negative for names it contains, but it can be stale: a name registered a second ago may not be in a given server’s copy yet. That’s why the final INSERT relies on a unique constraint, not on the filter. Add new names to the filter on sign-up, rebuild it nightly from the table so deleted accounts eventually drop out, and alert on the fill ratio so it doesn’t silently degrade the way the 3x test did.