Bloom Filters.

🎯The problem

You have 100M usernames. Before hitting the database on every signup, you want a fast "is this taken?" check in memory. A HashSet works but costs gigabytes. A Bloom filter answers the same question in a tiny fixed-size bit array — at the price of occasional false positives.

The one rule that defines it:

• "No" is always the truth. If it says NOT present, it's 100% not present.
• "Yes" is a maybe. It can lie (false positive), but never the other way.

🔨Build it in 5 lines (Python)

import mmh3            # murmurhash, cheap + fast
bits = [0] * 1000
def add(x):
    for i in range(5): bits[mmh3.hash(x, i) % 1000] = 1
def maybe(x):
    return all(bits[mmh3.hash(x, i) % 1000] for i in range(5))

What each piece teaches:

1. bits — one shared bit array, size m. This is your whole "set". Memory is fixed no matter how many items you add.
2. range(5) — k independent hash functions. Each item flips k bits ON.
3. add — set k bits to 1. Note: you NEVER store the item itself. That's why it's tiny.
4. maybe — item is "present" only if ALL k of its bits are already 1.
5. The lie: another item's bits might have coincidentally turned all k of yours on → false positive. But if even ONE of your bits is 0, that item was definitely never added.

📉The knobs (the intermediate part)

False-positive rate depends on three numbers: m (bits), k (hashes), n (items).

• Too few bits → array fills with 1s → everything looks "present."
• Optimal k ≈ (m/n) × 0.693. More hashes isn't always better; past the optimum you flip too many bits and FP rate climbs again.
• Rule of thumb: ~10 bits per item gives ~1% false positives. 100M items ≈ 120 MB — vs many GB for a real set.

⚠️Common mistakes

• Trying to DELETE by zeroing an item's bits — you'll break other items that share those bits. Standard Bloom filters can't delete (use a Counting Bloom filter).
• Treating "maybe present" as "present" and skipping the real check. The pattern is: filter says no → skip DB (fast path); filter says yes → still verify.
• Using it where a wrong "yes" is dangerous (e.g. "have I already charged this card?"). Wrong tool.

🌍Where it's actually used

Cassandra, HBase, and RocksDB put a Bloom filter in front of each on-disk SSTable, so a read for a missing key skips the disk entirely. CDNs use them for cache checks; browsers historically used them for malicious-URL lookups.

🧪Your exercise

With m=1000 bits and k=5 hashes, roughly how many items can you add before the false-positive rate crosses ~1%? (Hint: ~10 bits per item.) Then: why does adding MORE hash functions eventually make accuracy WORSE, not better?