为什么在哈希表中使用线性探测，而不是使用链表分离链接？

Question

我最近学习了有关哈希表中处理冲突的不同方法，并发现使用带有链表的分离链接法总是比线性探测法更高效。对于空间效率，我们为线性探测法分配预定义的内存，但后来可能不会使用，而对于分离链接法，我们动态使用内存。

使用带有链表的分离链接法比线性探测法更有效吗？如果是这样，那么为什么我们还要使用线性探测法呢？

- Adilli Adil

Answer 1

我很惊讶你认为链式哈希比线性探测更快——在实践中，线性探测通常比链式哈希快得多。这主要是由于参考局部性，因为线性探测中执行的访问通常比链式哈希中执行的访问更接近于内存。

线性探测还有其他优势。例如，在线性探测哈希表中插入不需要进行任何新的分配（除非您重新对表进行哈希），因此在像网络路由器这样内存稀缺的应用中，一旦建立了表，就可以将元素放入其中，而不必担心malloc失败的风险。

线性探测的一个弱点是，如果散列函数选择不当，一次聚集会导致表的性能显著下降。虽然链式哈希仍然可能受到糟糕的散列函数的影响，但它对具有相邻哈希码的元素不太敏感，从而不会对运行时产生不良影响。理论上，只有当哈希函数是5独立的或者键中具有足够的熵时，线性探测才能给出期望的O(1)查找。有许多解决方法，例如使用Robin Hood哈希技术或跳跃式哈希，这两种技术的最坏情况明显比普通的线性探测好得多。

线性探测的另一个弱点是，在负载因子接近1时，其性能会显著下降。您可以通过定期重新哈希或使用上述描述的Robin Hood哈希技术来解决这个问题。

希望这能有所帮助！

- templatetypedef

---

我经常使用分离链接法，但是以一种方式使用，其中单链表节点仅存储数组中的索引。这基本上是一个32位整数的数组，用于存储桶头。32位整数指向节点，这些节点同样只是32位整数，存储下一个节点。这避免了每个节点的内存分配。从内存使用的角度来看，我倾向于找到这个解决方案，因为它非常可预测。如果我们有一个具有5,000个桶的哈希表，并插入10,000个元素，则内存开销为60,000字节（每个桶4字节，每个元素4字节）... - user4842163

与元素数组相平行的节点“next”索引数组。这也带来了一个好处，即如果复制表格，它会产生最佳的空间局部性，因为复制的表格将保证存储桶中的邻居是连续的。唯一讨厌的事情是每个节点/桶的4个字节开销，但当我们不必担心聚类时，我认为这是一个值得的权衡。无论如何，我想参与其中，只是因为一个列表节点不必总是导致内存碎片或每个节点的堆分配。 - user4842163

你如何高效地处理删除操作？看起来你会在元素表中留下很多未使用的插槽，并且需要一些开销来查找下一个空闲位置。 - templatetypedef

在低级C代码的情况下，例如固定分配器类似的情况，数组中的每个元素都充当其本身元素和数组中下一个未使用空间的自由索引的联合体，这种情况变得有些丑陋。哈希表存储了它自己的“free_head”索引，模拟了一个不需要存储堆栈的堆栈（内存双倍重叠，既可以作为下一个空闲元素的索引，也可以作为元素数据）。这样留下的空缺位置可以在随后的插入中重新获取。 - user4842163

在我的情况下，大多数用例通常不需要处理删除情况。就像创建一个哈希表，进行大量搜索，然后丢弃。 - user4842163

Answer 2

当哈希表接近满时，线性探测实际上更具有内存效率。

历史上，人们拥有非常非常少的内存，所以每个字节都很重要（现在仍有一些内存非常有限的情况）。

为什么它使用的内存更少？

考虑表的外观：（根据 维基百科 的分离链接变体 - 还有其他变体，但它们通常使用更多的内存）

Linear             Separate chaining #1    Separate chaining #2
probing            List head in table      Pointer in table
|------|           |------|---|            |---|    |------|---|
|Object|           |Object|Ptr|            |Ptr| -> |Object|Ptr|
|------|           |------|---|            |---|    |------|---|
|Object|           |Object|Ptr|            |Ptr| -> |Object|Ptr|
|------|           |------|---|            |---|    |------|---|
| NULL |           | NULL |Ptr|            |Ptr|
|------|           |------|---|            |---|
 .                  .                       .
 .                  .                       .
 .                  .                       .

(Ptr 代表 "指针" - 任何未指向任何东西的指针都可以被视为 NULL)

与线性探测相比，分离链接 #1 明显使用更多内存（始终如此），因为表中的每个元素都比指针的大小大。

当表中没有太多内容时，分离链接 #2 可能具有优势，但当其被填满时，它将在每个元素周围大约有另外2个指针。

---

templatetypedef 关于线性探测通常更快（他很少错）可能是正确的，但通常教授分离链接更快，并且您可以在主要 API 中看到它（例如像Java 实现），也许是因为这种信仰，以避免线性探测明显较慢的情况（通过选定一些值，您可以快速地达到 O(n) 性能，而分离链接仍将是 O(1)），或者出于其他原因。

- Bernhard Barker