Bloom filter
On the roadmap:Staff Engineer · step 2: Approximate answers at scale
A compact set that never forgets an item but sometimes claims to have seen one it has not, sized from the item count and error rate you choose.
In plain words
A tiny memory-saving checklist. It can say 'definitely not seen' or 'probably seen'. It never forgets an item you added, but it will sometimes claim to know one it hasn't seen.
Why it matters
Checking a small filter first lets a system skip slow lookups for things that cannot be there. You choose the trade: a smaller filter means more false 'probably' answers.
Where you meet it
- Databases such as Cassandra and HBase, to skip disk reads for missing keys
- Crawlers and feeds, to avoid showing or fetching the same item twice
- Caches, to avoid looking up keys that do not exist
You will be able to
- Size a filter from the number of items and the error rate you accept
- Explain why it has no false negatives
- Say when an exact set is the better choice
In interviews
Shows up in 'seen before?' problems: crawlers, feeds, duplicate checks, username availability.
Practise on the Interview Ready roadmap1Learn the idea first
2See it work before you read the code
3Build it and run the check
What you build
- Size the bit array and hash count from n and p
- Double hashing to derive k positions from two hashes
- add() sets bits, has() checks them
- A measured false-positive rate
function fnv(s: string, seed = 0x811c9dc5): number {
let h = seed;
for (let i = 0; i < s.length; i++) { h ^= s.charCodeAt(i); h = Math.imul(h, 0x01000193); }
h ^= h >>> 15; h = Math.imul(h, 0x2c1b3c6d); h ^= h >>> 12;
return h >>> 0;
}
export class BloomFilter {
readonly bits: number; // m
readonly hashes: number; // k
private data: Uint8Array;
/** n: expected items, p: wanted false-positive rate. */
constructor(n: number, p: number) {
this.bits = Math.ceil((-n * Math.log(p)) / Math.LN2 ** 2);
this.hashes = Math.max(1, Math.round((this.bits / n) * Math.LN2));
this.data = new Uint8Array(Math.ceil(this.bits / 8));
}
private positions(item: string): number[] {
const h1 = fnv(item), h2 = fnv(item, 0x9747b28c) | 1; // odd step so positions differ
return Array.from({ length: this.hashes }, (_, i) => ((h1 + Math.imul(i, h2)) >>> 0) % this.bits);
}
add(item: string): void {
for (const p of this.positions(item)) this.data[p >> 3] |= 1 << (p & 7);
}
/** false = definitely not added; true = probably added. */
has(item: string): boolean {
return this.positions(item).every((p) => (this.data[p >> 3] & (1 << (p & 7))) !== 0);
}
}
Rather run it on your own computer?
Save the code as index.ts and the check as check.ts in one folder. The check exits with an error if anything is wrong and prints bloom-filter ok when everything passes. You need Node.js installed.
mkdir bloom-filter && cd bloom-filter
# save index.ts and check.ts in this folder
npx tsx check.tsHow real systems do it
This lab is the core idea in a small form. Here is what production versions add or do differently.
- Cassandra keeps one filter per data file (SSTable), sized from that file's row count and a chosen false-positive chance, and saves it to disk next to the file. Lowering the chance from 10% to 1% costs roughly three times the memory.
- RocksDB sizes by bits per key: about 10 bits per key gives roughly a 1% false-positive rate, the same rule this lab uses.
- Production filters are often 'blocked': all of a key's bits sit in one cache-line-sized chunk, so a lookup costs one memory miss instead of several. The price is a slightly higher false-positive rate for the same memory.
- Real code uses wider, stronger hashes than this lab's 32-bit one, and newer designs such as Ribbon filters save about 30% of the space for more CPU. A plain Bloom filter cannot delete; counting or cuckoo filters can.
Bloom filter or something else?
| What it tells you | Delete an item? | Can it be wrong? | Memory | Pick it when | |
|---|---|---|---|---|---|
| Bloom filter | Seen before, or not | No | Yes: it can say 'seen' for something new | About 10 bits per item at a 1% error rate | An occasional extra check is cheap |
| Hash set | Exactly which items are in it | Yes | No | The items themselves | You need exact answers and it fits in memory |
| Counting Bloom filter | Seen before, or not | Yes | Yes, like a Bloom filter | Several times a Bloom filter (counters instead of bits) | Items come and go |
| Cuckoo filter | Seen before, or not | Yes | Yes, rarely | Often similar to or smaller than a Bloom filter at low error rates | You need deletes and low error |
| HyperLogLog | How many different items were seen | No | Approximate count | A few kilobytes | You need 'how many', not 'have I seen this' |
| Count-Min Sketch | How often each item was seen | No | Counts can be too high | Small and fixed | You need frequencies, such as the most popular items |
What it cannot do
It cannot remove an item
Deleted or expired items keep their bits on. Use a counting or cuckoo filter, or rebuild the filter now and then.
Its size is chosen up front
Add far more items than planned and false positives climb quickly. Plan the item count, or chain several filters.
A 'yes' is only 'probably'
Never approve something risky on a 'yes' alone. Use it to skip work, and check the real data when it matters.
You cannot list or count what is inside
The items are gone; only bits remain. You cannot get them back or know exactly how many there are.
It needs good, independent hashes
Weak or related hashes give more false positives than the maths promises.
4Now extend it
Each one makes your version closer to what real systems do. Pick one and make the check cover it.
- Add a counting variant so items can be removed
- Rotate several filters to age out old items
- Compare memory with an exact Set of the same items