data-structures - 当实际哈希冲突超过 sizeof(Neighborhood) 时，Hopscotch 哈希表中会发生什么？

Question

相关链接:http://en.wikipedia.org/wiki/Hopscotch_hashing

Hopscotch 哈希表看起来很棒，但我还没有在文献中找到这个问题的答案:如果我的邻域大小为 N 并且(由于渎职或非常糟糕的运气)我插入了 N+1 个元素，这些元素都哈希到相同的确切值？

Answer 1

原article据说需要调整表的大小:

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