Cuckoo Filter Explained: How It Works & When to Use It

Cuckoo Filter is just like a Bloom filter, is a probabilistic data structure. A probabilistic data structure is a data structure that provide approximate answers to queries about a large dataset rather than exact answers.These data structures are designed to handle large amounts of data in real-time, by making trade-offs between accuracy and time and space efficiency.

How does it work

A Cuckoo Filter works by storing a small fingerprint, which is a tiny hash, of an item instead of the whole item. Every item has two possible buckets for its fingerprint.

When you insert an item, the filter first checks if either of its two buckets has space. If one is available, the fingerprint is stored there. If both buckets are full, the filter moves one of the existing fingerprints to the other bucket to create room for the new one. This process is called cuckoo eviction, similar to how a cuckoo bird pushes another bird's egg out of a nest.

To check if an item exists, the filter calculates the same fingerprint and looks only in its two possible buckets. If it finds the fingerprint, the item is probably present. If it doesn’t find it in either bucket, the item is definitely not present.

Deleting an item is straightforward because its fingerprint is stored directly in one of the two buckets. The filter simply finds the fingerprint and removes it; this is something a standard Bloom Filter cannot do safely.

• Insertion in a Cuckoo Filter

The insertion process in a Cuckoo Filter begins when a new item arrives. Instead of saving the whole item, the filter first creates a fingerprint, which is a small hash value that represents that item. Then, it calculates two possible buckets where this fingerprint can be stored.

The filter checks if either of the two buckets has an empty slot.

If at least one bucket has space, the fingerprint is stored there, and the insertion is done. If both buckets are full, the filter chooses one bucket and removes one of the fingerprints already stored there. The new fingerprint is then placed into the empty slot.

The removed fingerprint is not deleted. Instead, the filter calculates its alternate bucket (the other bucket where it can be stored) and tries to move it there.

If the alternate bucket has space, the removed fingerprint is saved, and the insertion is successful. If the alternate bucket is also full, another fingerprint is removed from that bucket, and the same process happens again. This series of removals is known as the kick-out process or cuckoo eviction.

To avoid an endless loop, the filter keeps track of how many kick-outs have taken place. If the number exceeds a predefined limit, the table is seen as too full. The filter then resizes, and all current fingerprints are reinserted into the bigger table. Once this is done, the new fingerprint is successfully inserted.

This kick-out method is inspired by the cuckoo bird, which lays its eggs in another bird's nest, pushing out one of the existing eggs. Similarly, a new fingerprint pushes an existing one to its alternate location until every fingerprint finds a valid spot in the filter.

flowchart TD
    A([Start]) --> B[Receive Item]
    B --> C[Generate Fingerprint]
    C --> D[Compute Two Candidate Buckets]

    D --> E{Is either bucket available?}

    E -- Yes --> F[Store Fingerprint]
    F --> G([Insertion Successful])

    E -- No --> H[Choose One Bucket]
    H --> I[Evict Existing Fingerprint]
    I --> J[Insert New Fingerprint]
    J --> K[Calculate Alternate Bucket for Evicted Fingerprint]

    K --> L{Alternate bucket has space?}

    L -- Yes --> M[Store Evicted Fingerprint]
    M --> G

    L -- No --> N[Repeat Kick-Out Process]

    N --> O{Maximum Kicks Reached?}

    O -- No --> I
    O -- Yes --> P[Resize Filter]
    P --> Q[Reinsert All Fingerprints]
    Q --> G

• Lookup in a Cuckoo Filter

The lookup process starts when it gets the item that we need to search for. It is similar to when we add an item the filter makes a code for the item, which is called a fingerprint and it figures out which two places the fingerprint could be stored.

The filter then looks at these two places to see if the fingerprint is there.

If the fingerprint is found in one of these places the filter says that the item is probably in the list. We say probably because sometimes different items can have the fingerprint, which means we get a wrong result.

If the fingerprint is not found in either place the filter knows for sure that the item is not in the list. This is good because Cuckoo Filters never say an item is not in the list when it actually is unless something is wrong with how they're working.

Since the filter only looks at two places no matter how big the list is it can find the item quickly. This means that Cuckoo Filters are very good at checking if an item is, in a list and they can do it fast.

flowchart TD
    A([Start]) --> B[Receive Item]
    B --> C[Generate Fingerprint]
    C --> D[Compute Two Candidate Buckets]
    D --> E[Check Both Buckets]

    E --> F{Fingerprint Found?}

    F -- Yes --> G[Item is Probably Present]
    F -- No --> H[Item is Definitely Not Present]

    G --> I([End])
    H --> I

