4 ms·
"These filters can claim that a given entry is definitely not represented in a set of entries, or might be represented in the set." unless the Cuckoo filter ha
by chronolitus 9y ago
"These filters can claim that a given entry is definitely not represented in a set of entries, or might be represented in the set."
unless the Cuckoo filter has any two filled buckets, right? Which is a pretty critical failure mode not mentioned here. (What do you do then, accept the small new false-negative likelihood? start over with another filter?)
- jetrink 9y agoIf both buckets are filled, one of the existing occupants is evicted and reinserted at its alternate location. If there is an item already at that location, it is likewise evicted and reinserted. This process continues until an open space is found or a loop is detected. If there is a loop, the hash table needs to be rebuilt with more capacity or new hash functions.
- bdupras 9y agochronolitus did jetrink's comment answer your question? I'm happy to further clarify if needed.
- chronolitus 9y agoah, I understand. The website demo had me confused. thanks for your help!