Cuckoo Filters vs. Bloom Filters: Let’s Take it Easy

Kishan Agarwal — Sat, 30 May 2026 07:55:26 +0000

Ok, before we go into the depths of these concepts, I want to tell you that we will take it easy. I don’t want you to get overwhelmed about the topics and the depth of the discussion.

Bloom Filters

A Bloom filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set.

Sounds hard, right? In just one sentence: "probabilistic," then "data structure," and all this is what the definition says. Let's break it down so you understand what it truly is.

The Concept

Ok, I give you a problem. Think of it for a second. Let's say you have an array of characters (English alphabet characters) of size n, and you have to find whether a char exists or not.

Approach 1 (Loop): Quite simple, we can just loop the array once. This gives us a time complexity of O(n)
Approach 2 (Sort + Binary Search): We sort the array (O(nlog n)) and then perform a binary search (O(log n)). Steps increased, but at least we reduced the time.
Approach 3 (HashMap): We store it in a HashMap. This way we take double space, but at least we can optimise the time to O(1)

Can we optimise it further? For most of us, this may be ok because you have to prioritise over time and space. Now, for those who want both, the discussion is for you, my friend.

Think of this: Have you read about ASCII values before?

Let's say a user gives me input 'a'. I don't store 'a'. Instead, I calculate its relative position from 'a' and store it in a bit array of length 26.

We get a number, consider it as an index.
Store 1 in the position, else 0.

Now, to check for a char, we just repeat the process. We can access this in, and the space it will take is just 26 bits. Insane, right?

The Real Engineering Part (The Hashing Reality)

But then, that's for a single char. For a string, we can't do that. And Bloom filters are mostly used on strings. So now get to the real engineering part.

In Bloom filters, we use a hashing function known as MurmurHash. What is hashing? Hashing is a technique of converting a string to an equivalent number.

But here is the catch: Hashing is deterministic (Input A always gives Output A), but the universe of strings is infinite, while our array is finite.

For A, you get a hash.
Then B gets a hash.
Then C can also generate the same hash as B.

Can you see what is happening? These are collisions. The main problem is this: hashing can sometimes give the same index for two strings. So in order to prevent this, we need to be clever.

Bloom Filters in Production (Making it Robust)

Now, you might be thinking, "If collisions are inevitable, isn't this useless?"

In a real production setup, we don't rely on just one hash function. That would be too risky. In the real world, we use Multiple Hash Functions (let's say functions).

When a string comes in, we run it through Hash Function 1, Hash Function 2, and Hash Function 3.
We get 3 different indexes.
We set all 3 positions to 1.

Now, when we query:

We check all 3 positions.
If all of them are 1, then we say "Yes, it's probably here."
If even one of them is 0, we can say with 100% guarantee: "It is not here."

This drastically reduces the false positive rate. It’s like asking three different friends if a restaurant is open. If all three say yes, it's probably open. If one says, "No, I'm standing in front of it, and it's closed," then you know for sure.

The Major Problem

Now, can you see a major problem in this Bloom filter? I also recently came to know about it.

The problem is deletion.

Once a Bloom filter gets filled, let's say User A deletes their account. Technically, this username is free. But your Bloom filter will still say that the username exists.

We can query in O(1)
We can insert in O(1)
But we cannot delete data.

Why? If I go to those 3 positions and set them back to 0, maybe User B was also using one of those spots! If I delete User A, I might accidentally "corrupt" User B. This is why deletion is extremely challenging in Bloom filters.

So, is there a fix? (The Counting Bloom Filter)

Now you might be thinking, "Can’t we just simply count the items instead of just flipping bits?"

Actually, yes. There is something called a Counting Bloom Filter.

The logic is super simple:

In a normal Bloom filter, we have bits (0 or 1).
In a Counting filter, we keep a counter (a number).

So when you add an item, you just increment the counter at that index (+1). When you want to delete, you just decrement it (-1).

Sounds perfect, right? Problem solved! But here is the major catch.

To store a counter (even a small number), you need way more space than a single tiny bit. A standard Bloom filter uses 1 bit per spot. A Counting filter might need 4 bits or more just to hold that number.

So, we effectively quadrupled the space usage. We solved the deletion problem, but we killed the whole purpose of using a Bloom filter: Space Efficiency. If it takes too much RAM, we might as well just use a HashMap, right?

We need something that allows deletion without blowing up our memory.

Cuckoo Filters: The Solution

So you might be thinking, "yeah, then there might be a solution." Yes, there is a fantastic solution known as the Cuckoo Filter.

Does the name give you some hint? Cuckoo.

The bird that doesn't build its own nest; it takes over the nests of other birds. But why this?

Cuckoo Hashing: The "Kicking" Strategy

Cuckoo filters work on the principle of partial-key cuckoo hashing. Bloom filters store bits (0 or 1). Cuckoo filters store a Fingerprint.

What is a fingerprint? Instead of just marking a spot as "occupied," we take a small signature of the data (like an 8-bit or 12-bit hash) and store that. This is the game changer.

Here is how the "Kicking" works (The Cuckoo Logic):

