data-structures - 线性探测上的二次探测

Question

对于给定的哈希值，线性探测生成的索引如下:
h , h+1 , h+2 , h+3 ， 等等..

对于给定的哈希值，二次探测生成的索引如下:
h , h+1 , h+4 , h+9 ， 等等..

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

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

Answer 1

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

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

二次探测形式二级聚类 .这是一种防止集群形成的尝试。这个想法是探测更广泛分离的单元格，而不是那些与主哈希站点相邻的单元格。以此类推，它试图阻止先到者以避免形成人群。与主集群相比，次集群在性能方面更加微妙且不那么严重。