Cuckoo Filter

Cuckoo Filter is a compact, dynamic probabilistic data structure in computation and algorithms that tests approximate set membership with zero false negatives, worst-case O(1) lookup and deletion latency, and lower space overhead than a standard Bloom filter for false-positive rates ε < 3%. Introduced by Bin Fan, Dave G. Andersen, Michael Kaminsky, and Michael D. Mitzenmacher at ACM CoNEXT 2014, a cuckoo filter stores short f-bit fingerprints of inserted keys inside a bucketized cuckoo hashing table rather than setting bits in a flat bit array.

In computational complexity theory and high-throughput networking systems, classical Bloom filters prohibit element deletion (because clearing any bit B[h_i(x)] could create false negatives for other stored keys sharing that bit) and require k = ⌈0.693 (m/n)⌉ independent memory accesses per lookup. Counting Bloom filters support deletions only by inflating every bit into a 3- or 4-bit counter (3× to 4× memory overhead). By introducing partial-key cuckoo hashing—an involutory bitwise XOR relocation scheme that computes a fingerprint's alternate bucket address without retaining the original key—a cuckoo filter with 4-slot buckets achieves 95.5% table occupancy, executes every lookup and deletion in at most two CPU cache-line reads, and supports Semi-Sorting bucket compression that saves an additional 1 bit per item.

Why Standard Cuckoo Eviction Fails Without Full Keys

In standard cuckoo hashing (Pagh & Rodler, 2001), each key x is assigned two independent bucket locations i₁ = h₁(x) and i₂ = h₂(x) in an array of m buckets. When inserting a new key x into a full bucket i₁, the table evicts an existing occupant y from bucket i₁ and relocates y to its alternate bucket by recomputing h₁(y) and h₂(y) from the stored full key y.

In a compact approximate-membership filter, however, the full key y is discarded upon insertion; each slot stores only a short f-bit fingerprint τ = fingerprint(y) ∈ {1, ..., 2^f − 1} (typically f = 8, 12, or 16 bits, reserving the all-zero value 0 for empty slots). Because the original key y is no longer available during an eviction, evaluating an independent hash function h₂(y) is impossible.

The Involutory XOR Identity of Partial-Key Cuckoo Hashing

Fan, Andersen, Kaminsky, and Mitzenmacher solved this relocation problem by defining the second candidate bucket index i₂ as the bitwise exclusive-OR (⊕) of the first bucket index i₁ and the hash of the f-bit fingerprint τ = fingerprint(x), where the number of buckets m = 2^q is a power of two:

Because bitwise XOR is self-inverse (a ⊕ b ⊕ b = a), the relationship between i₁ and i₂ is fully symmetric:

Consequently, whenever an incumbent fingerprint τ sitting in any current bucket i ∈ {i₁, i₂} is evicted during an insertion, its twin candidate bucket j is computed directly from i and τ alone—without knowing the original key x or even whether i was originally i₁ or i₂:

Notably, hashing the fingerprint via h₂(τ) (rather than XORing the raw f-bit integer τ directly into i₁) is essential: if τ were XORed without hashing when 2^f ≪ m, the alternate bucket i₂ would always lie within ±2^f slots of i₁, causing pronounced localized clustering and premature insertion failure. Applying an invertible mixing hash h₂(τ) distributes alternate buckets across the entire m-bucket table.

Bucketized (d = 2, b = 4) Layout and Lookup

A canonical cuckoo filter consists of an array T[0 .. m − 1] of m buckets, where each bucket holds b = 4 fingerprint slots of f bits each. To test whether a query key x is in the set (Lookup(x)):

1. Compute the f-bit non-zero fingerprint τ = fingerprint(x), the primary bucket i₁ = h₁(x), and the alternate bucket i₂ = i₁ ⊕ h₂(τ).
2. Read the 4 slots of bucket T[i₁] and the 4 slots of bucket T[i₂] (which can be compared against τ in a single SIMD instruction). If any of the 2b = 8 slots contains τ, return true; otherwise return false.

Eviction Insertion and Safe Deletion

• Insertion (Insert(x)): Compute τ, i₁, and i₂. If either bucket T[i₁] or T[i₂] has a vacant slot, store τ in that slot and return. Otherwise, pick i ∈ {i₁, i₂} at random and enter the cuckoo eviction loop (for up to MaxNumKicks = 500 iterations): randomly select one of the b = 4 fingerprints τ′ in T[i], swap τ ↔ τ′, update i ← i ⊕ h₂(τ), and return as soon as T[i] has a free slot.
• Deletion (Delete(x)): Compute τ, i₁, and i₂. If either bucket T[i₁] or T[i₂] contains a matching copy of τ, clear one matching copy to 0 and return true. (As in any deletion-capable filter, only keys known to have been previously inserted may be deleted so as not to remove another member key that collided on both bucket and fingerprint; if identical keys are inserted multiple times, up to 2b = 8 duplicate copies can be stored across the two buckets.)