• Deletion in a Cuckoo Filter

The deletion process starts when the item that needs to be removed is received. The filter creates the item's fingerprint and finds the same two candidate buckets where the fingerprint might have been stored during insertion.

The filter looks for the fingerprint in both buckets.

If the fingerprint is found, it is removed from the bucket, and the deletion is done. If the fingerprint is not found, the filter determines that the item is not there, so nothing is removed.

Unlike a Bloom Filter, a Cuckoo Filter stores fingerprints directly instead of setting shared bits. Since each fingerprint is linked to a specific bucket, it can be removed safely without impacting other items. This is one of the main benefits of a Cuckoo Filter, making deletion a simple O(1) average-time operation.

flowchart TD
    A([Start]) --> B[Receive Item]
    B --> C[Generate Fingerprint]
    C --> D[Compute Two Candidate Buckets]
    D --> E[Search Both Buckets]

    E --> F{Fingerprint Found?}

    F -- Yes --> G[Remove Fingerprint]
    G --> H([Deletion Successful])

    F -- No --> I[Item Not Present]
    I --> J([End])

    H --> J

Deletion assumes that the item being removed was previously inserted. If two different items happen to share the same fingerprint (a rare false positive), deleting based only on the fingerprint could theoretically remove the wrong entry. In practice, this is extremely uncommon.

False Positives in a Cuckoo Filter

A false positive is the kind of mistake a Cuckoo Filter can have. It happens when the filter says an item is likely present even though that item was never added to the filter.

To know why this occurs keep in mind that a Cuckoo Filter does not keep the items. It keeps a tiny part of each item called a fingerprint. These fingerprints are very small compared to the information. This makes the filter use memory.. It also means that different items can sometimes create the same fingerprint.

Examples

Suppose a Cuckoo Filter stores the username harsh. Instead of storing the entire username, it stores only a small fingerprint.

Now, a user searches for the username david, which has never been inserted into the filter.

After generating its fingerprint:

When the system looks something up the Cuckoo Filter checks the two places and finds the fingerprint 01100110. The Cuckoo Filter only stores these fingerprints, not the usernames so it thinks the username is really there. The Cuckoo Filter is just working with the Cuckoo Filters fingerprints, like 01100110 to figure out if the username is present, in the Cuckoo Filter.

Inserted Usernames

1. harsh → 10110101
2. ishan → 01100110
3. coc → 11001011
4. john → 00111100
5. sophia → 10011010

Search: david say it generates the fingerprint 01100110 but this fingerprint already exists in the therefore, result: "Probably Present"

Even though david was never inserted into the filter, it shares the same fingerprint as ishan. Since the Cuckoo Filter stores only compact fingerprints to save memory, it cannot distinguish between these two usernames. As a result, it returns "Probably Present", which is a false positive.

This example uses simple binary fingerprints for illustration. In real Cuckoo Filters, fingerprints are generated using hash functions and are typically 8–16 bits long, making collisions like this possible but relatively rare.

Time & Space Complexity

• Time Complexity

The Cuckoo Filter is designed to perform all its primary operations in constant time on average. Since each item can be stored in only two candidate buckets, lookup and deletion require checking at most those two locations, making them extremely fast.

Insertion is also O(1) on average. In most cases, the fingerprint is placed into one of its candidate buckets immediately. If both buckets are full, the filter performs a series of cuckoo evictions (kick-outs) until an empty slot is found. Although multiple evictions may occur, the average insertion time remains constant. Only when the filter becomes nearly full does insertion become more expensive, potentially requiring the filter to be resized.

Operation	Average Time	Worst Case
Insertion	O(1)	O(n) (during resize)
Lookup	O(1)	O(1)
Deletion	O(1)	O(1)

• Space Complexity

A Cuckoo Filter stores only a small fingerprint for each item instead of the complete item. Because fingerprints are typically 8–16 bits, the filter uses significantly less memory than storing the original data.

The overall space complexity is O(n), where n is the number of stored items. As more items are inserted, the filter requires proportionally more buckets to maintain a low false positive rate and efficient insertions.

The amount of memory used depends mainly on:

• Fingerprint size – Larger fingerprints reduce false positives but consume more memory.
• Bucket size – The number of fingerprints each bucket can store (commonly 4).
• Load factor – Keeping the filter around 90–95% full provides a good balance between memory efficiency and insertion performance.

