链接在哈希表

Question

当我们有链接哈希表：

我只是想知道，如果保持的列表中每个键，以便将影响搜索，插入和哈希表中删除的运行时间？

Answer 1

是的，当然。通常引用的散列表的O（1）假设完美的散列 - 其中没有两个不相同的条目解析为相同的散列。

在实践中，这将不会是这样。你会一直有（为了一个足够大的数据集）碰撞。无论您是使用链接还是其他碰撞解决方法，碰撞都意味着查找时会有更多工作。

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

Answer 2

可以想像，你选择你的哈希算法和地图的大小，以减轻碰撞，你会在第一时间得到的数字。此时，您应该在任何位置都有一个非常小的列表（理想情况下是一个或两个元素），因此在链中维护排序结构的额外工作肯定不仅仅是迭代该存储桶中的少量项目。

Answer 3

从理论上讲：是的，因为在一般情况下，你只需要步行半链找到，如果一个项目在连锁与否。

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

顺便说一句：在大多数情况下的时隙数大于所述散列值的“密钥空间”小得多。如果您能够承担该空间，则将散列值存储在链节点中将节省重新计算每一跳上的散列值，并且将避免大部分最终比较。这当然是一个空间< - >时间折衷。如：

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. 

*/