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

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

什么是散列表

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

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

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

延伸閱讀：

二、開放尋址法

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

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

當我們往散列表中插入數(shù)據(jù)時，經(jīng)過散列函數(shù)發(fā)現(xiàn)位置已經(jīng)被占用了，我們就從當前位置開始，依次往后查找，直到找到空閑位置為止。

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

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

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

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

二次探索，和線性探索原理一樣，先行探索每次的步長為 1 ，探索的下標依次為 hash(key)+0，hash(key)+1，hash(key)+2…，二次探索每次的步長變?yōu)樵瓉淼亩畏剑悦看翁剿鞯南逻厼?hash(key)+0，hash(key)+1^2，hash(key)+2^2。

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

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