散列中的聚集（在碰撞中）是什么意思？

Question

线性探测的主要问题是聚类，许多连续的元素形成组，它开始花时间找到空闲槽或搜索元素。

为什么来自组&的连续元素为什么会影响找到空闲插槽的时间？

Answer 1

散列函数需要的输出是将100个字符串散布为随机地说200个“鸽子”。在发生碰撞的情况下，即已经占用的插槽，线性扫描将搜索下一个未占用的插槽，立即产生一组至少两个（它也可能连接两组）。当与群集发生冲突时，线性探测会将群集添加一个新密钥，其原始位置应该位于群集中的任何位置。

很多快速评估哈希函数都会遇到不均匀分配密钥的问题。当输入数据不均匀分布时，这两个现象相互强调，在线性探测的情况下可能会导致大量的密钥集群。实际上，这不仅会导致插入，而且还会搜索O（n）问题而不是O（1）。

Answer 2

它不是总是连续的元素将形成集群的情况。

Condictory例如

假设有100条目的哈希表：和所述散列函数是：

h(x) = x mod 100; 

说您插入元件：形成

948,748,172,973,473,572,72 

簇将是：

簇1：948(position 48),748(position 49)（清楚元素不连续）

簇2：172(position 72),973(position 73),473(position 74),572(position 75),72(position 76)（清楚元素不连续）。

YES，集群影响的时间找到一个免费的插槽，因为在linear probing，我们扫描哈希表找到第二天空闲时隙，所以由于集群，线性扫描将需要更多的时间，由于集群形成，但其唯一的原因是线性扫描在碰撞的情况下。