數(shù)據(jù)結(jié)構(gòu)與算法——散列表

VincentFF 發(fā)布于2019-08-16 16:10 / 2358人閱讀

摘要：散列表其實(shí)是基于數(shù)組實(shí)現(xiàn)的，可以說，沒有數(shù)組就沒有散列表。根據(jù)下圖你更能理解散列表哈希函數(shù)結(jié)合上面的理解，你應(yīng)該可以想到，其實(shí)散列表的關(guān)鍵就在于哈希函數(shù)的實(shí)現(xiàn)。

1. 什么是散列表？

散列表（Hash Table）又叫做哈希表，是一種很常用的數(shù)據(jù)結(jié)構(gòu)。散列表其實(shí)是基于數(shù)組實(shí)現(xiàn)的，可以說，沒有數(shù)組就沒有散列表。先來舉一個(gè)簡單的例子，來認(rèn)識(shí)一下什么是散列表。

假如在學(xué)校的運(yùn)動(dòng)會(huì)上，每個(gè)運(yùn)動(dòng)員的胸前都會(huì)標(biāo)識(shí)自己的號(hào)碼，編號(hào)是1，2，3……，這樣的話，我們可以很容易的將運(yùn)動(dòng)員信息存儲(chǔ)在數(shù)組當(dāng)中，運(yùn)動(dòng)員的編號(hào)就是數(shù)組的下標(biāo)。但是會(huì)存在這樣一種情況，假如運(yùn)動(dòng)員的編號(hào)不是順序排列的，而是需要加上更多的信息，比如年級，班級，例如一個(gè)運(yùn)動(dòng)員的編號(hào)是15030711，15是年級，03是專業(yè)，07是班級，11是順序號(hào)，這樣的話我們該怎么存儲(chǔ)運(yùn)動(dòng)員信息呢？

其實(shí)也不難，我們只需要截取運(yùn)動(dòng)員編號(hào)的最后兩位，作為數(shù)組的下標(biāo)存儲(chǔ)在數(shù)組中，當(dāng)需要根據(jù)編號(hào)查詢信息的時(shí)候，我們也同樣截取編號(hào)最后兩位來進(jìn)行查詢。這就是很典型的散列思想。

選手的編號(hào)叫做鍵，把運(yùn)動(dòng)員編號(hào)轉(zhuǎn)換為數(shù)組下標(biāo)的方法叫做散列函數(shù)（或哈希函數(shù)），通過散列函數(shù)計(jì)算得到的值叫做散列值（或哈希值）。

根據(jù)下圖你更能理解散列表：

2. 哈希函數(shù)

結(jié)合上面的理解，你應(yīng)該可以想到，其實(shí)散列表的關(guān)鍵就在于哈希函數(shù)的實(shí)現(xiàn)。哈希函數(shù)，顧名思義，其實(shí)就是一個(gè)函數(shù)，key 就是鍵值，經(jīng)過 hash(key) 得到的值就是哈希值。

哈希函數(shù)的設(shè)計(jì)有三個(gè)原則：

通過哈希函數(shù)計(jì)算得到的哈希值是一個(gè)非負(fù)的整數(shù)。

如果 key1 = key2，那么 hash(key1) = hash(key2)。

如果 key1 != key2，那么 hash(key1) != hash(key2)。

前面兩點(diǎn)其實(shí)很好理解，第一點(diǎn)，要求是一個(gè)非負(fù)的整數(shù)，這是因?yàn)閿?shù)組的下標(biāo)是從 0 開始的，第二點(diǎn)，如果 key 相同，那么通過哈希函數(shù)得到的哈希值也相同。

第三點(diǎn)稍微有點(diǎn)不好理解，key1 不等于 key2，那么哈希值也是不相等的，這只是一種理想的狀況，但是在實(shí)際情況中，無法避免這種哈希沖突。

3. 哈希沖突

哈希沖突，又叫哈希碰撞，是哈希函數(shù)可能會(huì)遇到的問題，即不同的 key 值經(jīng)過哈希函數(shù)計(jì)算之后，可能得到相同的哈希值，那么這種狀況該怎么解決呢？一般是通過兩種方式：

開放尋址法

鏈表法

開放尋址法可以通過線性探測這種方式來實(shí)現(xiàn)，比如我們的一個(gè) key 經(jīng)過哈希函數(shù)得到哈希值之后，相應(yīng)的存儲(chǔ)位置已經(jīng)被占用，那么我們遍歷散列表，找到一個(gè)空閑的位置，將數(shù)據(jù)插入。

