Cuckoo Filter

Why Not Just Use a Bloom Filter?

A Bloom filter answers membership queries by hashing an item with several independent hash functions and setting the corresponding bits in a shared bit array. Checking membership means checking whether all those bits are set. This design is compact and fast, but it has a structural flaw: once bits are set, the filter has no idea which item caused which bit to flip, because many items can share the same bit. That means you can never safely clear a bit to remove one item, since doing so might silently break membership tests for other items that happen to rely on that same bit.A cuckoo filter sidesteps this problem entirely by changing what gets stored. Rather than scattering bits across a shared array, it stores a small, explicit fingerprint, a short bit string derived from hashing the item, inside one particular slot of a bucketed hash table. Each fingerprint occupies its own identifiable slot rather than contributing anonymously to shared bits. That structural difference is what makes deletion tractable: to remove an item, the filter just needs to locate its fingerprint in one of its two candidate buckets and clear that specific slot, with no risk of collateral damage to other stored items.This does not mean cuckoo filters are strictly better in every dimension. Bloom filters remain simpler to implement, have no eviction logic to worry about, and can be tuned smoothly for extremely low false-positive rates by adding more hash functions and bits. Cuckoo filters, in exchange for supporting deletion, need a bit more bookkeeping and can, in rare cases, fail to insert an item if eviction chains do not terminate within a bounded number of kicks. In practice, though, for the same target false-positive rate, cuckoo filters are often more space-efficient than Bloom filters, particularly at low false-positive rates, and they add lookup and deletion that behave predictably against individual fingerprints rather than shared bits. The choice between the two comes down to a simple question: does your workload ever need to remove items from the set? If yes, the cuckoo filter's design advantage becomes decisive.

Fingerprints Instead of Bit Flips

The core building block of a cuckoo filter is the fingerprint: a short, fixed-length bit string produced by hashing the original item and truncating or otherwise deriving a compact summary from that hash. A typical fingerprint might be just four to sixteen bits long, far smaller than the item itself. This is a lossy compression on purpose. The filter never stores the original item, only this small fingerprint, which is what keeps the overall structure compact.Because a fingerprint is so short, many different items can, in principle, hash to the same fingerprint value. This is the source of the cuckoo filter's false positives: if you query an item that was never inserted, but its fingerprint happens to match one already sitting in one of its two candidate buckets, the filter will incorrectly report that the item is present. The probability of this happening is governed directly by the fingerprint length. Longer fingerprints mean fewer collisions and a lower false-positive rate, but they also mean the table consumes more memory per stored item, so fingerprint length is the primary knob for trading accuracy against space.What fingerprints do not do is preserve any usable information about the original item. You cannot reconstruct the item from its fingerprint, and the filter never needs to, because every operation, insertion, lookup, and deletion, only ever needs to know the fingerprint value and the two bucket indices it could possibly live in. This is a deliberate design constraint that keeps the structure both compact and self-contained: everything the filter needs to relocate or verify a fingerprint is derivable on the fly from the fingerprint itself, never from a stored copy of the original data.

The Two-Bucket Trick: Finding a Fingerprint's Alternate Home

Classic cuckoo hashing stores full keys or key-value pairs, and each key's alternate bucket is usually computed by hashing the key itself with a second hash function. A cuckoo filter cannot do this directly, because it deliberately throws away the original item after computing the fingerprint, keeping only the short fingerprint in the table. So how does it know where a fingerprint's second candidate bucket is, if it no longer has the item to rehash?The answer is a small piece of mathematical elegance. When an item is first inserted, the filter computes its first bucket index by hashing the item directly, call this bucket i1. It then computes the fingerprint f of the item as usual. The second candidate bucket, i2, is computed not by hashing the item again but by XORing i1 with a hash of the fingerprint f. This formula has a beautiful self-inverting property: applying the exact same operation again, XORing i2 with the hash of f, returns you to i1. In other words, from either bucket index alone, plus the fingerprint sitting inside it, the filter can always recompute the other candidate bucket without ever needing the original item again.This is precisely what allows eviction chains to work. During insertion, if both of a new fingerprint's candidate buckets are already full, the filter picks a victim fingerprint from one of the occupied slots, evicts it, and needs to find that victim a new home. Since the victim is just a fingerprint sitting in a bucket, the filter recovers its alternate bucket using the XOR formula, then tries to place it there, potentially triggering another eviction. This cascades, bucket by bucket, until an empty slot is found or a maximum number of relocation attempts is reached. It is exactly the same displacement idea used in cuckoo hashing, just operating on compact fingerprints instead of full keys.

