Cuckoo Filter

Stores a short fingerprint of each item in one of two candidate buckets, using the same "kick out and relocate" trick as cuckoo hashing. Supports deletion and often beats Bloom filters on space at low false-positive rates.

How it works

Each item is reduced to a short fingerprint (a few bits, e.g. 8) and a first candidate bucket bucketA = hash(item). The second candidate bucket is bucketB = bucketA XOR hash(fingerprint): the "partial-key cuckoo hashing" trick, which means you can recompute either bucket from the other plus the fingerprint alone, without re-hashing the original item. That's what makes deletion possible.

add() places the fingerprint in whichever candidate bucket has a free slot. If both are full, it picks an existing fingerprint at random, evicts ("kicks") it to its alternate bucket, and repeats, cascading evictions just like cuckoo hashing, up to a max-kicks limit before giving up (meaning the filter is too full for its size).

contains() just checks both candidate buckets for the fingerprint, no eviction needed. remove() clears it from whichever bucket holds it.

Interactive demo

Buckets × slots12 × 4
Load factor0.0%
Capacity48
0
·
·
·
·
1
·
·
·
·
2
·
·
·
·
3
·
·
·
·
4
·
·
·
·
5
·
·
·
·
6
·
·
·
·
7
·
·
·
·
8
·
·
·
·
9
·
·
·
·
10
·
·
·
·
11
·
·
·
·
No operations yet. Try adding an item above.

API surface

OperationDescriptionComplexity
new CuckooFilter(buckets, slotsPerBucket?, fpBits?)Allocate buckets × slotsPerBucket fingerprint slots.O(buckets × slots) space
add(item): booleanInsert a fingerprint, evicting/relocating on collision. False if max kicks exceeded.O(1) amortized
contains(item): booleanCheck both candidate buckets for the fingerprint.O(slots) time
remove(item): booleanClear the fingerprint from whichever bucket holds it.O(slots) time

References

Original papers

Library implementations

Real-world use cases