A Bloom filter is a probabilistic data structure that answers a very specific question - have I seen this thing before? - while using almost no memory.
A Bloom filter is a probabilistic data structure that answers a very specific question - have I seen this thing before? - while using almost no memory.
There is a trade-off, though - bloom filters can be ‘wrong’. A Bloom filter will never tell you something is absent when it is actually present, but it might occasionally claim something exists when it does not.
In this essay, we explore Bloom filters end-to-end, from fundamental concepts to advanced variants like counting and deletable Bloom filters, the nuances of hash functions, and real-world benchmarks and use-cases.
Say, you are building a recommendation engine for a content platform with millions of users. Each user has seen thousands of articles. When generating recommendations, you need to filter out articles the user has already seen.
Storing every article ID for every user in a hash set would consume enormous amounts of memory. Let’s crunch the numbers…
Assumptions:
10 million active users
Each user has seen an average of 5,000 articles
Article IDs are 64-bit integers (8 bytes each)
Storing article IDs directly in a hash set:
Plain text
That is 800 GB of RAM just for tracking which articles users have seen. Even with a more optimistic 1.5x overhead factor, you are looking at 600 GB.
Bloom Filter will take up about ~60GB (one-tenth) of space by not storing actual article IDs, but rather storing the existence in a compact bit array that can answer the question:
has this user probably seen this article?
If the answer is no, you can confidently recommend it. If the answer is yes, you either skip it or do a more expensive lookup to confirm. In practice, this cuts memory usage by more than 90% without slowing down recommendation generation.
Variations of this idea show up in many large systems - Medium uses it in recommendations, Chrome uses it to flag unsafe URLs, and databases rely on Bloom filters to avoid unnecessary disk reads.
The Fundamental Structure
A Bloom filter consists of two components: a bit array of m bits, all initially set to zero, and a collection of k independent hash functions. Each hash function maps an arbitrary input to one of the m array positions.
To add an element to the filter:
Plain text
To check if an element might exist in the filter:
Plain text
If any bit at the computed positions is zero, the element was definitely never added. Those positions would have been set to one during insertion. However, if all bits are one, the element might have been added, or those positions might have been set by other elements. This is the source of false positives.
Consider a concrete example. Suppose you have a 10 bit array and two hash functions. You insert the strings “apple” and “banana”:
hash1(“apple”) mod 10 = 2, hash2(“apple”) mod 10 = 5
hash1(“banana”) mod 10 = 3, hash2(“banana”) mod 10 = 7
After these insertions, bits 2, 3, 5, and 7 are set to one. Now you check for “cherry”:
hash1(“cherry”) mod 10 = 2, hash2(“cherry”) mod 10 = 3
Both positions are already one (set by previous insertions), so the filter incorrectly reports that “cherry” might be present. This is a false positive.
Mathematics of False Positives
After inserting n elements using k hash functions into a filter with m bits, the probability that a specific bit remains zero is:
Plain text
If you have m bits in your array and a hash function that outputs random positions, the probability of hitting any specific bit is 1/m. Hence, the probability of NOT hitting a specific bit with one hash is 1 - 1/m. The probability of that bit being zero with n insertions and each one setting k bits will be (1 - 1/m)^(kn).
For large m, this approximates to:
Plain text
The probability of a false positive is the probability that all k bits are set for a random element not in the set:
Plain text
Here’s an interesting and important trade-off. Increasing m (more bits) reduces false positives but uses more memory. Increasing k (more hash functions) can either help or hurt depending on the relationship between k and m/n.
The optimal number of hash functions that minimizes the false positive rate is (via simple differentiation):
Plain text
At this optimal k, the false positive rate becomes:
Plain text
Working backwards, if you want a specific false positive rate p, you need approximately:
Plain text
For a 1% false positive rate, you need about 9.6 bits per element. For 0.1%, you need about 14.4 bits per element.
Compare this to storing 1 million 64-bit integers directly, which would require 8 MB. The Bloom filter achieves roughly 7x space savings while providing probabilistic membership testing.
Hash Functions
Bloom filters require hash functions that are fast, produce uniformly distributed outputs, and behave independently of each other.
Cryptographic vs Non-cryptographic Hashes
Cryptographic hash functions, such as SHA-1 or MD5, offer good distribution properties and security guarantees; however, they are computationally expensive. Since Bloom filters do not require cryptographic security, using them wastes CPU cycles.
Non-cryptographic hash functions are the standard choice:
MurmurHash3
: Widely considered the best general-purpose non-cryptographic hash. It provides excellent distribution, handles all input sizes well, and is very fast. MurmurHash3 supports both 32 bit and 128 bit outputs.
xxHash
: Extremely fast, especially on modern CPUs with SIMD support. The xxh3 variant used in RocksDB is particularly optimized for short keys.
FNV (Fowler Noll Vo)
: Simple to implement and performs well on short strings (under 20 characters). The FNV-1a variant is slightly better than FNV-1 for most use cases.
Double Hashing Optimization
A seminal paper by Kirsch and Mitzenmacher showed that you do not actually need k independent hash functions. Instead, you can compute just two hash functions and derive all k positions using a linear combination:
Plain text
This is called double hashing or the Kirsch Mitzenmacher optimization and it reduces computational overhead dramatically while maintaining the same asymptotic false positive rate. Most production Bloom filter implementations use this approach.
Plain text
A subtle but important implementation detail: if h2 can be zero or share a common factor with m, you may get degenerate cases where multiple positions collide. The enhanced double hashing variant addresses this by ensuring h2 is always odd (when m is a power of two) or relatively prime to m:
Plain text
RocksDB discovered this issue in their Bloom filter implementation and fixed it by ensuring the delta value is always odd, which guarantees distinct positions when m is a power of two.
Deletable Bloom Filters
Standard Bloom filters have a significant limitation: you cannot remove elements. Once a bit is set to one, there is no way to know if it was set by one element or multiple elements. Unsetting it could cause false negatives for other elements that share that bit position.
Several variants address this limitation:
Counting Bloom filters
The most straightforward approach replaces each bit with a small counter (typically 4 bits). Instead of setting bits to one, you increment counters. To delete an element, you decrement the counters at the corresponding positions.
Plain text
The trade off is significant: using 4 bit counters means the filter uses 4x more memory than a standard Bloom filter. Counter overflow is another concern. If too many elements hash to the same position, the counter saturates. Most implementations handle this by leaving saturated counters at maximum and never decrementing them, accepting a slight increase in false positives.
Deletable Bloom Filter (DlBF)
The Deletable Bloom filter takes a different approach. Instead of counting, it splits the entire bloom filter array into r logical regions, then tracks which bit regions have experienced collisions (in at least one of the bit), and maintains a separate collision bitmap.
When inserting an element:
Compute the k
bit positions
For each position, if the bit is already set, mark that region as having a collision.
Set the bits
When deleting an element:
Check if any of the element’s bits are in collision-free regions.
If at least one bit is in a collision-free region, that bit can be safely unset
If all bits are in collision regions, the element cannot be deleted without risking false negatives
The DlBF provides probabilistic deletability: most elements can be deleted, but some cannot. The advantage is a much lower memory overhead compared to counting filters.
Benchmarking Bloom Filters
When evaluating Bloom filter implementations, several metrics matter and most of these benchmarks can be found on my GitHub Repository - abloom.
Insertion Throughput
Measures how many elements per second can be added to the filter. This depends primarily on:
Hash function speed
Number of Hash Functions
A Bloom filter should achieve hundreds of thousands to millions of insertions per second. Redis benchmarks show around 250,000 insertions per second with pipelining.
Lookup Throughput
Typically similar to or faster than insertion, since lookups can short-circuit on the first zero bit. The double hashing optimization particularly benefits lookups by reducing hash computations.
Actual False Positive Rate
The theoretical false positive rate assumes perfect hash functions. Real implementations could be benchmarked to verify.
Plain text
Bloom Filters in Databases
Bloom filters are pretty common in modern databases, particularly those using Log-Structured Merge (LSM) trees.
LSM Tree
Databases like RocksDB, Cassandra, LevelDB, and HBase all use Bloom filters to optimize read paths. In an LSM tree:
Writes go to an in-memory MemTable
When full, the MemTable flushes to an immutable SSTable on disk
Reads must potentially check multiple SSTables to find a key.
Without Bloom filters, every key lookup might require reading multiple SSTables from disk. With Bloom filters attached to each SSTable, the database can quickly determine if a key is definitely not present, avoiding expensive disk reads.
Cassandra exposes this as a tunable parameter. The bloom_filter_fp_chance setting controls the false positive rate per SSTable:
Plain text
Lower values (like 0.01) use more memory but reduce unnecessary disk reads. Higher values (like 0.1) save memory at the cost of more false positive disk accesses.
Use cases
Content Deduplication
Checking if content has been seen before is a classic Bloom filter application. Examples include:
Recommendation systems filter previously shown items.
Web crawlers track visited URLs
The key insight is that false positives (occasionally re-checking something already processed) are acceptable, while false negatives (missing something new) are not.
Cache Systems
CDNs use Bloom filters to track which objects are cached at edge nodes. Akamai pioneered the technique of using Bloom filters to avoid caching “one hit wonders” (objects accessed only once). By only caching objects seen at least twice, they dramatically improved cache efficiency.
The pattern:
First request: Add to Bloom filter, serve from origin
Subsequent requests: Check Bloom filter, cache if present
Database Acceleration
PostgreSQL Bloom Indexes
Imagine a table with 10 columns and queries that filter on various combinations:
Plain text
The traditional approach is to create B-tree indexes. But which combinations do you index?
Plain text
This explodes quickly. With 10 columns and arbitrary query patterns, you might need dozens of indexes, each consuming significant disk space and slowing down writes.
PostgreSQL’s Bloom index creates a single compact index that encodes all specified columns into one Bloom filter per row (or per page).
Plain text
For each row, hash each column value and set bits in a small Bloom filter (say, 80 bits per row)
Store these mini Bloom filters in the index.
At query time:
Plain text
Hash ‘red’ and ‘large’ to get the expected bit positions.
Scan the Bloom index, checking each row’s filter.
If any expected bit is 0, the row definitely does not match, skip it
If all bits are 1, the row might match, fetch and verify it
Spark Broadcast Joins
You are joining a large table (1 billion rows, 500 GB) with a small table (100,000 rows, 10 MB):
Plain text
Without optimization, Spark would broadcast the small table to all nodes:
Send the entire small table (10 MB) to every executor.
Each executor joins its partition of the large table locally
No shuffle of the large table needed
But what if only 5% of rows in the large table actually have matching user_ids? You are still reading and processing 1 billion rows.
Bloom filter optimization:
Plain text
What happens:
Build a Bloom filter containing all 100,000 user_ids from the small table (maybe 200 KB)
Broadcast this tiny Bloom filter to all nodes.
Each executor filters its partition of the large table:
Now only ~5% of rows (50 million instead of 1 billion) participate in the join
Footnotes
Bloom filters, invented by Burton Howard Bloom in 1970, remain one of the most widely deployed probabilistic data structures. It’s simplicity, efficiency, and well-understood mathematical properties put it to the core of modern systems design - from database internals to distributed systems to network security.
When you need fast, space-efficient membership testing and can tolerate occasional false positives, Bloom filters are often the optimal choice.
