Bloom Filters: How Systems Check Billions of Items Without Storing Them All

Imagine you're building a system with 100 million URLs.

Someone asks:

Have we already seen this URL?

The obvious solution is a HashSet.

HashSet.contains(url)

Fast.

But now imagine the dataset contains billions of objects.

The set itself can become enormous.

What if you only need to answer:

"Is this item definitely NOT present?"

And you don't need to know exactly where it is?

That's where Bloom Filters become incredibly useful.

What Is a Bloom Filter?

A Bloom Filter is a probabilistic data structure that answers one question:

"Have I probably seen this before?"

It has two possible answers:

Definitely NOT
 
or
 
Probably YES

That wording is important.

A Bloom Filter can produce false positives.

It cannot produce false negatives.

In other words:

If it says an item isn't there, you can trust it.

If it says an item might be there, you need to check the real data structure.

The Basic Idea

A Bloom Filter consists of:

1. A bit array
2. Multiple hash functions

Imagine a tiny array:

0 0 0 0 0 0 0 0 0 0

Suppose we want to add:

"apple"

We run it through several hash functions.

hash1("apple") → 2
hash2("apple") → 6
hash3("apple") → 8

We set those positions to 1.

0 0 1 0 0 0 1 0 1 0

Now let's add:

"banana"

Maybe its hashes are:

hash1("banana") → 1
hash2("banana") → 6
hash3("banana") → 9

The array becomes:

0 1 1 0 0 0 1 0 1 1

Notice that we don't store the actual strings.

We only store bits.

That's the trick.

Checking An Item

Now someone asks:

"apple"

We calculate the same hashes:

2
6
8

All three positions contain 1.

0 1 1 0 0 0 1 0 1 1
    ↑         ↑   ↑
    2         6   8

So the Bloom Filter says:

Probably present

We then check the actual database if we need certainty.

What If We Search For "orange"?

Suppose:

hash1("orange") → 3
hash2("orange") → 5
hash3("orange") → 7

The filter contains:

0 1 1 0 0 0 1 0 1 1

Positions 3, 5, and 7 aren't all set.

Therefore:

Definitely NOT present.

We don't need to query the database at all.

That's where the performance benefit comes from.

The Interesting Part: False Positives

Here's the weird part.

Suppose we search for:

"grape"

It was never inserted.

But its hash functions might produce:

2
6
8

Those bits happen to already be 1 because other items set them.

The Bloom Filter says:

Probably present

But the item isn't actually there.

That's a false positive.

And that's completely normal.

Why No False Negatives?

Suppose we inserted:

apple

Its bits were:

2
6
8

We never turn bits back to 0.

So when we search for apple...

Those positions will still be 1.

Therefore:

Inserted item
      ↓
All required bits are 1
      ↓
Never says "definitely absent"

That's the fundamental property of a standard Bloom Filter.

Why Not Just Use A HashSet?

Because memory.

Imagine storing millions of large strings.

A HashSet needs to store:

Actual Item
+
Hash Table Metadata
+
References
+
Memory Overhead

A Bloom Filter stores:

Bits

That's it.

For some workloads, the difference is enormous.

You trade perfect accuracy for extremely low memory usage.

Bloom Filters In Redis

One interesting real-world application is Redis.

Redis itself can be used alongside Bloom Filters through RedisBloom / Redis Stack functionality.

Imagine an application checking whether a user has already seen an article.

Without a filter:

Request
 
↓
 
Database
 
↓
 
Check user history
 
↓
 
Return result

With a Bloom Filter:

Request
 
↓
 
Bloom Filter
 
↓
 
Definitely NOT?
   │
   └── Yes → Skip database
 
Probably YES?
   │
   └── Check database

The filter acts as a cheap first layer.

Cassandra And Distributed Databases

Bloom Filters are especially useful in systems that have to search across many storage files.

Consider a distributed database containing thousands of SSTables.

A query asks:

Where is user_id = 93821?

Checking every file would be expensive.

Instead, each SSTable can have a Bloom Filter.

Query
  │
  ├── SSTable A → Definitely Not
  ├── SSTable B → Definitely Not
  ├── SSTable C → Probably Yes
  ├── SSTable D → Definitely Not
  └── SSTable E → Definitely Not
                    │
                    ▼
              Read SSTable C

