有兩種數(shù)據(jù)結(jié)構(gòu)（散列表和鏈表）經(jīng)常會(huì)被放在一起使用。前面的章節(jié)中有兩個(gè)地方講到散列表和鏈表的組合使用传货，分別是：
另外损离，Java中有一個(gè)容器LinkedHashMap也使用到散列表和鏈表。
下面我們來看看這幾個(gè)問題，散列表和鏈表是如何組合使用的窟勃。
LRU緩存淘汰算法
首先來回顧一下當(dāng)時(shí)是如何通過鏈表實(shí)現(xiàn)LRU緩存淘汰算法的秉氧。
- 當(dāng)緩存空間不夠，需要淘汰一個(gè)數(shù)據(jù)的時(shí)候汁咏，就直接將鏈表頭部的結(jié)點(diǎn)刪除攘滩。
- 當(dāng)緩存某個(gè)數(shù)據(jù)的時(shí)候纸泡，先在鏈表中查找這個(gè)數(shù)據(jù)女揭，如果沒有找到，則直接將數(shù)據(jù)放到鏈表的尾部磷仰；如果找到芒划，就把它移動(dòng)到鏈表的尾部欧穴。
總結(jié)一下涮帘，一個(gè)緩存（cache）系統(tǒng)主要包含下面幾個(gè)操作：
- 往緩存中添加一個(gè)數(shù)據(jù)调缨；
- 從緩存中刪除一個(gè)數(shù)據(jù)弦叶；
- 在緩存中查找一個(gè)數(shù)據(jù)；
因?yàn)椴檎覕?shù)據(jù)需要遍歷鏈表燕侠，所以使用鏈表實(shí)現(xiàn)的LRU緩存淘汰算法的時(shí)候復(fù)雜度是O(n)。
如果將散列表和鏈表兩種數(shù)據(jù)結(jié)構(gòu)組合使用七问，就可以把這三個(gè)操作的時(shí)間復(fù)雜度都降低到O(1)械巡。
具體的結(jié)構(gòu)如下：
使用雙向鏈表存儲(chǔ)數(shù)據(jù)，鏈表中的每個(gè)結(jié)點(diǎn)處理存儲(chǔ)數(shù)據(jù)（data）疹启、前驅(qū)指針（prev）皮仁、后繼指針（next）贷祈、還有一個(gè)特殊字段hnext势誊，是為了將結(jié)點(diǎn)串在散列表的拉鏈中粟耻。
再來看看挤忙，緩存的三個(gè)操作是如何做到時(shí)間復(fù)雜度是O(1)的册烈。
如何查找一個(gè)數(shù)據(jù)
- 通過散列表可以很快找到一個(gè)數(shù)據(jù)，然后移到雙向鏈表的尾部大猛。
如何刪除一個(gè)數(shù)據(jù)
- 通過散列表在O(1)時(shí)間內(nèi)找到結(jié)點(diǎn)挽绩，再通過雙向鏈表找到前驅(qū)結(jié)點(diǎn)，刪除當(dāng)前結(jié)點(diǎn)驾中。
如何添加一個(gè)數(shù)據(jù)
- 添加數(shù)據(jù)到緩存稍微有點(diǎn)麻煩唉堪。需要先看這個(gè)數(shù)據(jù)是否在緩存中模聋。
- 如果在，移到雙向鏈表的尾部巨坊；
- 如果不在撬槽，還要看緩存是否滿此改；
- 如果滿了趾撵，就將雙向鏈表頭部的結(jié)點(diǎn)刪除，然后再將數(shù)據(jù)放到鏈表的尾部共啃；
- 如果沒滿占调，就直接將數(shù)據(jù)放到鏈表的尾部。
到此移剪，通過散列表和雙向鏈表的組合使用究珊，實(shí)現(xiàn)了一個(gè)高效的纵苛、支持LRU緩存淘汰算法的緩存系統(tǒng)原型。
Redis有序集合
在有序集合中瞬浓，每個(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ì)很慢秽五。解決辦法跟LRU緩存淘汰算法類似，再按照鍵值構(gòu)建一個(gè)散列表，這樣按照key來刪除、查找一個(gè)成員對(duì)象的時(shí)間復(fù)雜度就變成了O(1)蓖救。
Java LinkedHashMap
看一下這段代碼：
// 10是初始大小斩例，0.75是裝載因子晶乔，true是表示按照訪問時(shí)間排序
HashMap<Integer, Integer> m = new LinkedHashMap<>(10, 0.75f, true);
m.put(3, 11);
m.put(1, 12);
m.put(5, 23);
m.put(2, 22);
m.put(3, 26);
m.get(5);
for (Map.Entry e : m.entrySet()) {
System.out.println(e.getKey());
}
這段代碼打印的結(jié)果是1，2回还，3运提，5。
每次調(diào)用put()函數(shù)，往LinkedHashMap中添加數(shù)據(jù)的時(shí)候，都會(huì)將數(shù)據(jù)添加到鏈表的尾部。
前6行代碼執(zhí)行后的效果：
第7行代碼（m.put(3, 26);）執(zhí)行后的效果：
第8行代碼（m.get(5);）執(zhí)行后的效果：
LinkedHashMap是通過雙向鏈表和散列表這兩種數(shù)據(jù)結(jié)構(gòu)組合實(shí)現(xiàn)的。LinkedHashMap中的“Linked”實(shí)際上是指的是雙向鏈表，并非指用鏈表法解決散列沖突伟件。
總結(jié)一下，為什么散列表和鏈表經(jīng)常一起使用？
散列表這種數(shù)據(jù)結(jié)構(gòu)雖然支持非常高效的數(shù)據(jù)插入闪萄、刪除为迈、查找操作耿战，但是散列表中的數(shù)據(jù)都是通過散列函數(shù)打亂之后無規(guī)律存儲(chǔ)的狐胎。
因?yàn)樯⒘斜硎莿?dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，不停地有數(shù)據(jù)的插入、刪除砚哆，所以每當(dāng)希望按順序遍歷散列表中的數(shù)據(jù)的時(shí)候绪钥，都需要先排序，那效率就很低。為了解決這個(gè)問題寸潦，將散列表和鏈表（或者跳表）結(jié)合在一起使用斩箫。