Hash 1: String A comes. I hash it and try to put its fingerprint in Nest 1.
Collision: If Nest 1 is full, we don't just give up. The new entry kicks out the old entry!
Re-homing: The old entry (the victim) is now homeless. It has to find a new spot.
The Magic Math: In production, we use a math trick (XOR operation) to calculate the "alternative nest" using just the current position and the fingerprint. The victim flies to Nest 2.
Loop: If Nest 2 is also full? It kicks that one out.

It’s a chain reaction. It can very easily turn into an infinite loop. This is the only slight problem.

The Fix: We assign Max Iterations (let's say 500). It will try to kick items around 500 times. If no solution is reached, then we know the filter is too full, and we need to expand.

Production Setup: Buckets and Efficiency

In a real production setup (like in large-scale databases), we don't just have single slots. We use Buckets.

Imagine the array is divided into buckets, and each bucket has 4 slots.
This means when a hash maps to a bucket, we can fit 4 different items there before we have to start kicking anyone out.
This makes the Cuckoo filter insanely dense. We can fill it up to 95% capacity, and it still works fast. Bloom filters usually start failing around 50% or 70% full.

Why does this solve Deletion?

Because we store Fingerprints, not just bits.

If I want to delete User A:

I calculate the hash and look in the bucket.
I check the fingerprints stored there.
I find the fingerprint that matches User A.
I remove it.

Since I am matching a specific fingerprint, I am highly unlikely to delete User B by accident. This gives us ** Deletion** without the huge memory cost of Counting Bloom Filters.

Want to try it? (RedisBloom)

Now, you might be thinking, "This is cool, but do I have to write all this complex math and XOR logic myself?"

No, my friend. You don't.

If you are using Redis (and you probably are), there is a module called RedisBloom. It has all this implemented for you.

For Bloom Filters: You just run BF.ADD key item and `BF.EXISTS key item. It handles the multiple hashes for you.
For Cuckoo Filters: You run CF.ADD key item the magic command. CF.DEL key item.

It’s production-ready, highly optimised, and you don't have to worry about the "kicking" logic—it happens behind the scenes. So if you need to optimise space, just load this module, and you are good to go.

DIY: Build It Yourself (Pseudocode)

I know some of you are curious. You don't just want to use a library; you want to see the guts of the algorithm.

If you want to implement this in Python, Go, or Java to learn, here is the blueprint. I’ve written this in pseudocode so you can translate it into your favourite language.

1. The Bloom Filter Logic

This is straightforward. We need a bit array and multiple hash functions.

// Configuration
ArraySize = 1000
BitArray = [0] * ArraySize

// Function to Add an Item
Function Add(item):
    idx1 = Hash1(item) % ArraySize
    idx2 = Hash2(item) % ArraySize
    idx3 = Hash3(item) % ArraySize

    BitArray[idx1] = 1
    BitArray[idx2] = 1
    BitArray[idx3] = 1

Function Exists(item):
    idx1 = Hash1(item) % ArraySize
    idx2 = Hash2(item) % ArraySize
    idx3 = Hash3(item) % ArraySize

    IF (BitArray[idx1] == 1 AND BitArray[idx2] == 1 AND BitArray[idx3] == 1):
        RETURN True
    ELSE:
        RETURN False

2. The Cuckoo Filter Logic

This is where the magic happens. The key here is the "Kicking" loop and the XOR math to find the alternate index.

// Configuration
MaxKicks = 500
Buckets = [Size 1000] // Each bucket can hold multiple fingerprints

// Helper: Calculate Fingerprint (a small hash)
Function GetFingerprint(item):
    RETURN Hash(item) -> truncated to 8 bits

// Helper: Calculate Two Possible Locations
Function GetLocations(item, fingerprint):
    idx1 = Hash(item)
    
    // The Magic: We can find idx2 using only idx1 and the fingerprint!
    idx2 = idx1 XOR Hash(fingerprint)
    
    RETURN idx1, idx2

// Function to Add Item
Function Insert(item):
    fp = GetFingerprint(item)
    idx1, idx2 = GetLocations(item, fp)

    // 1. Try to fit in the first nest
    IF Buckets[idx1] has space:
        Buckets[idx1].add(fp)
        RETURN Success

    // 2. Try to fit in the second nest
    IF Buckets[idx2] has space:
        Buckets[idx2].add(fp)
        RETURN Success

    // 3. Both full? Time to KICK!
    current_idx = RandomlyPick(idx1, idx2)
    
    LOOP for count from 0 to MaxKicks:
        // Swap the new fingerprint with the one currently in the bucket
        victim_fp = Buckets[current_idx].swap_with(fp)
        
        // Make the victim the new item to insert
        fp = victim_fp
        
        // Calculate where the victim should go (The Magic XOR again)
        current_idx = current_idx XOR Hash(fp)

        IF Buckets[current_idx] has space:
            Buckets[current_idx].add(fp)
            RETURN Success

    RETURN Failure // Filter is too full, we need to expand!

Try implementing this! It’s one thing to read about "kicking" items, but it’s a whole different feeling when you write that loop and see your code shuffling data around to make space.

Happy Exploration!

DEV Community: Kishan Agarwal