How to expand the hashtable once capacity is full

[seiflotfy]

Hey Dave, Loving the Cuckoo Filter. Right now I am trying to figure out what the best strategy is to expand a Cuckoo Filter. Lets say my cuckoo Filter can take up to 1 million items max. Now once reached that limit I need to expand, the following 2 strategies come to mind: 1) create a second cuckoo filter (c2) and do any insertion there (making sure first it does not exist already in (c1) (i don't want to count duplicate items). How will this affect the false positive rate 2) Expand the current cuckoo filter by expanding the number of buckets and reallocating all the fingerprints. This however is flawed imho because i lost the "hash" of existing items already. All i can do is keep a count of the "expansion" requests and recalulcate the i1, and i2 (positions). But it then i can't do lookup on existing items Any thoughts? Cheers Seif

[skull-squadron]

To implement such efficiently would require something like "consistent cuckoo hashing" unless one wishes to take the penalty of rehashing old things. ;)