Bloom filter

On this page 8

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 rateBits per elementOptimal hash functionsMemory for 1 million items
10%About 4.83About 0.6 MB
1%About 9.67About 1.2 MB
0.1%About 14.410About 1.8 MB
0.01%About 19.213About 2.4 MB
Bits per element and hash count for target false positive rates

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.

VariantChange to the designMain benefitCost
Counting Bloom filterSmall counters instead of bitsSupports deletionAbout 3 to 4 times more memory
Scalable Bloom filterChain of filters with tighter targetsGrows with unknown nSlower lookups across filters
Blocked Bloom filterAll k bits in one cache lineFewer cache missesSlightly higher error rate
Partitioned Bloom filterOne array slice per hash functionEven bit distributionSimilar accuracy, simpler analysis
Common Bloom filter variants

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.

StructureFalse positivesDeletionMemory per elementStores keys
Bloom filterYes, tunableNoAbout 10 bits at 1%No
Hash table or setNoYesFull key plus overheadYes
Cuckoo filterYes, tunableYesOften lower at low error ratesFingerprints only
Xor filterYes, tunableNo, static setAbout 9.8 bits at 1%Fingerprints only
Membership structures compared

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.

SymptomCauseFix
Rising false positivesMore elements than the planned nResize, rebuild or use a scalable filter
Wrong negative resultsHash or seed changed between writes and readsVersion the hash scheme with the filter
Deleted items still reportedBits cleared are shared by other keysUse a counting or cuckoo filter
Uneven bit usageWeak or correlated hash functionsUse well-tested hashes with double hashing
Bloom filter pitfalls and fixes

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.