哈希表与线性列表

Question

会有一个实例，在线性列表中搜索关键字比哈希表快吗？

我基本上想知道是否存在一个边缘情况下，在线性列表中搜索关键字将比散列表搜索更快。

谢谢！

Answer 1

是的，在少数元素的情况下。想想哈希如何工作。它必须计算哈希来查找一个桶，然后搜索该桶中的列表。此外，它可能是一个复杂的多层次散列等。因此，您甚至可以在通过线性列表进行搜索时比使用散列查找算法更有效。

另一个实例是，如果您正在查找的元素始终位于列表的开头或附近。根据你在做什么可能会发生。

还有其他的，但应该帮助你考虑一下。

不过，不要混淆。散列通常是你想要的。

Answer 2

在散列表中搜索并不总是恒定的。如果散列函数与数据不匹配，则可能发生很多冲突，并且在极端情况下每个数据项具有相同的散列值，结果看起来就像线性搜索。根据具体情况，这种有效的线性搜索可能比对数组中的数据进行线性搜索要慢。 （例如，带有二次探测序列的open addressing，这使得对处理器缓存的使用较差，可能比对阵列进行线性搜索要慢）。

下面是一个真实案例的示例，其中所有密钥都以同一个桶：Java bug 4669519。