Imagine you are running a website with 100 million registered users.
Every time someone enters a username, your application needs to answer:
«“Has this username already been used?”»
The obvious solution is to query the database.
But what if you receive 100,000 username checks per second, and most of those usernames don't even exist?
A Bloom filter can act as a tiny, extremely fast pre-check before the expensive database operation.
The surprising part is that the Bloom filter doesn't store the usernames.
It stores only a carefully constructed pattern of bits.
1. What is a Bloom filter?
A Bloom filter is a probabilistic data structure used to test whether an item belongs to a set.
It has two possible answers:
- Definitely not present
- Possibly present
That second answer is important.
A Bloom filter can produce a false positive—it can say an item may exist when it actually doesn't.
But a properly functioning standard Bloom filter does not produce false negatives: if it says an item is definitely absent, it is absent.
Bloom filters were introduced by Burton H. Bloom in a 1970 paper on reducing the space required for hash-coded membership testing while allowing a controlled error rate.
2. Let's forget the theory and build one
Suppose we have these registered usernames:
alice
bob
charlie
david
Instead of storing them directly in the Bloom filter, we create a bit array:
Position:
0 1 2 3 4 5 6 7 8 9
Bits:
0 0 0 0 0 0 0 0 0 0
Initially every bit is "0".
We will use three hash functions:
H1
H2
H3
The hash functions convert an input into positions in the bit array.
For example, for illustration:
H1("alice") → 2
H2("alice") → 6
H3("alice") → 8
So when we insert "alice", we set:
bit[2] = 1
bit[6] = 1
bit[8] = 1
The array becomes:
0 0 1 0 0 0 1 0 1 0
↑ ↑ ↑
Notice something very important:
We haven't stored ""alice"" anywhere in the Bloom filter.
We only changed three bits.
3. What exactly happens to the input?
This is often the most confusing part.
Suppose the user enters:
alice
The application sends the string through the hash functions:
"alice"
│
┌─────────┼─────────┐
▼ ▼ ▼
H1 H2 H3
│ │ │
▼ ▼ ▼
102 456 789
Those are hash values.
But our bit array has only 10 positions.
So we convert each hash value into an array position.
Conceptually:
position = hash % number_of_bits
For example:
102 % 10 = 2
456 % 10 = 6
789 % 10 = 9
Therefore:
alice → positions 2, 6, 9
The real implementation can use more sophisticated hashing techniques, but this simple example captures the fundamental idea. Bloom filters use hashes to determine which positions in the bit array are set or checked.
4. Now let's insert another user
Suppose we add:
bob
Our hash functions might produce:
H1("bob") → 1
H2("bob") → 5
H3("bob") → 8
Set those bits:
0 1 1 0 0 1 0 0 1 1
↑ ↑ ↑ ↑ ↑
Some bits overlap with bits already set by "alice".
This is completely normal.
The Bloom filter doesn't care who set a bit.
It only knows:
«This position has been activated.»
5. Now the real magic: searching
A user enters:
alice
We hash it again:
H1("alice") → 2
H2("alice") → 6
H3("alice") → 9
Then we inspect:
bit[2]
bit[6]
bit[9]
Suppose we get:
bit[2] = 1
bit[6] = 1
bit[9] = 1
All three positions contain "1".
The Bloom filter says:
«Possibly present.»
Notice that it doesn't say:
«Definitely present.»
Why?
Because another combination of usernames could have caused those same bits to become "1".
6. Now search for a username that doesn't exist
Suppose the user enters:
michael
The hashes might produce:
H1("michael") → 3
H2("michael") → 6
H3("michael") → 7
We inspect:
bit[3] = 0
bit[6] = 1
bit[7] = 0
We immediately have a zero.
Therefore:
«Michael definitely does not exist in the set.»
We don't need to query the database.
That's where the Bloom filter saves work.
7. Why does one zero prove absence?
This is the fundamental idea behind Bloom filters.
When an item is inserted, all of its hash-derived positions are set to "1".
For example:
alice
↓
H1 → bit 2
H2 → bit 6
H3 → bit 9
bit[2] = 1
bit[6] = 1
bit[9] = 1
If we later check "alice" and find:
bit[2] = 1
bit[6] = 0
bit[9] = 1
Then something is impossible.
If "alice" had actually been inserted, bit 6 would have been set.
Therefore:
one required bit = 0
↓
item definitely wasn't inserted
This is why Bloom filters can guarantee negative results.
8. But how can a false positive happen?
Let's say we have inserted:
alice
bob
charlie
david
After all those insertions, our bit array might look like:
1 1 1 1 1 1 1 0 1 1
Now suppose:
michael
was never inserted.
But its hashes happen to point to:
H1 → 1
H2 → 4
H3 → 9
All three bits are already "1".
So the Bloom filter says:
POSSIBLY PRESENT
But the database says:
NOT PRESENT
That's a false positive.
The Bloom filter cannot tell which original items caused those bits to become "1".
9. This leads to the real architecture
This is how you would normally use a Bloom filter in a production system:
USER REQUEST
│
▼
"michael123"
│
▼
┌────────────────┐
│ Bloom Filter │
└───────┬────────┘
│
┌────────┴────────┐
│ │
ONE BIT ALL BITS
= 0 = 1
│ │
▼ ▼
DEFINITELY NO POSSIBLY YES
│ │
▼ ▼
Stop here Query database
│
┌──────┴──────┐
│ │
FOUND NOT FOUND
│ │
▼ ▼
YES False positive
This is the key practical use of a Bloom filter.
It doesn't replace your database.
It protects your database from unnecessary lookups.
10. A real-world example: username registration
Imagine your application has:
100 million users
A new user wants the username:
superdeveloper
Without Bloom filter:
Application
↓
Database
↓
SELECT username ...
↓
Result
Now imagine 90% of requests are usernames that have never been registered.
You're performing millions of unnecessary database lookups.
With a Bloom filter:
Application
↓
Bloom Filter
↓
Definitely not present
↓
Username is available
No database lookup is required for that negative case.
If the filter says:
Possibly present
then:
Bloom Filter
↓
Database
↓
Exact answer
Redis documents this kind of use case, including checking whether usernames have already been used, and provides Bloom-filter operations such as "BF.ADD" and "BF.EXISTS".
- Another real-world example: URLs
Consider a crawler processing:
https://example.com/a
https://example.com/b
https://example.com/c
...
The crawler doesn't want to download the same URL twice.
You could maintain a huge set:
Visited URLs
example.com/a
example.com/b
example.com/c
...
100 million URLs
But this can consume substantial memory.
Instead:
URL
↓
Bloom Filter
↓
Already seen?
If the answer is:
NO
the crawler knows it has not previously seen the URL and can continue.
If:
MAYBE
the application can perform an exact lookup in its persistent URL store.
This pattern—using a small Bloom filter to avoid expensive disk or network lookups—is one of the classic applications of the data structure.
12. Why not simply store hashes?
You might now ask:
«Why not store the hash values instead of bits?»
For example:
apple → 123456
banana → 678901
orange → 345678
The problem is memory.
A Bloom filter deliberately throws away information.
It doesn't need to remember:
apple → hash value
It only needs to remember:
some positions are occupied
That allows the representation to be extremely compact.
The trade-off is:
Less memory
+
Very fast lookup
=
Small probability of false positives
Bloom filters are specifically attractive because their memory consumption is measured in bits per element, rather than storing the complete elements.
13. Why multiple hashes?
Suppose we use only one hash:
apple → bit 4
A different item could also map to bit 4.
That creates collisions easily.
Instead, we use several hash-derived positions:
apple
│
├── H1 → 4
├── H2 → 18
└── H3 → 73
Another item might be:
banana
│
├── H1 → 4
├── H2 → 22
└── H3 → 81
There is some overlap, but for "banana" to become a false positive, all three required positions need to already be "1".
More hash positions and more bits per element generally reduce the false-positive probability, although they also affect memory and computation.
14. The most important mental model
Don't think:
Input
↓
Hash
↓
Compare against stored hashes
Think:
INPUT
│
▼
HASH FUNCTIONS
│
┌───────┼───────┐
▼ ▼ ▼
12 57 91
│ │ │
▼ ▼ ▼
┌──────────────────────┐
│ BIT ARRAY │
│ │
│ 0 1 1 0 1 1 0 1 ... │
└──────────────────────┘
│ │ │
▼ ▼ ▼
1 1 1
│
▼
POSSIBLY YES
The hashes don't identify the stored object.
They identify positions to inspect in the bit array.
That distinction is the heart of understanding Bloom filters.
15. A tiny Python implementation
Here is the concept without using a Bloom-filter library:
class BloomFilter:
def __init__(self, size=20):
self.size = size
self.bits = [0] * size
def hashes(self, value):
h1 = hash(value)
h2 = hash(value + "salt")
h3 = hash(value + "another-salt")
return [
h1 % self.size,
h2 % self.size,
h3 % self.size
]
def add(self, value):
for index in self.hashes(value):
self.bits[index] = 1
def might_contain(self, value):
for index in self.hashes(value):
if self.bits[index] == 0:
return False
return True
Usage:
bf = BloomFilter()
bf.add("alice")
bf.add("bob")
bf.add("charlie")
print(bf.might_contain("alice"))
print(bf.might_contain("michael"))
Conceptually:
alice → True → Possibly present
michael → False → Definitely absent
For production systems, you would use a carefully designed hash strategy and a library rather than Python's built-in "hash()" directly.
16. Choosing the false-positive rate
Bloom filters don't have one fixed accuracy.
You can design one for something like:
10% false positives
1% false positives
0.1% false positives
0.01% false positives
The lower you want the false-positive rate, the more memory you generally need.
For example, Redis allows you to specify both an expected capacity and desired error rate when creating a Bloom filter.
Conceptually:
Bloom Filter
│
┌───────────┴───────────┐
│ │
Memory Accuracy
│ │
└────── trade-off ──────┘
- One important limitation
A standard Bloom filter is excellent at:
ADD
CHECK
But removing an individual element is problematic.
Why?
Suppose:
alice → bits 2, 5, 8
bob → bits 2, 7, 9
If we remove "alice" and simply change:
bit 2 → 0
we would accidentally affect "bob", because "bob" also uses bit 2.
That's why variants such as Counting Bloom Filters and Cuckoo Filters exist. Redis, for example, provides both Bloom and Cuckoo filters.
18. Where Bloom filters become really interesting
The concept becomes particularly powerful when the operation you're avoiding is expensive:
Cheap
│
Bloom Filter
│
┌─────┴─────┐
│ │
NO MAYBE
│ │
▼ ▼
Finish Expensive
operation
│
▼
Database
Disk
Network
API
That expensive operation could be:
- Database query
- Disk read
- Network request
- Microservice call
- Object-storage lookup
- URL fetch
- Duplicate-data check
This is why Bloom filters remain useful in large-scale systems. Redis describes them specifically as a way to avoid costly disk or network operations when an item can be ruled out immediately.
19. The one-sentence definition
If you remember only one thing, remember this:
«A Bloom filter hashes an item into several positions in a compact bit array; if any required bit is 0, the item is definitely absent; if all are 1, the item is only possibly present.»
Or even shorter:
ZERO → DEFINITELY NO
ALL ONE → MAYBE YES
That's the entire idea.
And that tiny idea is surprisingly powerful when you're dealing with millions or billions of membership checks.
References
- Burton H. Bloom's original 1970 paper introduced the space/time trade-off underlying Bloom filters.
- Redis documentation provides a current implementation and examples of Bloom filters, including capacity, error-rate configuration, and membership operations.
- Redis explains the bit-array/hash mechanism and practical use cases such as avoiding expensive database or network lookups.
Top comments (0)