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

There are two cases where we need resize hopscotch hash

1. you have H collisions for the given bucket
2. the load factor is really too big to find the free bucket. In practice, you should setup a uplimit for search free bucket.

Given the universal hash function, you only have 1/32! chance to get into case #1, in other word, if you continuously insert 2^35 elements, then you have one chance to resize due to collisions.

The case #2 is more popular reason for resize in practice, you could refer to some quadratic implementations for how they decide to resize[C# hashmap and Google sparse hashmap], there is no real implementation for linear probe due to its cluster drawback, i.e. can't guarantee constant lookup.

Answer 2

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!.