一、為什么散列表和鏈表經(jīng)常放在一起使用?

1.散列表的優(yōu)點:支持高效的數(shù)據(jù)插入、刪除和查找操作

2.散列表的缺點:不支持快速順序遍歷散列表中的數(shù)據(jù)

3.如何按照順序快速遍歷散列表的數(shù)據(jù)?只能將數(shù)據(jù)轉(zhuǎn)移到數(shù)組，然后排序，最后再遍歷數(shù)據(jù)。

4.我們知道散列表是動態(tài)的數(shù)據(jù)結(jié)構(gòu)，需要頻繁的插入和刪除數(shù)據(jù)，那么每次順序遍歷之前都需要先排序，這勢必會造成效率非常低下。

5.如何解決上面的問題呢?就是將散列表和鏈表(或跳表)結(jié)合起來使用。

二、散列表和鏈表如何組合起來使用?

LRU緩存淘汰算法

借助散列表，我們可以把LRU緩存淘汰算法的時間復(fù)雜度降低為O(1)。

首先，我們來回顧一下當(dāng)時我們是如何通過鏈表實現(xiàn)LRU緩存淘汰算法的。

我們需要維護一個按照訪問時間從大到小有序排列的鏈表結(jié)構(gòu)。因為緩存大小有限，當(dāng)緩存空間不夠，需要淘汰一個數(shù)據(jù)的時候，我們就直接將鏈表頭部的結(jié)點刪除。

當(dāng)要緩存某個數(shù)據(jù)的時候，先在鏈表中查找這個數(shù)據(jù)。如果沒有找到，則直接將數(shù)據(jù)放到鏈表的尾部;如果找到了，我們就把它移動到鏈表的尾部。因為查找數(shù) 據(jù)需要遍歷鏈表，所以單純用鏈表實現(xiàn)的LRU緩存淘汰算法的時間復(fù)雜很高，是O(n)。

實際上，我總結(jié)一下，一個緩存(cache)系統(tǒng)主要包含下面這幾個操作:

1.往緩存中添加一個數(shù)據(jù);

2.從緩存中刪除一個數(shù)據(jù);

3.在緩存中查找一個數(shù)據(jù)。

這三個操作都要涉及“查找”操作，如果單純地采用鏈表的話，時間復(fù)雜度只能是O(n)。如果我們將散列表和鏈表兩種數(shù)據(jù)結(jié)構(gòu)組合使用，可以將這三個操作的時間 復(fù)雜度都降低到O(1)。

具體的結(jié)構(gòu)就是下面這個樣子:

image.png

我們使用雙向鏈表存儲數(shù)據(jù)，鏈表中的每個結(jié)點處理存儲數(shù)據(jù)(data)、前驅(qū)指針(prev)、后繼指針(next)之外，還新增了一個特殊的字段hnext。這個hnext有 什么作用呢?

因為我們的散列表是通過鏈表法解決散列沖突的，所以每個結(jié)點會在兩條鏈中。一個鏈?zhǔn)莿倓偽覀兲岬降碾p向鏈表，另一個鏈?zhǔn)巧⒘斜碇械睦?。前?qū)和后繼指針是為了將結(jié)點串在雙向鏈表中，hnext指針是為了將結(jié)點串在散列表的拉鏈中。 了解了這個散列表和雙向鏈表的組合存儲結(jié)構(gòu)之后，我們再來看，前面講到的緩存的三個操作，是如何做到時間復(fù)雜度是O(1)的?

首先，我們來看如何查找一個數(shù)據(jù)。我們前面講過，散列表中查找數(shù)據(jù)的時間復(fù)雜度接近O(1)，所以通過散列表，我們可以很快地在緩存中找到一個數(shù)據(jù)。當(dāng)找 到數(shù)據(jù)之后，我們還需要將它移動到雙向鏈表的尾部。

其次，我們來看如何刪除一個數(shù)據(jù)。我們需要找到數(shù)據(jù)所在的結(jié)點，然后將結(jié)點刪除。借助散列表，我們可以在O(1)時間復(fù)雜度里找到要刪除的結(jié)點。因為我們 的鏈表是雙向鏈表，雙向鏈表可以通過前驅(qū)指針O(1)時間復(fù)雜度獲取前驅(qū)結(jié)點，所以在雙向鏈表中，刪除結(jié)點只需要O(1)的時間復(fù)雜度。

最后，我們來看如何添加一個數(shù)據(jù)。添加數(shù)據(jù)到緩存稍微有點麻煩，我們需要先看這個數(shù)據(jù)是否已經(jīng)在緩存中。如果已經(jīng)在其中，需要將其移動到雙向鏈表的尾

部;如果不在其中，還要看緩存有沒有滿。如果滿了，則將雙向鏈表頭部的結(jié)點刪除，然后再將數(shù)據(jù)放到鏈表的尾部;如果沒有滿，就直接將數(shù)據(jù)放到鏈表的尾

部。

這整個過程涉及的查找操作都可以通過散列表來完成。其他的操作，比如刪除頭結(jié)點、鏈表尾部插入數(shù)據(jù)等，都可以在O(1)的時間復(fù)雜度內(nèi)完成。所以，這三個 操作的時間復(fù)雜度都是O(1)。至此，我們就通過散列表和雙向鏈表的組合使用，實現(xiàn)了一個高效的、支持LRU緩存淘汰算法的緩存系統(tǒng)原型。

結(jié)論：

散列表這種數(shù)據(jù)結(jié)構(gòu)雖然支持非常高效的數(shù)據(jù)插入、刪除、查找操作，但是散列表中的數(shù)據(jù)都是通過散列函數(shù)打亂之后無規(guī)律存儲的。也就說，它無法支持按照某種順序快速地遍歷數(shù)據(jù)。如果希望按照順序遍歷散列表中的數(shù)據(jù)，那我們需要將散列表中的數(shù)據(jù)拷貝到數(shù)組中，然后排序，再遍歷。

因為散列表是動態(tài)數(shù)據(jù)結(jié)構(gòu)，不停地有數(shù)據(jù)的插入、刪除，所以每當(dāng)我們希望按順序遍歷散列表中的數(shù)據(jù)的時候，都需要先排序，那效率勢必會很低。為了解決這個問題，我們將散列表和鏈表(或者跳表)結(jié)合在一起使用。

作者：尼桑麻

鏈接：http://www.itdecent.cn/p/27637cb2fd9e

來源：簡書

著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。