线性探测的二次探测

Question

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

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

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

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

在线性的情况下将形成簇,但在二次的情况下不会形成簇.

但是,当两个进程(方法)需要采用相同数量的步骤进行插入或搜索时,二次方法如何比线性方法更有效.谢谢!

Answer 1

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

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

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

Answer 2

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