How to avoid cascading resizes when resizing hash tables?

Question

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.

Answer 1

You ask how to avoid cascading rehashes but you already gave the answer in your post. You keep the probability that bad events occur small.

Since you mention cuckoo hashing. The probability that you get a long probing sequence is $O(1/n^2)$. So if you rehash, you are inserting $n$ elements from scratch. The probability that the rehash is not successful is then $O(1/n)$, so with very high probability you are successful. In expectation you need only a constant number of tries. If you observe that you have problems with rehashing, then you should increase your table size and modify your load factor. Alternatively you can select a better family of hash functions.

Answer 2

I believe I have one solution, inspired by linear hashing:

If the hash function(s) is held constant (that is, not changed when resizing) and the table is always grown by doubling the slots, then after the table is grown, it holds that

$H \mod 2L = \begin{cases} H \mod L + L & \text{or} \\ H \mod L \end{cases}$

where $H$ is the hash of a key and $L$ is the old number of slots. This means that a key either stays where it is or moves to a unique slot in the newly allocated area, which is guaranteed to be empty.

To apply this to (d-ary) cuckoo hashing, simply resize each of the subtables individually and don't move keys between subtables.

To shrink the table, you need to confirm that one of $\lbrace H \mod \frac{L}{2} + \frac{L}{2}, ~ H \mod \frac{L}{2} \rbrace$ is vacant for every key in the table, and if so, move them all to their $H \mod \frac{L}{2}$ slots. Of course, this is $O(n)$... I'm not sure if there's a better way to do this than running the check for every deletion once the load factor drops below half.