当有超过sizeof(邻居)实际哈希冲突时,Hopscotch Hash Tables会发生什么？

Question

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

跳房子哈希表似乎很棒,但我没有在文献中找到这个问题的答案:如果我的邻居大小为N并且(由于渎职或运气极差)会发生什么？我插入N + 1个元素,这些元素都是哈希同样的确切值？

Answer 1

在原始文章中写道，需要调整表的大小：

最后，请注意，如果 h 将超过恒定数量的项目散列到给定的存储桶中，则需要调整表的大小。幸运的是，正如我们所展示的，对于通用哈希函数 h，在给定 H = 32 的情况下发生这种类型的大小调整的概率是 1/32！