Cuckoo Filter (Fan, Andersen, Kaminsky, Mitzenmacher 2014)

A modern alternative that often beats Counting Bloom on both space and lookup time, and supports DELETE cleanly.

How it works

• A table of B buckets, each holding ~4 slots.
• Each slot can store a small fingerprint (e.g. 8 bits of a hash of the key).
• Each item has TWO candidate buckets:
  • i_1 = h(x) mod B
  • i_2 = i_1 XOR hash(fingerprint(x)) (partial-key cuckoo)

The XOR trick is the heart of the data structure: from (i, fingerprint) alone you can compute the OTHER candidate bucket. This is what lets you DISPLACE existing items during insert without needing the original key.

Insert (with cuckoo kick)

1. Compute fingerprint and i_1, i_2.
2. If either bucket has an empty slot, store the fingerprint there. Done.
3. Otherwise: pick i_1 or i_2 at random; evict a random fingerprint from that bucket; insert your fingerprint in its slot.
4. The evicted fingerprint goes to ITS alternate bucket (computed from the evicted fingerprint and the current bucket index via the XOR trick).
5. Repeat up to MAX_KICKS (~500) times. If still no room, declare the table full.

Lookup

Check both candidate buckets. Bounded: always at most 2 * BUCKET_SIZE = 8 slot comparisons.

Delete

Find the fingerprint in either of its two candidate buckets; clear that slot. Caveat: if two different items happened to have the same fingerprint AND landed in the same bucket, a delete could remove the wrong one. The fingerprint width is sized to make this vanishingly rare.

Why Cuckoo beats Counting Bloom

• ~10-20% better space at common FP rates.
• DELETE is clean (no saturation issue).
• Lookup time is bounded.
• No false negatives, exactly like Bloom.

When NOT to choose Cuckoo

• INSERT can fail (table full). You need a rebuild strategy.
• Construction is more complex; if you don't need delete, a plain Bloom is simpler.
• Recent comparisons (Quotient filter, Xor filter) sometimes beat Cuckoo on lookup cost and space; the field moves fast.