散列表雖然支持高效的數(shù)據(jù)插入肮之、刪除和查找操作，但是其中的數(shù)據(jù)都是通過散列函數(shù)打亂之后無規(guī)律的爽雄。也就是說，它無法按照某種順序快速地遍歷。如果想有序遍歷散列表中的數(shù)據(jù)贝次，那就需要將數(shù)據(jù)拷貝到數(shù)組中，然后排序再遍歷彰导。
散列表是動(dòng)態(tài)的數(shù)據(jù)結(jié)構(gòu)蛔翅，不停地進(jìn)行數(shù)據(jù)的插入敲茄、刪除，當(dāng)我們想按順序遍歷散列表時(shí)山析，都需要先排序堰燎，這樣效率會(huì)很低。為了解決這個(gè)問題笋轨，就將散列表和鏈表（或者跳表）結(jié)合在一起使用秆剪。
常見的使用場(chǎng)景：
- LRU 緩存淘汰算法可以用鏈表和散列表實(shí)現(xiàn)；
- Redis 有序集合用到了跳表和散列表爵政；
- Java 的 LinkedHashMap 也用到了散列表和鏈表仅讽。
1. LRU 緩存淘汰算法
實(shí)際上，一個(gè)緩存（cache）系統(tǒng)主要包含下面這幾個(gè)操作：
- 往緩存中添加一個(gè)數(shù)據(jù)钾挟；
- 從緩存中刪除一個(gè)數(shù)據(jù)洁灵；
- 在緩存中查找一個(gè)數(shù)據(jù)。
上面三個(gè)操作都涉及查找操作掺出，如果單純地用鏈表徽千，查找的時(shí)間復(fù)雜度是 O(n)。如果用散列表和鏈表汤锨，時(shí)間復(fù)雜度變?yōu)?O(1)双抽。
使用雙向鏈表存儲(chǔ)數(shù)據(jù)，鏈表中的每個(gè)結(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)（data）泥畅、前驅(qū)指針（prev）荠诬、后繼指針（next）之外，還新增了一個(gè)特殊的字段 hnext位仁。
prev|data|next|hnext
每個(gè)結(jié)點(diǎn)會(huì)在兩條鏈中柑贞。一個(gè)鏈?zhǔn)请p向鏈表，另一個(gè)鏈?zhǔn)巧⒘斜碇械睦溎羟馈Ｇ膀?qū)和后繼指針是為了將結(jié)點(diǎn)串在雙向鏈表中钧嘶，hnext 指針是為了將結(jié)點(diǎn)串在散列表的拉鏈中。
整個(gè)過程涉及的查找操作都可以通過散列表來完成琳疏。其他的操作有决，比如刪除頭結(jié)點(diǎn)、鏈表尾部插入數(shù)據(jù)等空盼，都可以在 O(1) 的時(shí)間復(fù)雜度內(nèi)完成书幕。所以，這三個(gè)操作的時(shí)間復(fù)雜度都是 O(1)揽趾。
2. Redis 有序集合
實(shí)際上台汇，在有序集合中，每個(gè)成員對(duì)象有兩個(gè)重要的屬性，key（鍵值）和score（分值）苟呐。不僅會(huì)通過 score 來查找數(shù)據(jù)痒芝，還會(huì)通過 key 來查找數(shù)據(jù)。
如果細(xì)化一下 Redis 有序集合的操作牵素，那就是下面這樣：
- 添加一個(gè)成員對(duì)象严衬；
- 按照鍵值來刪除一個(gè)成員對(duì)象；
- 按照鍵值來查找一個(gè)成員對(duì)象笆呆；
- 按照分值區(qū)間查找數(shù)據(jù)请琳，比如查找積分在 [100, 356] 之間的成員對(duì)象；
- 按照分值從小到大排序成員變量腰奋；
如果僅僅按照分值將成員對(duì)象組織成跳表的結(jié)構(gòu)单起，那么按照鍵值來刪除、查詢成員對(duì)象就會(huì)很慢劣坊。這時(shí)可以再按照鍵值構(gòu)建一個(gè)散列表，按照 key 來刪除屈留、查找一個(gè)成員對(duì)象的時(shí)間復(fù)雜度就變成了 O(1)局冰。
3. Java LinkedHashMap
LinkedHashMap 是通過雙向鏈表和散列表這兩種數(shù)據(jù)結(jié)構(gòu)組合實(shí)現(xiàn)的。LinkedHashMap 中的“Linked”實(shí)際上是指的是雙向鏈表灌危，并非指用鏈表法解決散列沖突康二。
按照訪問時(shí)間排序的 LinkedHashMap 本身就是一個(gè)支持 LRU 緩存淘汰策略的緩存系統(tǒng)。實(shí)際上勇蝙，它們兩個(gè)的實(shí)現(xiàn)原理也是一模一樣沫勿。
課后思考
今天講的幾個(gè)散列表和鏈表結(jié)合使用的例子里，用的都是雙向鏈表味混。如果把雙向鏈表改成單鏈表产雹，還能否正常工作呢？為什么呢翁锡？
其實(shí)蔓挖，依然能夠工作。但是馆衔，插入和刪除的時(shí)候瘟判，需要查找前驅(qū)指針，時(shí)間復(fù)雜度 O(n)角溃。
