一、散列表為什么可以在O(1)時間復雜度內查找散列值

因為哈希函數的功能就是完成鍵到哈希值的映射，映射到的哈希值就是一個數字，被用來當作數組的下標，這個元素就是存儲在數組的這個下標內。散列表用的其實是數組隨機存取的特性。數組隨機存取的復雜度就是O(1)，所以散列表的查找效率就是O(1)。

什么是散列表

散列表（hash table），我們平時叫它哈希表或者Hash 表，你肯定經常聽到它。

散列表是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。

由定義我們可以知道，散列表用的是數組支持下標訪問數據的特性，所以散列表是數組的一種擴展，有數組演化而來。

延伸閱讀：

二、開放尋址法

開發尋址法就是但我們遇到了哈希沖突，我們就重新探索一個空閑位置，然后插入。

我們探索空閑位置有以下幾種方法。

當我們往散列表中插入數據時，經過散列函數發現位置已經被占用了，我們就從當前位置開始，依次往后查找，直到找到空閑位置為止。

比如一個散列表的大小為 10，一個數據經過散列函數之后，到了下標為 8 的位置，但是發現這個位置已經有數據了，那么就依次往后遍歷，如果到了尾部，還是沒有找到空閑位置，那么就再從頭開始找，直到找到空閑位置。

查找元素和插入類似，通過散列函數計算出哈希值，然后找到對應位置數據，然后與查找的元素進行比較，如果相等，則它就是我們要找的數據，如果不相等，就依次往后遍歷，如果遍歷到空閑位置還沒找到，就說明元素不在散列表中。

但是刪除的時候稍微有點特別，我們不能直接刪除數據，因為我們在查找的時候，如果找到一個空閑位置，就說元素不在散列表中，如果我們直接刪除了之后可能會導致某些元素找不到。所以我們將要刪除的元素，標記為 deleted，當我們查找的時候，遇到標記為 deleted 的元素，繼續往下遍歷。

線性探測法存在很大的問題，當散列表中插入的元素越來越多時，發生散列沖突的概率就越來越大，空閑的位置就越來越少，先行探索的時間就會越來越長，甚至在極端情況下，我們需要遍歷整個散列表。

二次探索，和線性探索原理一樣，先行探索每次的步長為 1 ，探索的下標依次為 hash(key)+0，hash(key)+1，hash(key)+2…，二次探索每次的步長變為原來的二次方，所以每次探索的下邊為 hash(key)+0，hash(key)+1^2，hash(key)+2^2。

原來我們使用一個散列函數，雙重散列，我們使用多個散列函數，我們先用名列前茅個散列函數，如果計算得到的位置已經被占用，就使用第二個散列函數，以此類推，直到找到空閑時的位置。

不管用哪個探索方法，當空閑位置變少的時候，散列沖突的概率會變得很高。為了盡可能保證散列表的操作效率，一般情況下，我們會盡可能保證散列表中有一定比例的空閑槽位。我們用裝載因子來表示空位的多少。 裝載因子 = 填入散列表的元素個數 / 散列表的長度