例如下圖，標(biāo)記為黃色的是已經(jīng)有數(shù)據(jù)，標(biāo)記為紅色的是空閑空間，一個(gè) key 經(jīng)過 hash 哈希函數(shù)之后的存儲(chǔ)位置為 2，但是下標(biāo)為 2 的的地方已經(jīng)有數(shù)據(jù)了，所以就重新探測一個(gè)空的位置。

第二種方式是鏈表法，這種方式會(huì)更加簡單，也更加適用。例如下圖，在每一存儲(chǔ)位置，都會(huì)有相應(yīng)的鏈表，如果哈希值相同，我們直接將數(shù)據(jù)存放在存儲(chǔ)位置對應(yīng)的鏈表中。

但是這種方式也可能會(huì)存在問題，比如說哈希函數(shù)設(shè)計(jì)的不合理，導(dǎo)致大量的數(shù)據(jù)都集中在一條鏈表中，這樣的話，數(shù)據(jù)的插入和查找速度就會(huì)急劇退化為O(n)。針對這種情況，我們可以使用更加優(yōu)秀的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)代替鏈表，例如紅黑樹、跳表等。這樣，就算數(shù)據(jù)全都集中在一個(gè)節(jié)點(diǎn)上，數(shù)據(jù)的查詢效率也不會(huì)下降得太厲害。

4. 散列表的具體應(yīng)用

其實(shí)，散列表和鏈表在很多時(shí)候都是結(jié)合在一起使用的，接下來就看看散列表的兩個(gè)具體應(yīng)用：LRU（最近最少使用策略，Least Recently Used）緩存淘汰算法和 Java 的 LinkedHashMap。

1.LRU 緩存淘汰算法

首先，該怎么理解 LRU，即最近最少使用策略呢？舉個(gè)簡單的例子，比如你買了很多書，書架上漸漸放滿了，當(dāng)你有新的書的時(shí)候，需要將原來的書拿掉一些，騰出新的位置來。這樣的話，你肯定會(huì)拿掉那些最近很少使用到的那些書，這就是一種最近最少使用策略。

其實(shí)可以用單鏈表實(shí)現(xiàn)一個(gè)LRU緩存淘汰算法，具體可以這樣做：我們維護(hù)一個(gè)有限的緩存空間，如果空間不夠，需要淘汰緩存的話，我們直接將鏈表頭部的數(shù)據(jù)刪除即可。當(dāng)要緩存某個(gè)數(shù)據(jù)的時(shí)候，我們需要查找這個(gè)數(shù)據(jù)，如果找到了，將其放置在鏈表尾部，如果沒找到，則將數(shù)據(jù)插入到鏈表尾部。因?yàn)樯婕暗降牟檎也僮餍枰闅v鏈表，時(shí)間復(fù)雜度是O(n)，所以我們可以用散列表加上雙向鏈表來實(shí)現(xiàn)，將時(shí)間復(fù)雜度降為O(1)。具體該怎么實(shí)現(xiàn)呢？

先來看看下面實(shí)現(xiàn)的圖：

首先，如果空間不夠，我們直接將雙向鏈表頭部的元素刪除；查找一個(gè)元素，我們可以在接近 O(1) 的時(shí)間復(fù)雜度找到該元素，并且將其插入到鏈表的尾部；刪除一個(gè)元素，由于雙向鏈表保存了上一個(gè)鏈表的指針，所以能夠在O(1) 的時(shí)間內(nèi)刪除；添加一個(gè)元素，如果此元素已經(jīng)在鏈表中，則直接將該元素插入到鏈表尾部，如果不在鏈表中，直接將元素插入到鏈表尾部，如果緩存滿了，則刪除鏈表頭部元素之后才添加。

2.LinkedHashMap

如果熟悉 Java 的話，肯定會(huì)經(jīng)常用到 LinkedHashMap 這個(gè)容器，它與 HashMap 唯一的區(qū)別就是，LinkedHashMap 能夠按照插入次序依次遍歷得到數(shù)據(jù)，這個(gè)功能是怎么實(shí)現(xiàn)的呢？其實(shí)和上面的結(jié)構(gòu)圖很類似，插入到 HashMap 中的數(shù)據(jù)用雙向鏈表連接起來，然后按照遍歷鏈表的方法依次得到數(shù)據(jù)，這樣就能夠?qū)崿F(xiàn)有序輸出數(shù)據(jù)了。

好了，散列表就基本上講完了。