A Bloom filter is a space-efficient probabilistic data structure that answers the question “is this element in the set?” with either “definitely not” or “probably yes”. Among data structures used in programming, it trades a small, controllable false positive rate for memory use that is far below that of a hash table or a set storing the elements themselves.
The structure was described by Burton Howard Bloom in 1970. It never produces false negatives, which makes it ideal as a fast pre-check in front of a slower, authoritative lookup such as a disk read, a database query or a network request.
How a Bloom filter stores membership
A Bloom filter consists of a bit array of m bits, all initially zero, and k independent hash functions that each map an element to one array position. To insert an element, the filter computes all k hashes and sets the corresponding bits to one. The element itself is never stored.
To query an element, the filter computes the same k positions. If any of those bits is zero, the element was certainly never inserted. If all k bits are one, the element is probably present, because other insertions may have set the same bits by coincidence. That coincidence is the source of every false positive.
In practice, implementations rarely run k fully separate hash functions. The double hashing technique derives all k positions from two base hashes, for example with fast non-cryptographic functions such as MurmurHash or xxHash, with no measurable loss in accuracy.
Sizing parameters and false positive rate
Accuracy depends on three parameters: the number of bits m, the number of inserted elements n and the number of hash functions k. The false positive probability is approximately (1 - e^(-kn/m))^k, and the optimal number of hash functions is k = (m/n) ln 2, at which roughly half of the bits are set.
At the optimum, the memory needed per element depends only on the target error rate: about 1.44 times log2(1/p) bits per element. The table shows typical sizing values for common targets.
| Target false positive rate | Bits per element | Optimal hash functions | Memory for 1 million items |
|---|---|---|---|
| 10% | About 4.8 | 3 | About 0.6 MB |
| 1% | About 9.6 | 7 | About 1.2 MB |
| 0.1% | About 14.4 | 10 | About 1.8 MB |
| 0.01% | About 19.2 | 13 | About 2.4 MB |
The figures reveal the central trade-off: each additional 4.8 bits per element cuts the false positive rate roughly tenfold. Inserting more elements than planned degrades accuracy quickly, because the fill ratio of the bit array rises and more queries hit only set bits.
Variants that extend the basic design
The classic structure supports only insertion and lookup, so several variants address its limitations. The most common ones change how bits are stored or how the filter grows.
| Variant | Change to the design | Main benefit | Cost |
|---|---|---|---|
| Counting Bloom filter | Small counters instead of bits | Supports deletion | About 3 to 4 times more memory |
| Scalable Bloom filter | Chain of filters with tighter targets | Grows with unknown n | Slower lookups across filters |
| Blocked Bloom filter | All k bits in one cache line | Fewer cache misses | Slightly higher error rate |
| Partitioned Bloom filter | One array slice per hash function | Even bit distribution | Similar accuracy, simpler analysis |
Bloom filter compared with related structures
A Bloom filter answers only membership questions, so it competes with structures that either store keys exactly or approximate membership differently. The right choice depends on whether deletion, exact answers or minimal memory matter most.
| Structure | False positives | Deletion | Memory per element | Stores keys |
|---|---|---|---|---|
| Bloom filter | Yes, tunable | No | About 10 bits at 1% | No |
| Hash table or set | No | Yes | Full key plus overhead | Yes |
| Cuckoo filter | Yes, tunable | Yes | Often lower at low error rates | Fingerprints only |
| Xor filter | Yes, tunable | No, static set | About 9.8 bits at 1% | Fingerprints only |
Unlike a hash table, a Bloom filter cannot enumerate its contents or return associated values. Its benefit is that it stays small enough to fit in memory or CPU cache when the authoritative data set does not.
Where Bloom filters are used in practice
Bloom filters appear wherever a cheap negative answer avoids an expensive operation. Typical deployments sit in front of disks, networks or remote services.
- LSM-tree storage engines such as RocksDB, Apache Cassandra and HBase keep one filter per sorted file to skip disk reads for absent keys.
- Content delivery caches use filters to avoid storing objects requested only once, the so-called one-hit wonders.
- Distributed joins send a compact filter of join keys to other nodes so they discard nonmatching rows early.
- Spell checkers and blocklists test words or URLs locally before a slower exact check.
Common mistakes and failure modes
Most production problems come from wrong sizing assumptions or misuse of the probabilistic answer. The table links typical symptoms to their causes.
| Symptom | Cause | Fix |
|---|---|---|
| Rising false positives | More elements than the planned n | Resize, rebuild or use a scalable filter |
| Wrong negative results | Hash or seed changed between writes and reads | Version the hash scheme with the filter |
| Deleted items still reported | Bits cleared are shared by other keys | Use a counting or cuckoo filter |
| Uneven bit usage | Weak or correlated hash functions | Use well-tested hashes with double hashing |
The most serious design error is treating “probably yes” as a confirmed match. A Bloom filter must always be backed by an authoritative check whenever a false positive would cause incorrect behavior.
Understanding it simply
A Bloom filter is like a doorman with a short list of marks instead of a full guest list. If your marks are missing, the doorman knows for sure you are not invited. If all your marks are there, you are probably on the list, but the doorman may occasionally be fooled.
Programs use this quick check to avoid slow searches for things that do not exist. It takes very little memory, and the small chance of a wrong “yes” is handled by a careful second check.
Applied in practice
A database team runs a key-value store on an LSM-tree engine holding about 500 million keys spread across hundreds of sorted files on disk. Many requests ask for keys that do not exist, and each such lookup used to touch several files before returning an empty result.
The team configures a Bloom filter of 10 bits per key for every file, which keeps the false positive rate near 1 percent and uses roughly 600 MB of memory in total. Lookups for absent keys now skip almost every disk read, and median read latency for those requests falls sharply while the server handles noticeably more queries per second.