Cuckoo Filter
Fingerprints in buckets · two candidate buckets · cuckoo kick-out relocation · lookup · delete
Lookup
O(1)
Delete
O(1)
Insert
O(1) amortized
FPR
≈ 2b / 2^f
i2 = i1 XOR hash(f)
Controls
Insert
Lookup
Delete
Random Insert
Reset
Speed
slow
fast
candidate bucket
insert / found
evicted (kick-out)
scanning
delete
Hash Trace
Insert, look up, or delete an item to see how its fingerprint and two candidate buckets are computed.
Buckets (each holds b = 4 fingerprints; 0 = empty)
items:
0
capacity:
0
load:
0%
kicks (last):
0
Last Operation
Ready. The filter starts empty.
Load Factor & FPR
fingerprint bits f
FPR ≈ 2b/2^f (b=4)
8
3.1%
10
0.78%
12
0.20%
16
0.012%
bucket size b
max load factor
1
~50%
2
~84%
4
~95%
8
~98%
Operation Log