Bloom Filter
A probabilistic set: tests "definitely not present" or "maybe present" in O(k) time and O(1) space per element — no false negatives, a tunable rate of false positives, and it can never report an item that was never added.
A Bloom filter is a bit array of size m plus k independent hash functions. Adding an element hashes it k ways and sets those k bits. Testing membership hashes the same way and checks whether all k bits are set: if any is 0, the element was definitely never added; if all are 1, it probably was — but different elements can coincidentally set the same bits, causing a false positive.
The false-positive rate is tunable by choosing m and k relative to the expected number of elements n: too small a bit array and it fills with 1s, driving false positives toward 100%; too large wastes memory. There is no way to remove an element (clearing bits could un-set another element's membership) without a counting variant.
Its value is checking "maybe" cheaply before paying for an expensive "for sure": a database skips a disk read if the Bloom filter says a key is absent, a web crawler skips a URL it has probably already visited, a spell-checker flags a word as possibly misspelled before a full dictionary lookup.
Operations
| Operation | Complexity |
|---|---|
| add(x) | O(k) hashes |
| mightContain(x) | O(k) hashes |
| false negatives | never |
| false positives | tunable, > 0 |
Where it's used
Database read-avoidance (LSM-trees, Cassandra, BigTable), web crawlers (visited-URL check), spell-checkers, network routers (packet deduplication).