链式哈希表与开放地址哈希表

Question

有人能解释一下这两种实现之间的主要区别(优缺点)吗？

对于一个库，推荐的实现是什么？

Answer 1

对于人们使用过的不同哈希表方案，Wikipedia's article on hash tables给出了明显更好的解释和概述，这是我想不到的。事实上，你最好阅读这篇文章，而不是在这里问问题。:)

也就是说..。

链式哈希表索引到指向链表头部的指针数组中。每个链接列表单元格都有为其分配的键以及为该键插入的值。当您想要从某个特定元素的键中查找它时，使用键的散列来确定要跟随哪个链表，然后遍历该特定列表以找到您要查找的元素。如果哈希表中有多个键具有相同的散列，那么您将拥有具有多个元素的链表。

链式散列的缺点是必须跟随指针才能搜索链表。优点是，链式哈希表只会随着负载因子(哈希表中的元素与存储桶数组长度之比)的增加而线性变慢，即使它上升到1以上。

开放寻址哈希表索引到指向(键、值)对的指针数组中。您可以使用键的散列值来确定首先查看数组中的哪个槽。如果哈希表中有多个键具有相同的散列，那么您可以使用某种方案来决定要查找的另一个槽。例如，线性探测是您查看所选插槽之后的下一个插槽，然后是下一个插槽，依此类推，直到您找到一个与您正在查找的键匹配的插槽，或者您遇到了一个空插槽(在这种情况下，键肯定不在那里)。

当负载因子较低时，开放寻址通常比链式散列更快，因为您不必遵循列表节点之间的指针。如果负载因子接近1，它会变得非常、非常慢，因为在找到您要查找的键或空槽之前，您通常必须在存储桶数组中的许多槽中进行搜索。此外，哈希表中的元素永远不能多于存储桶数组中的条目。

为了处理所有哈希表在其负载因子接近1时至少变慢(在某些情况下实际上完全崩溃)的事实，实际的哈希表实现在负载因子超过某个值(通常约为0.7)时使桶数组变得更大(通过分配新桶数组，并将元素从旧桶数组复制到新桶数组中，然后释放旧桶数组)。

上面的内容有很多不同之处。再一次，请看维基百科的文章，它真的很好。

对于一个供其他人使用的库，我强烈建议进行实验。因为它们通常对性能非常关键，所以您通常最好使用其他人的哈希表实现，而这个实现已经经过了仔细的调优。有很多开源的BSD，LGPL和GPL授权的哈希表实现。

例如，如果您正在使用GTK，那么您会发现有一个很好的hash table in GLib。

Answer 2

我的理解(简而言之)是，这两种方法都有优缺点，尽管大多数库都使用链接策略。

链接方式：

在这里，哈希表数组映射到一个链接的项目列表。如果碰撞的数量相当少，则这是有效的。最坏的情况是O(n)，其中n是表中元素的数量。

使用线性探针的开放寻址：

在这里，当碰撞发生时，移动到下一个索引，直到我们找到一个空白点。因此，如果碰撞的数量很少，这是非常快和空间有效的。这里的限制是表中条目的总数受数组大小的限制。这不是链式的情况。

还有另一种方法，那就是用二叉搜索树链接。在这种方法中，当冲突发生时，它们被存储在二叉树中，而不是链表中。因此，这里最坏的情况是O(log n)。在实践中，当存在非常不均匀的分布时，这种方法最适合。

Answer 3

由于已经给出了很好的解释，为了进一步说明，我将添加从CLRS中获取的可视化内容：

开放寻址：

​

链接：

​