Some operations in memory are astonishingly elegant. One of them is answering, almost for free, a question that at first glance seems expensive: “Is this item in this set?”. For that task there is a probabilistic data structure called a Bloom filter, invented by Burton Bloom in 1970, and today it hides behind databases, caches, browsers and file systems. Its trick: pay a little certainty in exchange for a tiny, constant amount of memory.
The problem of searching a large set
Imagine a cache that stores already-visited URLs, or a database that needs to know whether a key exists before reading from disk. The naive way is to store every key and compare one by one: O(1) with a hash table, yes, but the hash table stores the whole item — the key, its address, collision penalties. When the set holds billions of elements, storing them all weighs too much, and occupying that memory at process startup is unacceptable.
The Bloom filter solves this with a radical twist: it does not store the items; it stores traces of them in a bit array. And even so it can give a useful answer almost all the time.
How it is built: a bit array and several hash functions
A Bloom filter is, in essence, a bit array (a vector of m bits, all set to 0) and k independent hash functions. A hash function is an algorithm that turns arbitrary data into a number; here we use it to choose positions inside the array.
To insert an item: you run it through the k hash functions, each one returns a position within the m bits, and you set those positions to 1. That’s it. To query whether an item exists: you recompute the same k positions and check them. If all are 1, the filter answers “probably yes”. If any is 0, it answers with total certainty “does not exist”.
That “probably yes” is the key to everything: a Bloom filter never yields false negatives (it never says “no” to something that is actually present), but it can yield false positives (say “yes” to something absent, if those positions were set by other elements). The false-positive probability is tuned with m and k, and can be made negligible.
The math that makes it cheap
With n inserted items, m bits and k hash functions, the approximate false-positive probability is (1 − e^(−kn/m))^k. The beautiful part is that it can be sized: if you want an error probability p, the optimal array size is m ≈ −(n·ln p)/(ln 2)² and the optimal number of functions k ≈ (m/n)·ln 2 ≈ 0.69·(m/n).
In plain numbers: for 1 billion items at a 1% error rate, you only need around 9.6 billion bits, roughly 1.2 gigabytes — versus the hundreds of gigabytes the full data would occupy. And the query is always O(k): a handful of hash operations and memory accesses, regardless of how large the set is.
Where you use it without knowing
The Bloom filter is everywhere:
- Databases built on LSM-trees (the write model of Cassandra, RocksDB, LevelDB and ScyllaDB): each on-disk data file carries a Bloom filter in memory. Before reading a block they query the filter; if it says “no”, they skip the disk read entirely — a saving that shows in latency.
- PostgreSQL and its indexes, which combine B-trees with auxiliary structures to speed up lookups without touching every page.
- Browsers such as Chrome in Google Safe Browsing: your browser keeps a local list of hashed dangerous URLs and queries the filter before loading a page; if it says “probably dangerous”, it contacts the server to confirm.
- CDNs and network caches (Nginx uses a Bloom filter for its IP blacklist and to decide whether to serve a cache miss from disk).
- File systems and data deduplication, and in the crypto world, Bitcoin SPV clients used Bloom filters to ask a node for only their relevant transactions.
Limitations and variants
Its great weakness: you cannot delete an item (if you set a bit back to 0 you could break other items sharing that position). For that there are counting Bloom filters, which use counters instead of bits and do allow deletion. Other variants such as the cuckoo filter or the quotient filter allow deletion and even enumeration, at the cost of some added complexity.
There are also scalable versions that grow by chaining smaller filters, and partitioned filters spread across several machines. When memory matters more than perfection, there is almost always a Bloom filter in the background winning back a few hundred microseconds.
The takeaway
The Bloom filter is a reminder that, in computing, probability is not synonymous with irresponsible imprecision: sometimes accepting a measurable, tunable margin of error achieves results that the exact solution cannot afford. That small, well-calibrated lie is what makes your database queries return in milliseconds.