Instead of performing expensive disk reads everywhere...

The Bloom Filters eliminate most of the candidates first.

This is a beautiful example of using a tiny amount of memory to avoid expensive I/O.

Why Databases Love This Idea

Disk access is expensive.

Memory access is cheap.

A Bloom Filter basically says:

"Before you touch the disk, let me quickly tell you whether there's any point looking."

That principle appears throughout storage-engine design.

Cheap Check
 
↓
 
Expensive Operation

The cheap check prevents unnecessary expensive operations.

Web Crawlers

Here's another interesting application.

Imagine a crawler has already visited:

100 million URLs

Before crawling another URL, it needs to ask:

Have I already visited this?

Storing every URL in a massive in-memory set can become expensive.

A Bloom Filter can provide a quick first check:

New URL
  │
  ▼
Bloom Filter
  │
  ├── Definitely new
  │       ↓
  │     Crawl
  │
  └── Probably seen
          ↓
      Check exact store

This can dramatically reduce unnecessary work.

CDN And Caching Systems

Bloom Filters can also be useful around caching and content lookup.

Imagine a system receiving millions of requests for objects.

Instead of immediately checking an expensive backing store:

Request
  ↓
Bloom Filter
  ↓
Probably exists?
  ↓
Cache / Storage lookup

The filter can quickly eliminate objects that definitely aren't present.

This pattern is especially useful when a negative lookup is expensive.

The General Pattern

Once you understand Bloom Filters, you'll start noticing the pattern everywhere.

                    Request
                       │
                       ▼
                Cheap Filter
                       │
             ┌─────────┴─────────┐
             ▼                   ▼
      Definitely No         Maybe Yes
             │                   │
             ▼                   ▼
           Stop           Expensive Lookup

That's the real idea.

Not the bits.

Not the hash functions.

Avoid expensive work whenever you can prove it's unnecessary.

The Trade-Off

Bloom Filters aren't magic.

They have limitations.

False positives

An item may appear to exist when it doesn't.

No deletion in a standard Bloom Filter

Once bits become 1, you can't safely remove an individual item.

There are variants such as Counting Bloom Filters that address this limitation.

You must choose the size

The size of the bit array affects the false-positive rate.

Too small...

And too many bits become 1.

Too large...

And you waste memory.

How Do You Choose The Size?

The important parameters are:

n = number of expected items
 
m = number of bits
 
k = number of hash functions

The approximate false-positive probability is:

p ≈ (1 - e^(-kn/m))^k

You don't normally calculate this manually in application code.

Libraries usually handle it.

But understanding the relationship is useful:

More bits
    ↓
Fewer collisions
    ↓
Lower false-positive rate

And:

More hash functions
    ↓
More work per lookup

So there's a balance.

Bloom Filter vs HashSet

| Property | HashSet | Bloom Filter | |----------|:-------:|:------------:| | Exact result | Yes | No | | False positives | No | Possible | | False negatives | No | No | | Stores actual values | Yes | No | | Memory usage | Higher | Very low | | Fast lookup | Yes | Yes | | Supports deletion | Yes | No | | Best for | Exact membership | Cheap filtering |

The key difference is simple:

HashSet asks:

"Is this item present?"

Bloom Filter asks:

"Is this item definitely not present?"

That distinction makes all the difference.

When Should You Use One?

Bloom Filters are useful when:

• The dataset is huge.
• Memory matters.
• Most lookups are negative.
• False positives are acceptable.
• The real lookup is expensive.

They're particularly attractive when the expensive operation is:

Disk I/O
Network request
Database query
Remote service call

If you can eliminate 90% of those operations with a tiny in-memory structure...

That's a pretty good trade.

Final Thoughts

I love Bloom Filters because they're a perfect example of an engineering trade-off.

Instead of demanding:

"Give me a perfect answer."

We ask:

"Can you cheaply prove that the answer is definitely no?"

That tiny change in the question can save enormous amounts of:

• Memory
• Disk I/O
• Network traffic
• Database queries
• CPU time

And that's often what good systems engineering looks like.

You don't always make the expensive operation faster.

Sometimes...

You simply stop doing it.