Why a Bloom filter is only ever sure about "no"
Why a Bloom filter answers only "definitely not" or "possibly", the conditions behind its no-false-negative guarantee, the false positive formula, and why deleting bits breaks it.
A Bloom filter answers “definitely not in the set” or “possibly in it”. Burton Bloom proposed it in 1970, trading a few wrong answers for space.
It is m bits, all 0, and k hash functions. Adding an element sets the k bits its hashes point to. A query says “no” if any of those k bits is 0.
No false negatives
An added element’s k bits were set on insertion. A standard Bloom filter never clears bits, and a query hashes the same way, so it finds them set.
This holds only while the element still belongs to the set, no bit is cleared, and m, k and the hash-to-position mapping are unchanged. By default Python’s hash() salts string hashes unpredictably, so a saved filter positioned with it can fail in another process with another seed.
False positives
A non-member can hit k bits others set. With uniform, independent hashes and n elements, the rate is about f ≈ (1 − e^(−kn/m))^k, smallest at k = (ln 2)·m/n. At m = 8n that is about 5.5; with k = 6,
python3 -c "import math; print((1 - math.exp(-6/8))**6)"prints about 0.0216.
Deletion
Clearing an element’s bits can clear bits another element needs, which then reads “no”. A counting Bloom filter keeps small counters instead, raised on insert and lowered on delete. An overflowed counter pinned at its maximum can still cause a false negative.
Implementations differ: by default Redis adds a sub-filter at capacity.