平方探测在线性探测之上的优势

Question

5

给定哈希值时，线性探测法生成的索引如下：h，h+1，h+2，h+3，等等。

给定哈希值时，二次探测法生成的索引如下：h，h+1，h+4，h+9，等等。

在线性探测中会形成聚簇，而在二次探测中不会。

但是，为什么二次探测比线性探测更有效，即使两种方法在插入或搜索时需要执行相同数量的步骤呢？谢谢！

- hoder

3个回答

8

当你遇到一个空槽时，就可以停止在哈希表中查找，因为如果你遇到了一个空槽，那么你要查找的值不会在哈希表中。由于减少了聚集，你更有可能遇到一个空槽并停止搜索。此外，由于减少了聚集，插入时更容易找到空槽，从而能更快地查找该值。

- user2902179

3

由于聚类形成较少，因此数值将更加分散，因此在二次情况下所需的平均探测次数将较少。

- user207421

如果插入相同哈希值（哈希函数返回的值）的数据项数量相等，那么在这两种情况下探测次数不就相等吗？ - hoder

请提供更多的解释。 - hoder

@hoder，你不明白“平均探测次数将会减少”的哪一部分？ - user207421

3

@EJP: 它将如何变得更少？在查找元素时，您不会线性探测。您将进行二次探测，就像插入密钥时所做的那样。我理解这将导致较少的簇形成。但是，您提出的论点并不可靠。 - Neo M Hacker

@NeoMHacker 但是用户2902179提出的相同论点也是有效的吗？ - user207421

如果一个元素恰好在大小为k的簇中，那么在线性探测的情况下，需要O(k)次迭代才能走出簇，但在二次探测的情况下只需要O(sqrt(k))次。 - fdermishin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Yogesh Umesh Vaity · Accepted Answer

效率取决于线性探测和二次探测所形成的聚类类型。

线性探测形成主聚类，一旦形成，聚类越大，增长速度就越快。这会严重降低性能。Robert Lafore 给出了一个很好的例子：就像在购物中心有人晕倒时聚集的人群。最初的人是因为看到受害者摔倒而来的；后来的人则是因为想知道其他人在看什么。人群越大，吸引的人就越多。

相反，二次探测形成次要聚类。它试图防止形成聚类。其想法是探测距离主哈希位置更远的单元格，而不是邻近的单元格。沿用上述类比，它试图防止第一批到达的人形成人群。次要聚类相对于主聚类来说，在性能方面更加微妙，影响也不那么严重。