data-structures - 二次探测优于线性探测

Question

对于给定的哈希值，线性探测生成的索引如下：

h, h+1, h+2,h+3等..

对于给定的哈希值，二次探测生成的索引如下：

h, h+1, h+4,h+9等..

在线性的情况下会形成簇，但在二次的情况下不会。

但是，当两个过程（方法）都需要采取相同数量的插入或搜索步骤时，为什么二次比线性更有效。谢谢！

Answer 1

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

线性探测形成初级聚类，一旦形成，簇越大，增长越快。这会严重降低性能。罗伯特·拉福尔举了一个很好的例子：就像有人在购物中心晕倒时聚集的人群。第一批来是因为他们看到受害者摔倒了；后来到达的人聚集在一起，因为他们想知道其他人在看什么。人群越多，吸引的人就越多。

其中二次探测形成二次聚类。这是一种阻止集群形成的尝试。这个想法是探测更广泛分离的单元，而不是那些与主哈希站点相邻的单元。按照类比，它试图阻止先到者以避免形成人群。与 Primary Clustering 相比，Secondary Clustering 更微妙，并且在性能方面没有那么严重。

Answer 2

当您点击一个空槽时，您将停止搜索表，因为您知道如果您点击一个空槽，那么您要查找的值将不在哈希表中。由于减少了聚类，您将更有可能遇到空槽并停止搜索。此外，由于减少了聚类，您将更有可能在插入时找到一个空槽，从而能够更快地搜索该值。

Answer 3

因为集群形成较少。这些值将更加分散，因此在二次情况下所需的平均探针数量将更少。