How Does a Cuckoo Filter Work?

A Cuckoo filter is a compact probabilistic data structure for answering membership questions such as:

"Could this item be in the set?"

It is designed for situations where storing every complete item would be expensive, but a fast approximate answer is acceptable. Like a Bloom filter, a Cuckoo filter stores a compressed representation of a set rather than the original values. However, it uses a different organization: it stores small fingerprints in one of two possible table locations, and it uses cuckoo eviction when both candidate locations are occupied.

The main ideas are:

1. Convert an item into a short fingerprint.
2. Compute two possible table locations for that fingerprint.
3. Store the fingerprint in one of those locations.
4. Query both locations when checking membership.
5. Move existing fingerprints when insertion encounters full locations.
6. Delete a fingerprint directly when removal is needed.

The result is a compact filter with efficient querying and support for deletion, making it useful when the set changes over time.

The membership problem​

Suppose an application repeatedly asks whether an item belongs to a large set. The items could be identifiers, keys, URLs, records, or other values. A straightforward solution is to store the complete set in a conventional data structure. That approach can provide exact answers, but it may require substantial memory.

A probabilistic filter takes a different approach. Instead of preserving each complete item, it stores a small summary. The summary is much smaller than the original data, so it can often be kept in memory and checked quickly.

The trade-off is that a filter may not always provide an exact answer. A typical filter is designed so that:

• If it says an item is definitely absent, the item is absent from the represented set.
• If it says an item may be present, the item might be present, but the answer can be a false positive.

A false positive occurs when the filter reports "possibly present" for an item that was never inserted. The filter does not need to store enough information to distinguish every item perfectly, so different items can sometimes produce matching stored summaries.

The central design goal is therefore to make the representation compact while keeping false positives acceptably rare and operations efficient.

Fingerprints: compact summaries of items​

A Cuckoo filter does not usually store a complete item in a table slot. Instead, it stores a short fingerprint derived from the item by hashing it.

For an item x, a hash function produces a binary value:

hash(x)

The filter keeps only part of that value, or otherwise derives a small fingerprint from it:

fingerprint(x)

For example, a conceptual fingerprint might be a short bit string such as:

101011

The exact number of bits is a design choice. A longer fingerprint uses more memory but generally makes accidental matches less likely. A shorter fingerprint saves memory but makes matching fingerprints more likely.

The fingerprint is not intended to reconstruct the original item. It is only a compact identifier used for comparison inside the filter. This distinction is important: the filter stores enough information to test its own representation, not enough information to recover the original data.

A table slot can contain one fingerprint or, in common bucket-based designs, a small collection of fingerprints. The essential idea is that fingerprints are placed into one of two candidate locations.

Two possible locations​

Each inserted item has two possible locations. One location is computed from the item itself, while the other is related to the first location and the fingerprint.

Conceptually, the two candidate locations can be written as:

i1 = index(hash(x))
i2 = alternate(i1, fingerprint(x))

The first index, i1, is derived from the item. The alternate index, i2, is computed using the first index and the fingerprint. A common conceptual form is:

i2 = i1 XOR hash(fingerprint)

where XOR is the bitwise exclusive-or operation. The exact implementation can vary, but the important property is that the second location can be derived from the first location and the fingerprint.

This relationship lets the filter relocate a fingerprint without retaining the complete original item. If a fingerprint is moved from one candidate location to the other, the filter can calculate the corresponding alternate location from the fingerprint and the location it currently occupies.

That is the structural idea behind cuckoo eviction.

What "dual hash tables" means​

The phrase "dual hash tables" can be understood as two choices for placement rather than necessarily two unrelated data structures. An item has two candidate positions, and its fingerprint may reside in either one.

A simplified table might look like this:

Location 0: [   ]
Location 1: [101011]
Location 2: [   ]
Location 3: [110001]
Location 4: [   ]

For a particular item, the filter might calculate candidate locations 1 and 4. If the fingerprint is found in either candidate location, the filter reports that the item may be present.

The two-location rule is valuable because it gives the insertion algorithm flexibility. A fingerprint does not have only one destination. If its first location is full, the algorithm can try its alternate location. If both are full, it can move another fingerprint out of the way and continue the process.

This is the same general spirit as cuckoo hashing: an element can occupy one of a small number of positions, and conflicts can be resolved by relocating existing elements.

Inserting an item​

Insertion begins by computing the item's fingerprint and its two candidate locations. The filter then attempts to place the fingerprint in one of those locations.

A conceptual insertion process is:

