哈希中的主要和辅助群集是什么？

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

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

二级聚类不太严重,如果两个记录的初始位置相同,则只有相同的碰撞链.例如,二次探测导致这种类型的聚类.