performance - 哈希表中的链接

Question

当我们有一个带有链接的哈希表时：

我只是想知道按顺序维护每个键的列表是否会影响在哈希表中搜索、插入和删除的运行时间？

Answer 1

理论上：是的，因为在一般情况下，您只需要走一半的链条就可以找到一个物品是否在链条上。

在实践中，可能没有太大区别，因为链通常很短，并且增加的代码复杂性也会花费一些周期，主要是在“插入”情况下。

顺便说一句：在大多数情况下，槽的数量远小于散列值的“键空间”。如果你能负担得起空间，将哈希值存储在链节点中将节省在每一跳上重新计算哈希值，并将避免大部分最终比较。这当然是空间<-->时间的权衡。如：

struct hashnode **this;
for (this=& table[slot] ; *this; this = &(*this)->link) {
    if ((*this)->hash != the_hash) continue;
    if (compare ((*this)->payload , the_value)) continue;
    break;
 }
 /* at this point "this" points to the pointer that points to the wanted element,
    or to the NULL-pointer where it should be inserted.

    For the sorted-list example, you should instead break out of the loop
    if the compare function returns > 0, and handle that special case here.

 */

Answer 2

假设您已经选择了哈希算法和映射大小，以减少您将首先遇到的冲突数量。此时，您应该在任何位置都有一个非常小的列表（理想情况下是一两个元素），因此在链中维护排序结构的额外工作肯定不仅仅是迭代该存储桶中的少量项目。

Answer 3

是的当然。哈希表通常引用的 O(1) 假设是完美的哈希 - 没有两个不相同的项目解析为相同的哈希。

在实践中，情况并非如此。您将始终（对于足够大的数据集）发生冲突。无论您使用的是链接还是其他一些冲突解决技术，冲突都意味着在查找时需要做更多的工作。

这就是为什么选择一个设计/编写良好的哈希函数非常非常重要，并且与您将用作哈希表键的数据匹配良好。在实践中，不同类型的数据将使用不同的散列函数更好地散列。