1. Compute fingerprint(x).
2. Compute the first candidate location.
3. Compute the alternate candidate location.
4. Check whether either location has available space.
5. Store the fingerprint in an available location.
6. If both locations are full, begin cuckoo eviction.

For example, imagine that an item has fingerprint 101011 and candidate locations 2 and 5. If location 2 has an empty slot, the filter stores the fingerprint there. If location 2 is full but location 5 has space, it stores the fingerprint at location 5.

The filter does not need to prefer one location universally. Either candidate can be used, depending on the implementation and current occupancy.

Cuckoo eviction​

The distinctive operation in a Cuckoo filter is cuckoo eviction. If both candidate locations are full, the filter selects an existing fingerprint from one of those locations and evicts it.

The evicted fingerprint is not discarded immediately. Because it has two possible locations, it can be moved to its alternate location. That move may free a slot for the new fingerprint.

A simplified sequence looks like this:

1. New fingerprint wants location A or B.
2. Both locations are full.
3. Select a stored fingerprint from location A.
4. Put the new fingerprint into the freed slot.
5. Move the evicted fingerprint to its alternate location.
6. If that location is full, evict another fingerprint.
7. Continue until a free slot is found.

For illustration, suppose a bucket has a stored fingerprint P, and a new fingerprint N needs that bucket. The algorithm can exchange them:

Before: bucket contains P
After:  bucket contains N
        P must move to its alternate bucket

At the next bucket, the same process may repeat. This creates an eviction chain. Each displaced fingerprint moves between its two permitted locations until the chain reaches an available slot.

The name "cuckoo" refers to this repeated displacement behavior. A newly inserted fingerprint can force an existing one out, much like an occupying item being replaced and relocated.

Why the fingerprint can be relocated​

A key technical requirement is that the filter must know where an evicted fingerprint can go next. It does not have the original item, so it cannot simply recompute both locations from the full key.

The solution is to make the two candidate locations related. If the current location is known and the fingerprint is stored with it, the alternate location can be derived:

next = alternate(current, fingerprint)

With an XOR-style relation, applying the same transformation again leads back to the other candidate location. Conceptually:

alternate(i1, f) = i2
alternate(i2, f) = i1

This gives every fingerprint a two-location route. During eviction, the filter can move the fingerprint from its current location to the other member of that pair.

This is one of the most important differences between simply storing random fingerprints and using a Cuckoo filter. The representation preserves enough placement structure to support movement.

Querying a Cuckoo filter​

A membership query follows the same placement logic used during insertion.

To query an item x, the filter:

1. Computes the item's fingerprint.
2. Computes the first candidate location.
3. Computes the alternate location.
4. Searches both locations for the fingerprint.

If the fingerprint appears in either location, the filter reports that the item may be present. If it appears in neither location, the filter reports that the item is absent.

Conceptually:

f = fingerprint(x)
i1 = first_location(x)
i2 = alternate(i1, f)

if f is in location i1 or location i2:
    return possibly_present
else:
    return definitely_absent

The query does not search the entire table. It checks only the item's two candidate locations, so the operation is focused and fast. The time complexity is O(1) on average, requiring only two table lookups and a fingerprint comparison.

The answer must be interpreted correctly. A positive result means that a matching fingerprint was found, not that the complete original item was proven to be present. Another item may have generated the same short fingerprint and occupied one of the candidate locations.

A negative result is stronger: if the fingerprint is absent from both candidate locations, the item could not have been stored according to the filter's placement rules.

False positives​

False positives are a natural consequence of fingerprint compression. Many complete items are mapped into a much smaller collection of possible fingerprints. Two different items can therefore share a fingerprint.

Suppose the filter stores the fingerprint for item A. Later, a query for item B produces the same fingerprint and the relevant candidate location contains that fingerprint. The filter may report that B is present even though only A was inserted.

The fingerprint length affects this behavior. With more fingerprint bits, there are more possible fingerprint values, so accidental matches become less likely. With fewer bits, the table uses less memory, but collisions become more likely.

The number of fingerprints stored and the occupancy of the table also influence practical false-positive behavior. A design must balance memory usage, capacity, and the acceptable probability of an incorrect positive result.

For a filter with m slots and fingerprints of b bits, the false-positive rate is approximately:

FPR ≈ (n / m) * (1 / 2^b)

where n is the number of inserted items. This shows that the false-positive rate depends on both the fingerprint length and the table occupancy. Doubling the fingerprint length roughly halves the false-positive rate, while doubling the table size also reduces the rate by approximately half.

