algorithm - 哈希中的聚类（在冲突中）是什么意思？

Question

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

为什么组中的连续元素以及它如何影响找到空闲槽的时间？

Answer 1

哈希函数的所需输出是将 100 个字符串随机分散到 200 个“鸽子槽”上。如果发生冲突，即已经占用的时隙，线性扫描将搜索下一个未占用的时隙，立即形成至少两个的组（它也可以连接两个组）。当集群发生冲突时，线性探测会通过一个新键添加集群，其原始位置应该在集群中的任何位置。

许多快速评估散列函数都存在密钥分配不均的问题。当输入数据也不是均匀分布时，这两个现象相互强调，在线性探测的情况下可能会导致大量的键进行聚类。实际上，这不仅会进行插入，还会搜索 O(n) 问题而不是 O(1)。

Answer 2

并非总是连续的元素会形成集群。

矛盾的例子

假设您有一个100条目哈希表： 并且哈希函数是：

h(x) = x mod 100;

假设您插入元素：

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

形成的集群将是：

集群1948(position 48),748(position 49)：（显然元素不是连续的）

第 2 组172(position 72),973(position 73),473(position 74),572(position 75),72(position 76)：（显然元素不连续）。

是的，集群会影响找到空闲槽的时间，因为在 中linear probing，我们扫描哈希表以找到下一个空闲槽，所以由于集群，由于形成了集群，线性扫描会花费更多时间，但它只是由于线性扫描 以防碰撞。