Cuckoo filter
A membership test like a Bloom filter, with one thing added: you can take items back out. The no-false-negative guarantee gains conditions in exchange, and they are worth reading.
Where this is actually used
Anywhere a Bloom filter would fit but the set keeps changing — a cache directory, a list of revoked certificates, the pieces a peer already holds. A Bloom filter cannot forget: anything dropped from the real set stays in the filter forever, so the only way to remove something is to rebuild the whole filter. This one deletes in place.
The guarantee
A lookup never misses an item the filter holds — provided no insert has failed and nothing was deleted that was not first inserted. Bloom’s guarantee has no conditions and Bloom cannot delete. That is the trade.
How it works
A short fingerprint of each item, stored in one of two candidate buckets. The second bucket is i₁ ⊕ h(fingerprint), so a displaced entry’s other home is computable from the fingerprint alone — which is what lets the table move entries it no longer has the items for.
At most 2b copies of one item fit, ever — identical items give identical fingerprints and identical buckets. A skewed stream therefore makes this filter refuse inserts while it is nearly empty. Bloom is completely indifferent to repeats.
Fan, Andersen, Kaminsky & Mitzenmacher, CoNEXT 2014