Bloom Filter Deep Dive

Why it matters

Bloom filters save memory + I/O in caches, DBs. Fundamental probabilistic structure.

The architecture

m-bit array.

k hash functions.

Insert: set k bits.

Query: all k bits set = maybe.

How it works end to end

False positive rate p = (1 - e^(-kn/m))^k.

Optimal k = (m/n) ln 2.

No deletion in basic variant.

Counting Bloom supports deletion.