Probabilistic Filters By Example
I'm familiar with both cuckoo hashing and Bloom filters but had not until now seen a demonstration of cuckoo filters; they look very useful. But there is one stated fact that I'm finding hard to believe:<p>> Cuckoo filters improve on Bloom filters by supporting deletion<p>The page implies that this is achieved by removing the fingerprint from the hash table, but presumably one cannot guarantee that another key doesn't share the same fingerprint. This would result in a false negative for that key and violate an essential characteristic of the data structure.<p>Perhaps there's a nuance of the implementation I've missed.