Most practical implementations use 4 fingerprints per bucket and keep the filter below 95% occupancy. This provides excellent lookup performance while keeping insertion failures extremely rare.

Advantages

Cuckoo Filters have become a popular choice for modern applications because they provide fast membership testing while using very little memory. Compared to traditional Bloom Filters, they also introduce several practical improvements, making them suitable for systems where data changes frequently.

• Memory Efficient: Cuckoo Filters store only compact fingerprints instead of complete items, allowing them to handle large datasets while using relatively little memory.
• Supports Dynamic Datasets: Unlike some probabilistic data structures that are best suited for static data, Cuckoo Filters work well when items are frequently added and removed.
• Better Space Efficiency than Counting Bloom Filters: When deletion support is required, Cuckoo Filters often consume less memory than Counting Bloom Filters while providing comparable or better performance.
• Highly Scalable: As the dataset grows, the filter can be resized to accommodate additional items, making it suitable for applications that need to handle increasing amounts of data.
• Configurable Accuracy: Developers can adjust the fingerprint size to balance memory consumption and the false positive rate according to the application's requirements.
• Ideal for High-Performance Systems: Their low memory footprint and efficient operations make Cuckoo Filters well suited for systems where fast membership testing is essential, such as databases, caches, networking software, and storage engines.

Disadvantages

• False Positives: Cuckoo Filters store fingerprints of items instead of the actual items. As a result, two different items can occasionally produce the same fingerprint, causing the filter to report that an item is present even though it was never inserted.
• Insertion Can Fail: When a Cuckoo Filter becomes nearly full, finding space for new items becomes more difficult. If repeated kick-out operations fail to create space, the filter must be resized and all existing fingerprints must be reinserted.
• Performance Degrades at High Load Factors: Cuckoo Filters perform best when they are not close to full capacity. As the filter fills up, insertions may take longer because more kick-out operations are required before an empty slot is found.
• More Complex Implementation: Compared to Bloom Filters, Cuckoo Filters are more difficult to implement because they require fingerprint management, cuckoo hashing, and eviction logic.
• Careful Parameter Selection: Choosing an appropriate fingerprint size, bucket size, and load factor is important. Poor parameter choices can increase the false positive rate or reduce insertion performance.
• Not Suitable for Exact Membership Testing: Since false positives are possible, Cuckoo Filters should not be used in applications where membership must be determined with absolute certainty without verifying against the original data source.

Bloom Filter vs Cuckoo Filter

Real-World Applications

Cuckoo Filters are widely used in systems that require memory-efficient membership testing. Their ability to support insertion, lookup, and deletion makes them suitable for applications where the dataset changes frequently.

• Databases: Used to determine whether a key or record is likely to exist before performing a disk or database lookup, reducing unnecessary I/O operations.
• Web Caches: Help determine whether a cached object or response is likely to exist, avoiding unnecessary cache misses and improving response times.
• Content Delivery Networks (CDNs): Used to check whether content is available on an edge server before forwarding requests to the origin server.
• Networking Systems: Applied in routers, switches, and firewalls to efficiently track IP addresses, packets, or network flows while using minimal memory.
• Storage Systems: Help identify whether blocks, files, or objects are likely to exist before accessing slower storage devices.
• Cybersecurity: Used to maintain dynamic lists of malicious IP addresses, URLs, or file signatures where entries need to be added and removed frequently.
• Distributed Systems: Reduce unnecessary network requests by filtering out queries for data that is definitely not present on a remote node.
• Web Crawlers: Keep track of visited URLs to avoid processing the same web page multiple times while allowing entries to be removed when necessary.

Conclusion

Cuckoo Filters provide a fast and memory-efficient way to perform membership testing while overcoming one of the biggest limitations of traditional Bloom Filters—support for deletion. By storing compact fingerprints and using cuckoo hashing, they enable efficient insertion, lookup, and deletion with constant average-time performance.

Although Cuckoo Filters can produce false positives and become less efficient as they approach full capacity, they remain an excellent choice for applications that require dynamic datasets and frequent updates. Their balance of speed, memory efficiency, and flexibility has made them a popular choice in modern databases, caches, networking systems, storage engines, and cybersecurity applications.

If your application requires a simple, read-only probabilistic data structure, a Bloom Filter may be sufficient. However, if you need to frequently add and remove items while maintaining high performance, a Cuckoo Filter is often the better solution.