Cuckoo filter

A cuckoo filter is a space-efficient probabilistic data structure for testing whether an element belongs to a set, in the same role as a Bloom filter. A query returns either possibly in set or definitely not in set, so false positives are possible but false negatives are not. Unlike a Bloom filter, a cuckoo filter can also delete items, and for applications that store many items and aim at moderately low false positive rates it can use less space than a space-optimized Bloom filter. It stores short fingerprints of items in a hash table based on cuckoo hashing, split into buckets of some size b. Each item has two candidate buckets: the first comes from hashing the item, and the second is found by combining the first with a hash of the fingerprint using exclusive or, so either bucket can be computed from the other. Cuckoo filters were first described in 2014.