A Cuckoo filter does not eliminate false positives; it manages them through the size and organization of fingerprints.

Deleting an item​

Deletion is a major feature of Cuckoo filters. To remove an item, the filter computes its fingerprint and its two candidate locations, just as it would for a query.

The deletion process is conceptually:

1. Compute fingerprint(x).
2. Compute the two candidate locations.
3. Search both locations for the fingerprint.
4. Remove a matching fingerprint if one is found.

After deletion, the corresponding slot becomes available for a future insertion.

This direct removal is useful because many sets are dynamic. Items may expire, be invalidated, or be removed as the application changes. A filter that supports deletion can update its summary without rebuilding the entire structure.

However, fingerprint-based deletion has an important interpretation. If several items produce the same fingerprint and share a candidate location, removing one matching fingerprint may also affect the filter's ability to represent another item with the same fingerprint. The filter stores fingerprints rather than complete identities, so it cannot always distinguish such cases using the fingerprint alone.

This illustrates the general trade-off of compressed representations: compact storage and fast operations are obtained by giving up some information about individual elements. In practice, this is rarely a problem if the fingerprint length is chosen appropriately, because the probability of multiple items sharing both a fingerprint and a candidate location is very low.

Comparing Cuckoo filters with Bloom filters​

Bloom filters are another well-known probabilistic membership structure. Both Bloom filters and Cuckoo filters store compact summaries and can answer membership queries without storing complete items in the filter.

Their internal approaches differ significantly.

A Bloom filter generally represents membership with a bit array. Insertion sets several bit positions derived from hashes of the item. Querying checks those positions. A Bloom filter does not normally store a separate fingerprint for each item; instead, it relies on the pattern of set bits to indicate membership.

A Cuckoo filter stores fingerprints in table locations. Each item has two candidate locations, and insertion can relocate existing fingerprints when necessary.

The supplied comparison highlights several practical differences:

The deletion distinction is especially important. In a basic Bloom filter, clearing a bit is unsafe because that bit may also be needed by other inserted items. More advanced variants like counting Bloom filters can support deletion by adding counters, but that changes the representation and its cost.

A Cuckoo filter's stored fingerprints make direct removal possible in its normal operating model. This does not mean it is always the best choice; the appropriate structure depends on the workload, memory target, desired error rate, and whether deletion is required.

In terms of memory efficiency, Bloom filters can be slightly more compact when targeting very low false-positive rates (below 1%), while Cuckoo filters often achieve better space efficiency for moderate false-positive rates (1-10%). The practical choice depends on the specific application requirements.

A small conceptual example​

Consider a filter with several locations. An item A produces fingerprint FA and candidate locations 1 and 4. The filter inserts FA into location 1.

A second item B produces fingerprint FB and candidate locations 1 and 3. If location 1 has an open slot, FB may be stored there as well, assuming a location can hold multiple fingerprints or the implementation has capacity available.

Now suppose item C produces fingerprint FC and candidate locations 1 and 4, and both locations are full. The filter chooses one stored fingerprint in location 1, say FA, and replaces it with FC. The filter then moves FA to its alternate location, which is location 4.

If location 4 is also full, the fingerprint displaced there is moved to its alternate location. The chain continues until an empty slot is found.

After the operation, all fingerprints still occupy one of their two valid locations, and the new fingerprint has been inserted without rebuilding the entire table.

A query for A recomputes FA and checks locations 1 and 4. If FA was successfully moved to location 4, the query can still find it. The physical location changed, but the membership rule did not.

This example demonstrates the key advantage of the two-location design: flexibility in placement and the ability to relocate items without losing track of them.

What happens when insertion cannot finish?​

Cuckoo eviction normally attempts to find a free slot through a sequence of relocations. However, a highly occupied table can create a cycle. A fingerprint may be moved through a repeating sequence of locations without reaching empty space.

A practical implementation therefore needs a bounded eviction policy. It can stop after a configured number of relocation attempts rather than continuing forever. If no slot can be made available, the insertion is considered unsuccessful under the current table configuration.

This is not a contradiction of the filter's design. Compact hash-based structures have capacity limits. As occupancy increases, insertion becomes more difficult, and the probability of long eviction chains or cycles increases.

Theoretically, if the table occupancy exceeds a certain threshold (typically around 50% for standard cuckoo hashing), the probability of insertion failure increases rapidly. This is why Cuckoo filters are typically maintained at occupancy levels below 90% to ensure reliable insertion.