Insertion, Lookup, and the Cascading Eviction Chain

Inserting an item into a cuckoo filter begins by computing its fingerprint and its two candidate buckets, i1 and i2, using the item's hash and the XOR relationship described above. If either bucket has a free slot, and buckets typically hold several slots each to improve load factor, the fingerprint is simply placed there and insertion is done. The interesting case is when both candidate buckets are completely full. The filter then picks one of the two buckets, selects one of its occupied slots at random, and evicts that fingerprint, writing the new fingerprint into the freed slot. The evicted fingerprint is not discarded; the filter computes its alternate bucket via the same XOR trick and attempts to insert it there, possibly evicting yet another fingerprint in turn. This chain of displacements continues until some bucket has room, or until a configured maximum number of kicks is exhausted, at which point the filter is considered too full and the insertion fails, signaling that it is time to resize or rebuild with a larger table.Lookup is comparatively simple and always terminates quickly. To check whether an item might be in the set, the filter computes its fingerprint and both candidate bucket indices, then checks whether that fingerprint appears in either bucket. If it does, the filter reports the item as present, possibly a false positive; if not, it reports the item as absent, and this negative answer is always correct, since a genuinely inserted fingerprint would necessarily still be sitting in one of its two candidate buckets.Deletion mirrors lookup almost exactly, which is the whole point of the structure. The filter computes the fingerprint and its two candidate buckets, searches both for a matching fingerprint, and if found, clears that specific slot. Because the fingerprint occupies an identifiable slot rather than shared bits, this operation is entirely safe and cannot corrupt the membership status of any other stored item, something a Bloom filter fundamentally cannot guarantee.

Practical Trade-offs and Real-World Use

Cuckoo filters shine in systems that need approximate membership testing over sets that change over time, not just grow. Classic Bloom filter use cases, like quickly rejecting a cache miss before hitting a slow disk or network lookup, checking whether a URL is on a known blocklist, or filtering duplicate work items in a stream, often also need to remove entries as data expires or becomes stale. Databases, network routers doing flow tracking, and caching layers have all adopted cuckoo filters specifically because their working sets shrink as well as grow, and rebuilding an entire Bloom filter from scratch just to remove a handful of stale items is often too expensive to do frequently.The trade-offs are real, though. Cuckoo filters generally need to keep their load factor below a threshold, often somewhere around ninety to ninety-five percent depending on bucket size, to keep eviction chains short and insertion failures rare. Push the table too close to full and insertions can start failing even though, in principle, there is still room somewhere in the table; the filter simply cannot find a path to it within the retry budget. This means capacity planning matters more for cuckoo filters than for Bloom filters, which degrade more gracefully, just with a rising false-positive rate, as they fill up.There is also a subtle correctness caveat worth internalizing: deleting an item that was never actually inserted is dangerous. If a lookup returns a false positive for some item and code mistakenly deletes it, that deletion might remove a fingerprint that actually belongs to a different, legitimately inserted item sharing the same fingerprint value, since fingerprints are not unique identifiers. Correct usage requires that deletions only ever be issued for items that the application can independently confirm were inserted, a discipline that Bloom filters, by having no deletion at all, never had to worry about. Choosing between a Bloom filter, a cuckoo filter, and heavier structures like counting Bloom filters ultimately comes down to weighing memory budget, mutability needs, and how carefully the surrounding application can track what was actually inserted.

Frequently asked questions

Try it live

Everything above runs in your browser — open Cuckoo Filter and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.