线性探测中的聚类如何影响搜索时间
How clustering in linear probing affect the search time
我理解线性探测中的问题，因为后续索引会有元素簇。但我不明白这个说法 The bigger the cluster gets, more it reduces the performance. 它如何降低散列的性能？
对于第一次插入空哈希 table，我们保证不会遇到任何冲突。假设为了论证我们很不走运——我们的第二次插入散列到与第一次相同的插槽，我们必须执行（非常小的）线性搜索以找到下一个空闲插槽。对于 n 个插槽的 table，此冲突的概率为 1/n。
现在我们有两个彼此相邻的空 table。我们下一次插入与这个集群碰撞的几率是多少？不是第二次插入时的 1/n，而是现在的 2/n - 机会增加了。某些东西散列到 k-slot 簇的几率是 k/n，当他们这样做时，他们必须一直线性搜索到簇下到最后，不仅浪费时间而且增加了长度集群！
问题是模式是 self-reinforcing，当你的 table 变满时，你的插入时间可能接近 O(n)。
我理解线性探测中的问题，因为后续索引会有元素簇。但我不明白这个说法 The bigger the cluster gets, more it reduces the performance. 它如何降低散列的性能？
对于第一次插入空哈希 table，我们保证不会遇到任何冲突。假设为了论证我们很不走运——我们的第二次插入散列到与第一次相同的插槽，我们必须执行（非常小的）线性搜索以找到下一个空闲插槽。对于 n 个插槽的 table，此冲突的概率为 1/n。 现在我们有两个彼此相邻的空 table。我们下一次插入与这个集群碰撞的几率是多少？不是第二次插入时的 1/n，而是现在的 2/n - 机会增加了。某些东西散列到 k-slot 簇的几率是 k/n，当他们这样做时，他们必须一直线性搜索到簇下到最后，不仅浪费时间而且增加了长度集群！ 问题是模式是 self-reinforcing，当你的 table 变满时，你的插入时间可能接近 O(n)。