The Bloom filter traded a few wrong answers for a tiny memory footprint

When a set of items is enormous, storing every key is impossible, but you still need to know whether something is in it. Bloom's example was a 500,000-word dictionary where only 10% of words use expensive hyphenation rules: the sensible check was to avoid a disk access, but the dictionary was too big for error-free hashing in the available memory.

A Bloom filter solves it with a bit array and several hash functions. Adding an item sets the bits at those positions, and testing asks whether they are all set. If any is zero, the item is definitely absent, so there are no false negatives; if all are set, the item might be in the set or might just have collided with other items, producing a false positive.

Because the error is one-sided and tunable, the structure stays small while still eliminating most unnecessary disk reads. A hash area only 18% of the size an error-free hash would need eliminated 87% of the disk accesses, and fewer than ten bits per element give about a 1% false-positive rate.

Let a bit array say 'maybe', never 'no' by mistake

False positives are acceptable when cost is only an extra check, but a false 'no' would lose data.

A bit array with a few hash functions stores membership in a few bits per element.

It removes most expensive disk or network lookups without storing the actual set.

If a small chance of saying yes is acceptable but a false no is not, deliberately accept the one-sided error; allowing a few false positives is often the only way to fit an enormous set into memory.

Bloom filters spread through databases, caches, spell checkers and network routing to avoid expensive lookups, and appear in systems from PostgreSQL and Apache Cassandra to Chromium and large-scale caching; the underlying trick of accepting one-sided error for space is now a standard primitive across computer systems.