Cuckoo filters

A cuckoo filter is an approximate membership structure that stores short fingerprints in a bucketized cuckoo hash table. It supports lookup, insertion, and deletion, but every operation has a precise contract.

Two candidate buckets

For key (x), compute fingerprint (f), primary bucket (i_1), and alternate bucket (i_2) derived so that the alternate location can be recovered from a stored fingerprint. Lookup searches both buckets.

• no matching fingerprint means "absent" under the implementation's hash/overflow assumptions;
• a match means "possibly present" and can be a false positive.

The false-positive rate depends on fingerprint width, bucket size, load, and implementation details. Do not quote one universal formula without pinning those parameters.

Insertion and load

Insert into a free slot in either bucket. If both are full, evict a fingerprint and move it to its alternate bucket, repeating up to a bounded kick limit. Insertion can fail near high load. A production design must resize/rebuild, use a stash or exact overflow, or reject without losing the authoritative mutation.

Never acknowledge an authoritative insert solely because the filter insert succeeded. The source of truth owns membership.

Deletion caveat

Deletion is safe for a key known to have been inserted under the filter's multiplicity policy. Deleting an arbitrary key after only an approximate positive can remove an unrelated stored fingerprint that caused the false positive. Duplicate logical inserts also require counts or set semantics outside a bare filter.

Concurrency and versioning

Bucket relocation touches multiple slots. Use the implementation's locking, optimistic version, or single-writer protocol so readers never observe an invalid half-move. Pin hash, fingerprint width, bucket size, and table generation; do not merge raw tables with different parameters.

Diagram scenarios

The animation covers two-bucket lookup, free-slot insertion, bounded relocation, insertion failure, exact-state-backed deletion, and rejection of delete-on-maybe.

Related concept

Interactive scenarios