logo标签列表

哈希表 vs 线性列表

listhashtablelookup
3

在线性列表中搜索关键字比哈希表搜索更快的情况是否存在？

我想知道是否有边缘情况，其中在线性列表中搜索关键字将比哈希表搜索更快。

谢谢！

2个回答
2
在现实中，哈希表的搜索并不总是恒定时间。如果哈希函数与数据不匹配，可能会有很多冲突。在极端情况下，每个数据项都具有相同的哈希值，结果看起来非常像线性搜索。根据细节，这种有效的线性搜索可能比在数组中对数据进行线性搜索更慢。（例如，使用二次探测序列的开放地址法，它对处理器缓存的利用很差，可能比在数组中进行线性搜索更慢。）
以下是一个所有键最终都落在同一桶中的实际案例：Java bug 4669519。
0

是的，在元素数量非常少的情况下会出现这种情况。想想哈希表是如何工作的。它必须计算哈希值以找到桶，然后在该桶中搜索列表。此外，它可能是一个复杂的多级哈希等等。因此，当通过线性列表搜索比哈希查找算法更费力时，你就可以打破平衡点。

另一个例子是，如果你要查找的元素始终位于列表的开头或接近开头。根据你所做的事情，这可能会发生。

还有其他情况，但这应该能帮助你思考。

不过，不要混淆。通常情况下，哈希表是你想要的。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接