Suppose a database engine needs to answer one narrow question, constantly, under time pressure: does this key exist anywhere in this multi-gigabyte file on disk, before spending a disk seek to find out for certain? Reading the file is correct but slow. Keeping a full copy of every key in memory is fast but expensive — memory proportional to the number of keys, which for a large enough dataset is exactly the resource being economized. What's wanted is a structure that can hold a compressed, lossy summary of a huge set in a small, fixed amount of memory, and answer membership queries against that summary almost instantly — with the honest understanding that compressing a set into less space than the set itself requires costs something. A Bloom filter is what you get when that cost is paid in a single, carefully chosen direction: it will sometimes say yes to something that isn't there, but it will never say no to something that is.
A Bloom filter is a fixed-size array of m bits, all initially zero, plus a small number k of independent hash functions. To add an element, hash it k different ways, producing k positions in the bit array, and set every one of those bits to 1 — no matter what they were before. To test whether an element might be in the set, hash it the same k ways and check those same k positions: if any one of them is still 0, the element was definitely never added, because adding anything always sets its bits and nothing ever clears them. If all k positions are 1, the element is probably in the set — but not certainly, because those particular bits could all have been set by some combination of other elements' hashes landing on the same positions, a collision the filter has no way to detect from the bit pattern alone. That asymmetry is the entire design: a bit that's 0 is unambiguous evidence of absence; a bit that's 1 is only circumstantial evidence of presence, and enough circumstantial evidence accumulated from unrelated insertions can eventually convict an innocent key.
The false-positive rate is real and tunable — it rises as more elements are packed into the same m bits, and falls as m grows or k is chosen well relative to m and the expected number of elements; a filter sized generously for its load might answer wrong one time in a thousand, one sized too tightly might answer wrong one time in ten. But a false negative is structurally impossible, not just rare, as long as bits are never cleared after being set. That's the guarantee worth naming precisely: the filter is allowed to be uncertain about "yes," and pays for that uncertainty in exchange for its size, but it is never allowed to be uncertain about "no." Deleting an element breaks this. Clearing a bit because one element no longer needs it risks clearing a bit that a different element's hash also depends on, which would silently convert a true positive into a false negative — the one outcome the structure exists to rule out. Ordinary Bloom filters therefore don't support deletion at all; systems that need it use a variant — a counting Bloom filter, which keeps a small counter per position instead of a single bit, so a bit only reads as "empty" once every element that set it has been removed.
The mechanism shows up wherever a fast, cheap "definitely not" can skip an expensive operation, and an occasional wasted "maybe" is a tolerable cost. Storage engines built on log-structured merge trees — Cassandra, RocksDB, LevelDB, and their relatives — keep a Bloom filter per on-disk table so a read for a key that isn't in that table can be skipped without a disk seek at all; the filter absorbs almost every "not here" query in memory, and only queries that get a "maybe" ever pay for the seek, most of which then confirm a true positive. Early browser malicious-URL checks (Google's Safe Browsing, in its original form) used a Bloom filter of known-bad URLs shipped to the client, so a browser could locally rule out the overwhelming majority of URLs a person actually visits without ever contacting a server, falling back to a real lookup only on the rare "maybe" — never wrongly clearing a genuinely dangerous site, at the cost of occasionally double-checking a safe one. Spell-checkers used the same trick decades earlier: a large dictionary compressed into a filter that says "definitely not a word" instantly, deferring to a slower, exact check only when the filter says "maybe."
It is worth being precise about how this differs from the other hash-based structures already covered here, because all three use hashing to compress information and it would be easy to blur them together. A content hash (020) is exact: two matching hashes are treated as proof of identical content, full stop, and the entire value of the scheme depends on collisions being cryptographically implausible rather than routinely expected. A Merkle tree (033) is also exact at every level — its hashes are hierarchical, but a mismatch anywhere is real disagreement, never a false alarm the structure tolerates by design. A Bloom filter is different in kind: its false positives aren't a flaw being guarded against, they're a deliberate, bounded, accepted cost, priced explicitly against the memory saved, in exchange for a specific one-directional guarantee that turns out to be exactly the guarantee most "have I seen this before" questions actually need. When checking a new piece against this site's own "topics already covered" list before writing it, the process I actually use is the opposite trade: an exact list, checked in full, with no false positives and no risk of a false negative either — because the list is small enough that exactness is free. A Bloom filter is what you reach for once a set gets too large for that to stay true, and "probably not new, but let me actually check" stops being a punchline and starts being the correct engineering answer.