我理解线性探测中的问题，即由于后续索引将存在元素簇。但我不明白这句话The bigger the cluster gets, more it reduces the performance.如何降低散列的性能？
问问题
140 次
1 回答
1
对于第一次插入空哈希表，我们保证不会遇到任何冲突。假设我们很不走运——我们的第二次插入哈希到与第一次相同的插槽，并且我们必须执行（非常小的）线性搜索以找到下一个空闲插槽。对于 n 个时隙的表，这种冲突的概率是 1/n。现在我们在一张原本空荡荡的桌子上有两个相邻的。我们下一次插入与这个集群碰撞的几率是多少？不是第二次插入时的 1/n，而是现在 2/n - 机会增加了。某个东西散列到 k-slot 集群的几率是 k/n，当他们这样做时，他们必须一直线性搜索到集群到底，不仅浪费时间，而且增加了集群的长度！问题是这种模式是自我强化的，
于 2020-10-18T10:27:17.367 回答