有人可以解释一下这两种实现方式之间的主要区别(优势/劣势)吗？
对于库，建议采用哪种实现方式？
最佳答案
Wikipedia's article on hash tables对人们使用的不同哈希表方案给出了明显更好的解释和概述，这比我能想到的要好得多。事实上，阅读那篇文章可能比在这里提问更好。 :)
也就是说……
链式哈希表索引到指向链表头部的指针数组。每个链表单元都有为其分配的键和为该键插入的值。当您想从其键中查找特定元素时，该键的散列用于计算要遵循的链表，然后遍历该特定列表以找到您要查找的元素。如果哈希表中的多个键具有相同的哈希值，那么您将拥有包含多个元素的链表。
链式哈希的缺点是必须遵循指针才能搜索链表。好处是，链式哈希表只会随着负载因子(哈希表中元素与桶数组长度的比率)的增加而线性变慢，即使它超过 1。
一个开放寻址哈希表索引到指向(键，值)对的指针数组中。您使用键的散列值来计算出首先查看数组中的哪个槽。如果哈希表中的多个键具有相同的哈希值，那么您可以使用某种方案来决定在另一个插槽中查找。例如，线性探测是您查看所选插槽后的下一个插槽，然后再查看下一个插槽，依此类推，直到找到与您要查找的键匹配的插槽，或者找到一个空插槽插槽(在这种情况下， key 不得存在)。
当负载因子较低时，开放寻址通常比链式哈希更快，因为您不必在列表节点之间跟踪指针。如果负载因子接近 1，它会变得非常非常慢，因为在找到您要查找的键或空槽之前，您通常不得不搜索存储桶数组中的许多槽。此外，哈希表中的元素永远不能多于桶数组中的条目。
当所有哈希表的负载因子接近 1 时，为了解决所有哈希表至少变得更慢(在某些情况下实际上完全崩溃)的事实，实际的哈希表实现使桶数组更大(通过分配一个新的桶数组，并且将元素从旧元素复制到新元素，然后释放旧元素)当负载因子超过某个值(通常约为 0.7)时。
以上所有内容都有很多变体。再说一次，请看维基百科的文章，真的很不错。
对于打算供其他人使用的库，我强烈建议进行试验。由于它们通常对性能非常关键，因此您通常最好使用其他人已经仔细调整过的哈希表的实现。有许多开源 BSD、LGPL 和 GPL 许可的哈希表实现。
例如，如果您正在使用 GTK，那么您会发现有一个很好的 hash table in GLib .
关于data-structures - 链式哈希表与开放寻址哈希表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2556142/