哈希表與線性列表

Question

會有一個實例，在線性列表中搜索關鍵字比哈希錶快嗎？

我基本上想知道是否存在一個邊緣情況下，在線性列表中搜索關鍵字將比散列表搜索更快。

謝謝！

Answer 1

是的，在少數元素的情況下。想想哈希如何工作。它必須計算哈希來查找一個桶，然後搜索該桶中的列表。此外，它可能是一個複雜的多層次散列等。因此，您甚至可以在通過線性列表進行搜索時比使用散列查找算法更有效。

另一個實例是，如果您正在查找的元素始終位於列表的開頭或附近。根據你在做什麼可能會發生。

還有其他的，但應該幫助你考慮一下。

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

Answer 2

在散列表中搜索並不總是恆定的。如果散列函數與數據不匹配，則可能發生很多衝突，並且在極端情況下每個數據項具有相同的散列值，結果看起來就像線性搜索。根據具體情況，這種有效的線性搜索可能比對數組中的數據進行線性搜索要慢。 （例如，帶有二次探測序列的open addressing，這使得對處理器緩存的使用較差，可能比對陣列進行線性搜索要慢）。

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