Fingerprint Length f as a Function of False-Positive Rate ε and Bucket Size b

When querying a non-member key y ∉ S, the query inspects 2b slots across the two candidate buckets T[i₁] and T[i₂]. A false positive occurs if any of the occupied slots in those two buckets holds the same f-bit fingerprint τ = fingerprint(y). Because each stored fingerprint matches τ independently with probability 1 / 2^f, the probability of a false positive across at most 2b comparisons is bounded by:

Solving for the required fingerprint bit width f yields:

Dividing by the maximum load factor α of a (d = 2, b)-slot cuckoo table gives the amortized space cost C in bits per stored item:

Because a Bloom filter scales multiplicatively as 1.4427 log₂(1/ε) bits per item whereas a (b = 4) cuckoo filter scales additively as (log₂(1/ε) + 3) / 0.955 bits per item, cuckoo filters use less memory than Bloom filters whenever ε < 3% (and under Semi-Sorting compression—which sorts the 4 fingerprints inside each bucket and encodes their high-order bits via a 12-bit permutation index, saving 1 bit per item—whenever ε < 2%).

In a 4-slot bucket (b = 4), the order of the 4 fingerprints within the bucket carries no semantic meaning. By sorting the four f-bit fingerprints in each bucket and grouping their 4 most significant bits into one of the (16 + 4 − 1 choose 4) = 3,876 monotonic 4-tuples—which fits inside a 12-bit table index instead of 4 × 4 = 16 bits—Semi-Sorting saves 4 bits per bucket (1 bit per item), lowering the cost to (log₂(1/ε) + 2) / 0.955 bits per item.

From a theoretical perspective,David Eppstein (2016) proved that because partial-key cuckoo hashing restricts the alternate bucket difference i₁ ⊕ i₂ to the 2^f values of h₂(τ), high-probability insertion ensures hold rigorously when the fingerprint width satisfies f = Ω((log n) / b). When b = 4 and f ≥ 8 bits, empirical and asymptotic analyses confirm 95.5% occupancy across multi-billion-key tables in network routers, consistent hashing directory caches, and distributed database storage engines alongside the quotient filter and Xor filter.

What happens if more than 2b = 8 keys collide on both the primary bucket i₁ and the f-bit fingerprint τ?

Because two keys with the same primary bucket i₁ and the same fingerprint τ also share the precise same alternate bucket i₂ = i₁ ⊕ h₂(τ), at most 2b (8 for b = 4) such identical-fingerprint keys can fit into buckets i₁ and i₂ combined. To keep the probability of > 2b identical (i₁, τ) collisions negligible across n keys, the total number of distinct (i₁, τ) pairs m · 2^f must outscale n, which requires f = Ω((log n) / b) bits (typically f ≥ 8 bits for b = 4).

Why can a Cuckoo Filter not use f = 0 or omit fingerprints altogether?

Even if false positives did not matter, partial-key cuckoo hashing requires storing a non-zero fingerprint τ in each slot so that an evicted item can compute its alternate bucket i₂ = i₁ ⊕ h₂(τ), and it reserves the value τ = 0 to mark unoccupied slots (re-mapping any key whose hash produces 0 to τ = 1).

1. Fan, B., Andersen, D. G., Kaminsky, M., & Mitzenmacher, M. D. (2014). "Cuckoo Filter: Practically better than Bloom." Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies (CoNEXT '14), 75–88. https://doi.org/10.1145/2674005.2674994
2. Pagh, R., & Rodler, F. F. (2004). "Cuckoo hashing." Journal of Algorithms, 51(2), 122–144. https://doi.org/10.1016/j.jalgor.2003.12.002
3. Dietzfelbinger, M., & Weidling, C. (2007). "Balanced allocation and dictionaries with tightly packed constant size bins." Theoretical Computer Science, 380(1–2), 47–68. https://doi.org/10.1016/j.tcs.2007.02.054
4. Eppstein, D. (2016). "Cuckoo filter: Simplification and analysis." Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), LIPIcs Vol. 53, 8:1–8:12. https://doi.org/10.4230/LIPIcs.SWAT.2016.8
5. Breslow, A. D., Zhang, D. P., Greathouse, J. L., Jayasena, N., & Tullsen, D. M. (2016). "Horton tables: Fast hash tables for in-memory data-intensive computing." Proceedings of the 2016 USENIX Annual Technical Conference (USENIX ATC '16), 281–294. https://doi.org/10.5555/3026959.3026986