数据结构 – 当有超过sizeof(邻居)实际哈希冲突时,Hopscotch哈希

发布时间：2020-12-16 05:03:49 所属栏目：百科来源：网络整理

导读：相关链接： http://en.wikipedia.org/wiki/Hopscotch_hashing 跳房子哈希表看起来很棒,但我没有在文献中找到这个问题的答案：如果我的邻居大小为N并且(由于渎职或极其糟糕的运气)会发生什么？我插入N 1个元素,这些元素都是相同的确切的价值？解决方法在原

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

跳房子哈希表看起来很棒,但我没有在文献中找到这个问题的答案：如果我的邻居大小为N并且(由于渎职或极其糟糕的运气)会发生什么？我插入N 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!.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!