Possible operational responses include allocating a larger table, rebuilding the filter, or rejecting the insertion. The particular response is an engineering decision and depends on the application's requirements. Some implementations use a secondary hash table or overflow area to handle insertions that cannot complete in the primary table.

Important implementation choices​

Several parameters influence the behavior of a Cuckoo filter:

Fingerprint length​

Longer fingerprints reduce accidental equality between different items, improving resistance to false positives. They also increase memory consumption. A common choice is 4 to 16 bits per fingerprint, depending on the target false-positive rate.

Bucket capacity​

A location may provide one slot or several slots for fingerprints. More capacity per bucket can make insertion more flexible, but it also affects memory layout and occupancy. Buckets with 2 to 4 slots are common in practice.

Table size​

A larger table provides more room for fingerprints and reduces pressure during insertion. A smaller table saves memory but reaches its capacity limit sooner. The table size should be chosen based on the expected number of items and the desired occupancy level.

Eviction limit​

An insertion should have a practical bound on the number of relocations it attempts. This protects the operation from spending unbounded time in a cycle. A limit of 100 to 1000 relocations is typical.

Hashing and fingerprint derivation​

The placement and fingerprint calculations should distribute items broadly across the available locations. Poor distribution can create unusually crowded regions, increasing collisions and eviction chains. High-quality hash functions are essential for good performance.

These choices should be evaluated together rather than independently. Saving memory by shortening fingerprints, reducing table size, and increasing occupancy can compound the likelihood of difficult insertions and false positives.

When a Cuckoo filter is useful​

A Cuckoo filter is a good conceptual fit when an application needs a compact membership summary and the represented set may change. Examples of requirements include:

• Checking whether a value might already have been seen, such as in deduplication systems.
• Avoiding expensive work for values that are definitely absent, such as checking a database before querying.
• Keeping a compact in-memory summary of a larger set stored elsewhere.
• Supporting item removal without rebuilding after every deletion.
• Performing membership checks through a small number of table lookups.
• Caching negative results efficiently in distributed systems.

The filter is not a replacement for an exact set when the application must prove membership. A positive result should usually be treated as a reason to perform a more authoritative check, while a negative result can be used to safely skip work when the filter's assumptions hold.

For example, a system might first query the Cuckoo filter. If the result is negative, it can conclude that the item is not represented by the filter. If the result is positive, it can consult a full database or exact data structure to distinguish a true match from a false positive.

Cuckoo filters are particularly valuable in scenarios where the set is frequently updated, because they support efficient deletion without the overhead of rebuilding or maintaining counters.

Practical mental model​

The easiest way to remember a Cuckoo filter is to separate the roles of its components:

• The fingerprint is the compact identity stored in the filter. It is derived from the item but is much shorter than the original.
• The two candidate locations tell the fingerprint where it is allowed to live. They are computed from the item and the fingerprint itself.
• The query recomputes those locations and searches both. If the fingerprint appears in either location, the item may be present.
• The eviction process moves existing fingerprints to their alternate locations when space is needed. This allows insertion to proceed without rebuilding the table.
• The deletion operation removes a matching fingerprint from either candidate location, freeing space for future insertions.

The filter is therefore more than a hash table containing shortened keys. Its placement relationship is what allows compact fingerprints to be moved while preserving the ability to find them later.

Key takeaways​

A Cuckoo filter is a probabilistic membership structure based on fingerprints and cuckoo-style placement. Instead of storing complete items, it stores short summaries in one of two possible locations.

Insertion first tries to place a fingerprint in an available candidate location. When both are full, the filter evicts an existing fingerprint and moves it to its alternate location, possibly creating a chain of relocations. This process is bounded to prevent infinite loops.

Querying computes the fingerprint and checks both candidate locations. A missing fingerprint gives a negative result; a matching fingerprint gives a possible positive result because fingerprints can collide. The query operation is very fast, requiring only two table lookups.

Deletion searches the same two locations and removes a matching fingerprint, which gives Cuckoo filters an important advantage for changing sets. This is a key difference from basic Bloom filters, which do not support efficient deletion.

Compared with Bloom filters, the most visible conceptual differences are fingerprint storage, cuckoo eviction, two-location lookup, and direct deletion. The right choice depends on the application's memory budget, acceptable false-positive behavior, update pattern, and need for removal.

The core idea is simple: store a small fingerprint, give it two possible homes, and move occupants between those homes when insertion needs space. This elegant design provides a practical balance between memory efficiency, query speed, and support for dynamic updates.