While Bloom Filters are widely used, the inability to delete items is a significant limitation for applications where the working set changes over time — for example, a cache that expires entries, or a fraud detection system that clears old flagged accounts.
Cuckoo Filters are a modern alternative that supports deletions and can be more space-efficient than Bloom Filters at low false-positive rates (below ~3%).
How Cuckoo Filters Work
Instead of a bit array, a Cuckoo Filter uses a compact hash table of small fingerprints — typically 4–8 bits per entry. Each item maps to two candidate bucket positions (computed from its hash). The filter stores the item's fingerprint in one of these two buckets.
Insertion: Compute the fingerprint f and two candidate buckets b1 and b2. If either bucket has an empty slot, store f there. If both are full, evict a random existing fingerprint from one bucket, move it to its alternative bucket, and repeat. This "cuckoo displacement" process continues until an empty slot is found or a maximum number of kicks is reached (at which point the filter is considered full).
Lookup: Check both candidate buckets for the fingerprint. If found in either, the item might be in the set.
Deletion: Find the fingerprint in one of the two candidate buckets and remove it. This works correctly because the fingerprint is stored explicitly, not just implied by bit positions.
Bloom vs. Cuckoo: When to Use Which
| Property | Bloom Filter | Cuckoo Filter |
|---|---|---|
| Deletion support | No (standard) | Yes |
| Space efficiency (low FPR) | Good | Better |
| Lookup performance | O(k) hash computations | O(1) — check 2 buckets |
| Insertion worst case | O(k) | O(1) amortized, can fail when full |
| Implementation complexity | Simple | Moderate |
Use a Bloom Filter when your set is write-once and you need simplicity. Use a Cuckoo Filter when you need deletions or when lookup speed is critical at very low false-positive rates.