algorithm - hash中什么是主次聚类？

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. 次要集群在性能方面不如主要集群严重，并且是一种尝试使用二次探测来防止集群形成。这个想法是探测更广泛分离的细胞，而不是那些毗邻主要哈希站点。