The Bloom Filter Idea

A Bloom filter is a probabilistic set with two operations: add(x) and contains(x).

• contains(x) returns either NO (definitely not in the set — no false negatives) or MAYBE (probably in the set, with a tunable false-positive rate).
• The trick: a bit array of m bits and k independent hash functions.

add(x) sets the k bits at positions h_1(x) % m, h_2(x) % m, ..., h_k(x) % m.

contains(x) returns MAYBE iff ALL k of those bits are 1. If even one is 0, the item was never added — so NO is exact.

Why this is useful

Bloom filters trade exactness for memory: ~10 bits/item gives a 1% false-positive rate. A million items fits in 1.2 MB. A hash set of the same items would need 50-100 MB.

The classic use is as a pre-filter for an expensive lookup:

def get(key):
    if not bloom.contains(key):
        return None              # NO is exact — skip the disk/network entirely
    val = expensive_lookup(key)  # MAYBE: confirm with the real store
    return val

False positives just cost an occasional unnecessary lookup. No false negatives means you never wrongly skip.

What's coming

In this lesson you'll implement the bare-bones version with m=64 bits, k=2 hash functions, and two hand-traceable hashes so you can verify the bit array by inspection. Later lessons add: the optimal-parameter math, the Kirsch-Mitzenmacher double-hashing trick, a self-tuning filter, deletion (Counting Bloom), unknown-N support (Scalable Bloom), set operations, the Cuckoo filter, and production monitoring.