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

因?yàn)楣：瘮?shù)的功能就是完成鍵到哈希值的映射，映射到的哈希值就是一個(gè)數(shù)字，被用來(lái)當(dāng)作數(shù)組的下標(biāo)，這個(gè)元素就是存儲(chǔ)在數(shù)組的這個(gè)下標(biāo)內(nèi)。散列表用的其實(shí)是數(shù)組隨機(jī)存取的特性。數(shù)組隨機(jī)存取的復(fù)雜度就是O(1)，所以散列表的查找效率就是O(1)。

什么是散列表

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

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

由定義我們可以知道，散列表用的是數(shù)組支持下標(biāo)訪問(wèn)數(shù)據(jù)的特性，所以散列表是數(shù)組的一種擴(kuò)展，有數(shù)組演化而來(lái)。

延伸閱讀：

二、開(kāi)放尋址法

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

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

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

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

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

但是刪除的時(shí)候稍微有點(diǎn)特別，我們不能直接刪除數(shù)據(jù)，因?yàn)槲覀冊(cè)诓檎业臅r(shí)候，如果找到一個(gè)空閑位置，就說(shuō)元素不在散列表中，如果我們直接刪除了之后可能會(huì)導(dǎo)致某些元素找不到。所以我們將要?jiǎng)h除的元素，標(biāo)記為 deleted，當(dāng)我們查找的時(shí)候，遇到標(biāo)記為 deleted 的元素，繼續(xù)往下遍歷。

線(xiàn)性探測(cè)法存在很大的問(wèn)題，當(dāng)散列表中插入的元素越來(lái)越多時(shí)，發(fā)生散列沖突的概率就越來(lái)越大，空閑的位置就越來(lái)越少，先行探索的時(shí)間就會(huì)越來(lái)越長(zhǎng)，甚至在極端情況下，我們需要遍歷整個(gè)散列表。

二次探索，和線(xiàn)性探索原理一樣，先行探索每次的步長(zhǎng)為 1 ，探索的下標(biāo)依次為 hash(key)+0，hash(key)+1，hash(key)+2…，二次探索每次的步長(zhǎng)變?yōu)樵瓉?lái)的二次方，所以每次探索的下邊為 hash(key)+0，hash(key)+1^2，hash(key)+2^2。

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

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