With conventional collision resolution methods like separate chaining and linear/quadratic probing, the probe sequence for a key can be arbitrarily long - it is simply kept short with high probability by keeping the load factor of the table low. Collisions during rehashing thus aren't a problem as they don't affect the load factor.However, with cuckoo hashing (and other methods offering worst-case O(1) lookup time?), a resize must happen when the probe sequence for a key gets too long. But when the keys get shuffled around during the rehash, it may be that they create a too-long probe sequence for one key, necessitating another resize - possibly several, if this happens multiple times in a row. The probability is small, especially with a good hash function, but I've seen it happen.Is there a way - short of explicitly generating a perfect hash function during the rehash - to ensure that resizes can't cascade in this manner? Possibly specific to a given collision resolution scheme? The literature I've encountered thus far seems to gloss over the matter entirely. Bear in mind that I'm also interested in shrinking hash tables, not just growing them.
How to avoid cascading resizes when resizing hash tables?
data structures;hash;hash tables