What happens in Hopscotch Hash Tables when there are more than sizeof(Neighborhood) actual hash collisions?

Question

Relevant link: http://en.wikipedia.org/wiki/Hopscotch_hashing

Hopscotch hash tables seem great, but I haven't found an answer to this question in the literature: what happens if my neighborhood size is N and (due to malfeasance or extremely bad luck) I insert N+1 elements which all hash to the same exact value?

Answer 1

In the original article it is written that table needs to be resized:

Finally, notice that if more than a constant number of items are hashed by h into a given bucket, the table needs to be resized. Luckily, as we show, for a universal hash function h, the probability of this type of resize happening given H = 32 is 1/32!.