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

Question

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

Hopscotch 哈希表看起来很棒，但我在文献中没有找到这个问题的答案：如果我的邻域大小为 N 并且（由于渎职或非常倒霉）我插入 N+1 个元素，所有这些元素都散列到相同的确切值？

Answer 1

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

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

Answer 2

有两种情况我们需要调整 hopscotch hash

1. 对于给定的存储桶，您有 H 次碰撞
2. 负载因子真的太大了，找不到空闲的桶。在实践中，您应该为免费搜索桶设置一个上限。

给定通用哈希函数，你只有 1/32！有机会进入案例＃1，换句话说，如果您连续插入 2^35 个元素，那么您有一次机会因碰撞而调整大小。

案例#2在实践中是resize的更流行的原因，你可以参考一些二次实现他们如何决定resize[C# hashmap和Google sparse hashmap]，由于它的集群缺点，没有真正的线性探针实现，即不能保证不断查找。