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

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，我們掃描哈希表找到第二天空閒時隙，所以由於集羣，線性掃描將需要更多的時間，由於集羣形成，但其唯一的原因是線性掃描在碰撞的情況下。