algorithm - 什么是哈希中的一级和二级聚类？

Question

在过去的几天里，我很困惑在我正在阅读的教科书中找到哈希冲突管理主题中主集群和次集群之间的区别。

Answer 1

主聚类

1. 主聚类是一种冲突解决方案的趋势，例如线性探测，以 在键的哈希位置附近创建长时间运行的填充槽。
2. 如果主哈希索引为x，则后续探测将转到x+1、 x+2等x+3，这将导致主聚类。
3. 一旦主集群形成，集群越大，增长越快。它会降低性能。

---

二次聚类

1. 二次聚类是一种冲突解决方案的趋势，例如二次探测，以创建 远离键的哈希位置的填充槽的长运行。
2. 如果主哈希索引是x，则探测到x+1、x+4、x+9等 x+16, x+25，这会导致二级聚类。
3. 二级聚类在性能损失方面不如一级聚类严重，并且是通过使用二次探测来防止聚类形成的一种尝试。这个想法是探测更广泛分离的单元，而不是那些与主哈希站点相邻的单元。

Answer 2

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

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