Bloom Filter
A space-efficient probabilistic data structure that tells you if an element is 'possibly in the set' or 'definitely not in the set.' Used by databases to avoid expensive lookups.
What is Bloom Filter?
In short
A Bloom filter is a space-efficient probabilistic data structure that answers one question about set membership: an element is either "definitely not in the set" or "possibly in the set." It can return false positives but never false negatives, which lets systems skip expensive disk reads or network calls for items that are guaranteed to be absent.
What a Bloom Filter Actually Is
A Bloom filter is a bit array of fixed size paired with a handful of hash functions. Every bit starts at 0. The structure does not store the elements themselves, only a fingerprint of which bits each element touches. That is why it is so small: a filter holding 1 million items at a 1 percent false positive rate needs about 1.2 MB, while storing the actual keys would take tens of megabytes or more.
Because it stores no keys, a Bloom filter cannot list its contents, cannot delete an element from a standard implementation, and cannot tell you exactly which items are present. It only answers membership questions, and it answers them with a deliberate asymmetry. A "no" is always trustworthy. A "yes" means "probably, go check the real source."
The whole point is to act as a cheap front gate. You ask the filter first. If it says no, you stop and save the cost of a real lookup. If it says yes, you do the expensive lookup as a fallback.
How It Works Under the Hood
To add an element, you run it through k independent hash functions. Each hash produces an index into the bit array, and you set those k bits to 1. Adding the string "alice" with three hash functions might set bits 4, 19, and 88.
To test for membership, you hash the element the same way and check whether all k of those bits are 1. If even one of them is still 0, the element was never added, so the answer is a definite no. If all k bits are 1, the answer is "possibly yes" because those bits could have been set to 1 by a combination of other elements.
That collision risk is the source of false positives. As you add more elements, more bits flip to 1, and the chance that an unrelated query happens to hit all-ones rises. The false positive rate is tunable: pick the array size m and the hash count k for your expected element count n. The optimal number of hashes is roughly k = (m/n) times ln(2), and adding more memory drives the error rate down fast.
Standard Bloom filters do not support deletion, because clearing a bit might undo bits shared with other elements. Variants exist to handle this. A counting Bloom filter replaces each bit with a small counter so items can be removed, and a scalable Bloom filter grows new layers as the dataset expands beyond the original sizing.
When to Use One and the Trade-offs
Reach for a Bloom filter when a definite "no" is cheap to act on and the real lookup is expensive. The classic case is avoiding disk seeks: before reading a large file on disk or a remote object, ask the filter whether the key could possibly be there. Most negative queries get rejected in memory in nanoseconds.
The trade-off is that you accept a small rate of false positives in exchange for huge memory savings and constant-time queries. You must size the filter up front against your expected element count. Overfill it and the false positive rate climbs toward useless; oversize it and you waste memory you were trying to save.
Do not use a Bloom filter when you need exact answers, when you need to enumerate or delete elements freely, or when the underlying lookup is already cheap. In those cases a plain hash set or the database itself is simpler and correct. A Bloom filter only pays off when the cost of the avoided work dwarfs the cost of the occasional wasted check caused by a false positive.
A Concrete Real-World Example
Consider a log-structured merge tree, the storage engine behind Cassandra, RocksDB, and LevelDB. Data lives in many immutable files called SSTables, sorted on disk. To read a key the engine may have to check several SSTables, and each check is a disk read.
Each SSTable carries a Bloom filter of the keys it contains, held in memory. On a read, the engine asks each filter first. If a filter says the key is definitely not in that SSTable, the engine skips the file entirely and never touches the disk for it. Only when a filter says "possibly" does the engine pay for the actual seek.
For a key that does not exist at all, which is common in write-heavy systems, this turns a multi-file disk scan into a few in-memory bit checks. The occasional false positive costs one needless seek, which is a tiny price next to the disk reads avoided on every true negative.
Where it is used in production
Apache Cassandra
Keeps a Bloom filter per SSTable so reads skip on-disk files that cannot hold the requested key.
Google Bigtable
The original LSM design that popularized per-SSTable Bloom filters to cut disk seeks on negative lookups.
RocksDB and LevelDB
Embedded key-value stores that attach Bloom filters to data blocks to avoid reading blocks that lack a key.
Medium
Uses Bloom filters to quickly skip articles a user has already seen when serving recommendations.
Frequently asked questions
- Can a Bloom filter give a wrong answer?
- Only in one direction. It can produce a false positive, saying an element might be present when it is not, but it never produces a false negative. If it says an element is absent, that is always correct.
- Why can't you delete from a standard Bloom filter?
- Each element sets several shared bits, and different elements can set the same bit. Clearing a bit to remove one element might also remove bits another element depends on, breaking it. A counting Bloom filter, which uses small counters instead of single bits, supports deletion.
- How do you control the false positive rate?
- By sizing the bit array and the number of hash functions against the expected number of elements. More memory and a well-chosen hash count lower the error rate. A common target is 1 percent, which needs about 9.6 bits per element.
- How is a Bloom filter different from a hash set?
- A hash set stores the actual keys, gives exact answers, and supports listing and deletion, but uses far more memory. A Bloom filter stores no keys, uses a fraction of the space, and trades exactness for the occasional false positive.
- Is a Bloom filter slower as it fills up?
- No. Lookup and insert time stay constant at k hash computations regardless of how many elements you add. What degrades is accuracy: the false positive rate rises as more bits get set to 1.
Learn Bloom Filter hands-on
This page explains the idea. The full lesson lets you step through the ring as servers join and leave, read the implementation, and check yourself with a quiz. It is one of 760+ lessons in the System Design Masterclass, from your first API call to distributed consensus. Eleven Foundation lessons are free, no signup. Lifetime access is ₹499 in India or $7.99 worldwide, one payment, no subscription.
Related lessons
Lessons that touch on Bloom Filter as part of a larger topic.
See also
Related glossary terms you might want to look up next.
Caching
Storing frequently accessed data in a faster storage layer so you don't have to fetch it from the original (slower) source every time.
Index
A data structure that speeds up database lookups. Like the index at the back of a book that lets you jump to the right page instead of reading every page.
Database
An organized collection of data that can be easily accessed, managed, and updated. The backbone of almost every application.
CAP Theorem
In a distributed system, you can only guarantee two of three: Consistency, Availability, and Partition tolerance. You must choose your trade-off.
Consensus
The process of getting multiple nodes in a distributed system to agree on a single value. The foundation of distributed databases and coordination services.
Paxos
A family of protocols for solving consensus in unreliable networks. Famously difficult to understand but mathematically proven correct.