hash中什么是主次聚类？

Question

我最近几天在看的教科书中发现散列冲突管理主题中主集群和二级集群之间的区别时感到困惑。

Answer 1

主聚类意味着如果有一个聚类并且新记录的初始位置将落在聚类中的任何位置，则聚类大小会增加。线性探测导致这种类型的聚类。

二次聚类不太严重，两条记录只有在初始位置相同的情况下才会有相同的碰撞链。例如二次探测导致这种类型的聚类。

Answer 2

主要聚类

1. 主要聚类是冲突解决方案（例如线性探测）的趋势，可以创建长时间运行的填充槽 near 键的哈希位置。
2. 如果主哈希索引是 x，后续探测将转到 x+1， x+2、x+3 等等，这导致主聚类。
3. 一旦主星团形成，星团越大， 它增长得更快。而且它会降低性能。

---

二级聚类

1. 二次聚类是一种冲突解决方案（例如二次探测）的趋势，可以创建长时间运行的填充槽 远离键的散列位置。
2. 如果主哈希索引是 x，探测将转到 x+1、x+4、x+9， x+16, x+25 依此类推，这导致二级聚类。
3. 次要集群在性能方面的影响不如主要集群严重，并且是一种 尝试使用二次探测来防止集群形成。 这个想法是探测更广泛分离的细胞，而不是那些 与主要哈希站点相邻。