Build a Cuckoo Filter

fingerprints with cuckoo kicking

Challenge 2 of Probabilistic StructuresAdvanced~50 min

A Bloom filter that supports deletion. Store compact fingerprints in two candidate buckets, look items up in O(1), relocate entries with cuckoo 'kicking' to make room under load, and delete cleanly. The approximate-membership structure used when you need to remove items, not just add them.

4 steps

1. 1Fingerprints and Buckets
2. 2Insert and Lookup
3. 3Cuckoo Kicking
4. 4Deletion