Overview
A Bloom filter is a space-efficient probabilistic data structure that answers: "Is element X in the set?" It can return:
- Definitely NOT in the set (100% accurate — no false negatives)
- Probably in the set (small chance of false positive)
Used when you need fast membership checks and can tolerate rare false positives but never false negatives.
Architecture
BLOOM FILTER INTERNALS
════════════════════════════════════════════════════════
Bit array of size m=10, k=3 hash functions
ADD "apple":
hash1("apple") = 2 → set bit[2] = 1
hash2("apple") = 5 → set bit[5] = 1
hash3("apple") = 8 → set bit[8] = 1
Bit array: [0, 0, 1, 0, 0, 1, 0, 0, 1, 0]
0 1 2 3 4 5 6 7 8 9
ADD "banana":
hash1("banana") = 0 → set bit[0] = 1
hash2("banana") = 5 → bit[5] already 1
hash3("banana") = 7 → set bit[7] = 1
Bit array: [1, 0, 1, 0, 0, 1, 0, 1, 1, 0]
CHECK "apple":
hash1("apple") = 2 → bit[2] = 1 ✓
hash2("apple") = 5 → bit[5] = 1 ✓
hash3("apple") = 8 → bit[8] = 1 ✓
ALL BITS SET → "probably in set" ✓ (correct)
CHECK "cherry":
hash1("cherry") = 2 → bit[2] = 1 ✓
hash2("cherry") = 5 → bit[5] = 1 ✓
hash3("cherry") = 7 → bit[7] = 1 ✓
ALL BITS SET → "probably in set" — FALSE POSITIVE!
(cherry was never added, but its hash positions happen to be set)
CHECK "mango":
hash1("mango") = 1 → bit[1] = 0 ✗
ANY BIT UNSET → "definitely NOT in set" ✓ (guaranteed accurate)
FALSE POSITIVE RATE:
════════════════════════════════════════════════════════
p ≈ (1 - e^(-kn/m))^k
Where:
k = number of hash functions
n = number of inserted elements
m = size of bit array
For 1% false positive rate with 1M elements:
m ≈ 9.6M bits = 1.2MB (vs 8MB for a hash set of 1M 8-byte IDs)
Practical guide:
m/n = 10 bits per element → ~1% false positive rate
m/n = 14 bits per element → ~0.1% false positive rate
m/n = 20 bits per element → ~0.01% false positive rate
USE CASES WHERE FALSE NEGATIVES ARE UNACCEPTABLE:
════════════════════════════════════════════════════════
✓ Web crawler: "Have we crawled this URL?"
False positive: skip a URL we haven't crawled (minor miss)
False negative: crawl URL again (bad — wastes resources)
✓ Cache miss defense: "Does this key exist in DB?"
False positive: query DB for key that exists elsewhere (cheap miss)
False negative: skip DB query for real key (broken!)
✓ Username dedup: "Is this username taken?"
False positive: tell user taken when it's not (minor UX)
False negative: create duplicate username (broken!)
✗ Not suitable: "Did this payment already process?"
False positive would block valid payment = bad
Use idempotency keys (exact, not probabilistic)
Technical Implementation
Bloom Filter in TypeScript
export class BloomFilter {
private bitArray: Uint8Array;
private readonly size: number;
private readonly hashFunctions: number;
constructor(expectedElements: number, falsePositiveRate = 0.01) {
// Optimal bit array size: m = -n*ln(p) / (ln(2))^2
this.size = Math.ceil(-expectedElements * Math.log(falsePositiveRate) / (Math.log(2) ** 2));
// Optimal hash function count: k = (m/n) * ln(2)
this.hashFunctions = Math.ceil((this.size / expectedElements) * Math.log(2));
this.bitArray = new Uint8Array(Math.ceil(this.size / 8));
}
add(element: string): void {
for (let i = 0; i < this.hashFunctions; i++) {
const position = this.hash(element, i) % this.size;
this.bitArray[Math.floor(position / 8)] |= (1 << (position % 8));
}
}
mightContain(element: string): boolean {
for (let i = 0; i < this.hashFunctions; i++) {
const position = this.hash(element, i) % this.size;
if (!(this.bitArray[Math.floor(position / 8)] & (1 << (position % 8)))) {
return false; // definitely not in set
}
}
return true; // probably in set
}
private hash(element: string, seed: number): number {
// Simple djb2 variant with seed
let hash = 5381 + seed * 31;
for (let i = 0; i < element.length; i++) {
hash = ((hash << 5) + hash) + element.charCodeAt(i);
}
return Math.abs(hash);
}
}
// Usage — web crawler dedup
const crawler = new BloomFilter(10_000_000, 0.001); // 10M URLs, 0.1% FP rate
function shouldCrawl(url: string): boolean {
if (crawler.mightContain(url)) return false; // probably already crawled
crawler.add(url);
return true;
}
Redis Bloom Filter (Production)
// Redis has native Bloom filter via RedisBloom module
// Or use ioredis with BF commands
import { createClient } from 'redis';
const redis = createClient({ url: process.env.REDIS_URL });
// Initialize bloom filter (1M items, 0.1% error rate)
await redis.sendCommand([
'BF.RESERVE', 'crawled-urls',
'0.001', // error rate
'1000000', // initial capacity
]);
// Add URL
async function markCrawled(url: string): Promise<void> {
await redis.sendCommand(['BF.ADD', 'crawled-urls', url]);
}
// Check URL
async function isCrawled(url: string): Promise<boolean> {
const result = await redis.sendCommand(['BF.EXISTS', 'crawled-urls', url]);
return result === 1;
}
// Batch check (more efficient)
async function batchCheck(urls: string[]): Promise<boolean[]> {
const results = await redis.sendCommand(['BF.MEXISTS', 'crawled-urls', ...urls]);
return (results as number[]).map(r => r === 1);
}
Cache Miss Attack Defense with Bloom Filter
// Without bloom filter: malicious requests for non-existent keys hit DB
// GET /users/fake-id-1, GET /users/fake-id-2 ... → 10K DB queries
export class UserRepository {
private bloomFilter: BloomFilter;
async init(): Promise<void> {
// On startup, load all valid user IDs into bloom filter
const allIds = await this.db.query('SELECT id FROM users');
this.bloomFilter = new BloomFilter(allIds.length * 2, 0.001);
allIds.forEach(({ id }) => this.bloomFilter.add(id));
}
async findById(userId: string): Promise<User | null> {
// Fast rejection — definitely not in DB
if (!this.bloomFilter.mightContain(userId)) return null;
// Check cache, then DB
return this.getCached(userId);
}
async create(user: User): Promise<void> {
await this.db.insert(user);
this.bloomFilter.add(user.id); // keep bloom filter in sync
}
}
Interview Preparation
Q: Can you remove an element from a Bloom filter?
Standard Bloom filters cannot support deletion — clearing bits might affect other elements that share those bit positions. Solution: Counting Bloom Filter — instead of bits, store counters. Increment on add, decrement on delete. More memory but supports deletion.
Q: What's the optimal number of hash functions?
k = (m/n) × ln(2), where m = bit array size, n = expected elements. Intuitively: too few hash functions → many bits unset → false positive rate too low but collisions more likely overall; too many → most bits set → everything looks like a match. The formula balances the trade-off.
Q: Where does Google/Meta use Bloom filters?
Google Bigtable: each SSTable has a Bloom filter — before reading an SSTable file from disk, check if the key might exist. Reduces unnecessary disk reads by ~90%. Google Chrome: Safe Browsing uses a Bloom filter to check if a URL is malicious before querying Google's servers. Cassandra: each SSTable has a Bloom filter to skip SSTables that don't contain a key.
Learning Resources
- Bloom Filters — Wikipedia — mathematical foundations
- Redis Bloom — production implementation
- Cassandra Bloom Filters
- Mining of Massive Datasets — Leskovec, Chapter 4