algorithm - 关于哈希表中的二级聚类

Question

Although quadratic probing eliminates primary clustering, elements that hash to the same position will probe the same alternate cells. This is known as secondary clustering. Simulation results suggest that it generally causes less than an extra probe per search.

以上是 Mark Allen Wessis 书中的算法书的文本片段。

我的问题有人可以用例子来解释什么是次要聚类以及作者所说的“模拟结果表明它通常导致每次搜索少于一个额外的探测”是什么意思。

谢谢!

Answer 1

二级聚类在您引用的文本中定义:探针将围绕其他点聚类，而不是靠近插入点。

“模拟结果表明它通常导致每次搜索少于一个额外的探测”意味着有人试图通过二次探测在哈希表中插入或查找大量数据，并发现，平均 , 只需不到两个探针就可以在哈希表中找到正确的位置。 (一个探针当然是在哈希表中插入或查找任何内容所需的最低限度。)