A cuckoo filter stores set membership using fingerprints in a cuckoo hash table. Each item hashes to two candidate buckets. If both are full, a random existing fingerprint is evicted to its alternate bucket, creating a chain of displacements, the cuckoo kick. This continues until an empty slot is found or a maximum kick count is reached.
The alternate bucket is computed from the current bucket index and the fingerprint itself: i₂ = i₁ XOR hash(fingerprint). This partial-key cuckoo hashing means the filter only needs to store fingerprints, not full keys. A lookup checks two buckets. A delete removes a matching fingerprint from either bucket.
Fan et al. introduced cuckoo filters at CoNEXT 2014, showing they outperform Bloom filters in both space and speed for false positive rates below about 3%. With 4 slots per bucket and 8-bit fingerprints, a cuckoo filter achieves roughly 95% occupancy before insertions start failing. Vacuum Filters (Wang et al., 2019) and Morton Filters (Breslow and Jayasena, 2018) extend the idea with better locality and higher load factors.
Watch the kick chains. Short chains (1-2 kicks) are common under low load. As occupancy climbs past 80%, chains get longer and more dramatic, sometimes cascading across half the table before finding an empty slot.
Fan et al. (CoNEXT 2014) / Wikipedia