基于线性探测的二次探测

Question

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

h、h+1、h+2、h+3等。

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

h、h+1、h+4、h+9等。

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

但是，当两个过程(方法)都需要采取相同数量的插入或搜索步骤时，二次算法比线性算法效率更高。谢谢!

Answer 1

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

Answer 2

效率取决于线性探测和二次探测形成的kinds of clustering。

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

其中，as二次探测形成辅助群集。这是防止集群形成的一种尝试。这个想法是探测更广泛分离的单元，而不是那些与主散列站点相邻的单元。按照这个类比，它试图阻止第一个到达的人，以避免形成人群。与主群集相比，辅助群集更加微妙，并且在性能方面没有那么严重。

Answer 3

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