About Bloom Filters
A Bloom filter is a space-efficient probabilistic data structure that tests whether an element is a member of a set. It can tell you with certainty that an element is not in the set (no false negatives), but may incorrectly report that an element is in the set (false positives).
It uses k independent hash functions to map each element to k positions in a bit array of size m. To insert, set all k bits. To query, check if all k bits are set.
The theoretical false positive rate is (1 - e^(-kn/m))^k where n is the number of inserted elements. The optimal number of hash functions is k = (m/n) * ln(2).
Use cases: web crawlers (avoid revisiting URLs), spell checkers, network routers (packet filtering), database query optimization (avoid disk lookups), blockchain (Bitcoin SPV), caching layers.
Limitation: Standard Bloom filters do not support deletion. Removing a bit could affect other elements sharing that position. Counting Bloom filters replace bits with counters to allow deletion at the cost of more space.