哈希如何有一個o（1）的搜索時間？

Question

當我們使用HashTable來存儲數據時，據說搜索需要o（1）次。我很困惑，有人可以解釋嗎？

Answer 1

嗯，這是一個小位謊言 - 它可能需要更長的時間，但它通常不會。

基本上，哈希表是一個包含所有要搜索的鍵的數組。數組中每個鍵的位置由散列函數決定，它可以是任何總是將相同輸入映射到相同輸出的函數。我們假設哈希函數是O（1）。

所以當我們在散列表中插入一些東西時，我們使用散列函數（我們稱之爲h）來找到放置它的位置，並放在那裏。現在插入另一個東西，哈希和存儲。另一個。每次插入數據時，都需要O（1）次插入（因爲散列函數是O（1）

查找數據是一樣的如果我們想要查找一個值，x，我們只有找出^h（x）的，它告訴我們哪裏X位於哈希表。因此，我們可以看一下在O（1），以及任何哈希值。

我們的謊言：上面是一個非常好的理論，有一個問題：如果我們插入數據，並且數組中已經存在某些東西？沒有什麼能保證散列函數不會爲兩個不同的輸入產生相同的輸出（除非你有一個perfect hash function，但這些都很難製作）。因此，當我們插入時，我們需要採取以下兩種策略之一：

• 在數組中的每個點上存儲多個值（比如說，每個數組插槽都有一個鏈接列表）。現在，當你進行查找時，它仍然是O（1）到達數組中的正確位置，但可能是一個線性搜索（希望是短的）鏈表。這被稱爲「分離鏈接」。
• 如果您發現某些東西已經存在，請再次散列並找到其他位置。重複，直到你找到一個空的地方，並把它放在那裏。查找過程可以遵循相同的規則來查找數據。現在它仍然是O（1）到達第一個位置，但是有一個可能的（希望是短的）線性搜索在桌子上反彈，直到你找到你之後的數據。這被稱爲「開放尋址」。

基本上，兩種方法都仍然大多 O（1）但具有希望-短的線性序列。我們可以爲大多數目的假設它是O（1）。如果散列表變得太滿，那些線性搜索可能變得越來越長，然後是「重新散列」的時候，這意味着要創建一個更大尺寸的新散列表並將所有數據重新插入到它中。

Answer 2

如果散列表中沒有collisons，搜索需要O（1）時間，所以對於sya來說，在散列表中搜索需要O（1）或常量時間，這是不正確的。

See how Hashtable works on MSDN?

編輯

mgiuca精美解釋它，我只是多加一個Collosion避免技術被稱爲鏈接。

在這項技術中，我們維護每個位置的值鏈接列表，因此當您發生爆炸時，您的值將被添加到該位置的鏈接列表中，因此當您搜索某個值時可能會出現需要的場景在整個鏈接列表中搜索值，因此在這種情況下搜索不會是O（1）操作。