Bloom Filters

Probabilistic Membership

1:00

A Bloom filter answers "is this element in the set?" with a fixed tiny bit array — guaranteeing no false negatives while accepting a tunable rate of false positives.

By the end, you can

Explain the one-sided guarantee: why false positives are possible but false negatives are impossible.
Trace an insert by identifying which k bit positions are set and verifying bit sharing.
Trace a query and determine whether the result is "definitely not in set" or "possibly in set".
Identify a false positive by showing all of a non-member's hashed bits were set by other elements.
Explain why deletion is unsafe and describe how counting/cuckoo filters address it.
Interpret the FPR formula and reason about how n, m, and k affect false-positive probability.
Apply the 9.6 bits/element rule of thumb and the ÷10 FPR gain per 4.8 extra bits.
State the O(k) time and O(m)-bit space complexity and explain why space is key-size independent.
Give concrete examples of where Bloom filters are used (Cassandra, caches, CDNs).

Up next in Trees, Hashing & Graphs