文章出處：極客時間《數(shù)據(jù)結(jié)構(gòu)和算法之美》-作者：王爭。該系列文章是本人的學(xué)習(xí)筆記。

7 散列表+鏈表的應(yīng)用

很多情況下散列表會和鏈表一起使用。散列表可以通過key查找value。鏈表可以按照value進行排序。這樣就能通過value查找key，也可以通過查找value的區(qū)間范圍查找key。

7.1 LRU 緩存淘汰算法

基本的LRU
　單純的LRU是維護了一個訪問時間從大到小的有序鏈表。因為緩存大小有限，當(dāng)超過緩存的時候，需要刪除表頭。
　當(dāng)要緩存一個數(shù)據(jù)的時候，先查找數(shù)據(jù)在鏈表中是否存在。如果存在，則刪除，插入到表尾。如果不存在，則看空間是否充足?？臻g充足，直接插入到表尾；如果空間不足，則刪除表頭，插入到表尾。
LRU支持的操作有：
　1 插入數(shù)據(jù)
　2 刪除數(shù)據(jù)
　3 查找數(shù)據(jù)
　這三個操作都涉及查找操作。鏈表的查找操作時間復(fù)雜度是O(n)。散列表+鏈表就可以將查找操作變?yōu)镺(1)。
　
　一個雙向鏈表+散列表。每個節(jié)點=數(shù)據(jù)+前驅(qū)指針+后繼指針+hnext指針。hnext是為了把節(jié)點串在散列表中。前驅(qū)指針、后繼指針是為了形成一個雙向列表。
　查找數(shù)據(jù)的過程。我們通過散列表查找數(shù)據(jù)，時間復(fù)雜度O(1)。找到之后把它移動到雙向鏈表的尾部。
　刪除數(shù)據(jù)的過程。我們通過散列表查找數(shù)據(jù)節(jié)點，利用前驅(qū)后繼指針刪除這個節(jié)點。
　插入數(shù)據(jù)的過程。需要先查找這個節(jié)點是不是存在。存在，移動到雙向鏈表的尾部。不存在需要插入到散列表對應(yīng)的槽位，和雙向鏈表的尾部。如果超出緩存空間，則把雙向鏈表頭部元素刪除。
　所有查詢的操作通過散列表完成。這三個操作都可以在O(1)時間內(nèi)完成。

7.2 Redis有序集合

有序集合中每個對象有兩個重要屬性key和value。
有序集合需要支持的操作有：
1 添加一個成員對象。
2 按照key刪除成員對象。
3 按照key查找成員對象。
4 按照value區(qū)間查找對象。
5 按照value從大到小排序?qū)ο蟆?br /> 　在跳表，我們可以實現(xiàn)按照value排序數(shù)據(jù)。散列表可以按照key組織數(shù)據(jù)。即可以在O(1)實現(xiàn)上述5種操作。
　Redist還可以按照排名查找對象。這個功能在以后講。

7.3 Java LinkedHashMap

Java的LinkedHashMap實際是一個LRU緩存的實現(xiàn)版本。是一個散列表+雙向列表。遍歷Map中的元素，遍歷的順序是按照訪問時間從小到大輸出。

7.4 散列表+鏈表結(jié)構(gòu)特點

散列表：支持高效地插入、刪除、查找操作。
雙向鏈表：按照某種順序遍歷數(shù)據(jù)。
兩者結(jié)合在一起就可以實現(xiàn)按照某種順序遍歷散列表中的數(shù)據(jù)。

7.5 應(yīng)用

假設(shè)獵聘網(wǎng)有 10 萬名獵頭，每個獵頭都可以通過做任務(wù)（比如發(fā)布職位）來積累積分，然后通過積分來下載簡歷。假設(shè)你是獵聘網(wǎng)的一名工程師，如何在內(nèi)存中存儲這 10 萬個獵頭 ID 和積分信息，讓它能夠支持這樣幾個操作：
根據(jù)獵頭的 ID 快速查找、刪除、更新這個獵頭的積分信息；
查找積分在某個區(qū)間的獵頭 ID 列表；
查找按照積分從小到大排名在第 x 位到第 y 位之間的獵頭 ID 列表。
　以積分排序構(gòu)建一個跳表，按照ID做key構(gòu)建一個散列表。
　在散列表中根據(jù)ID查找、刪除、插入積分信息。
　在跳表查找積分區(qū)間內(nèi)的ID。
　最后一個操作以后實現(xiàn)，目前做不到。

總結(jié)

以上是生活随笔為你收集整理的数据结构四——散列表(下)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。