來(lái)年加薪必備，2020年攻破數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記-數(shù)據(jù)結(jié)構(gòu)篇

著名數(shù)據(jù)專(zhuān)家沃斯曾說(shuō)：算法+數(shù)據(jù)結(jié)構(gòu)=程序

今天我們就來(lái)講講數(shù)據(jù)結(jié)構(gòu)

1. 數(shù)組

數(shù)組（Array）是一種 線性表數(shù)據(jù)結(jié)構(gòu)。它用一組 連續(xù)的內(nèi)存空間，來(lái)存儲(chǔ)一組具有 相同類(lèi)型的數(shù)據(jù)。具有的特性：

1. 線性表
2. 連續(xù)的內(nèi)存空間
3. 相同類(lèi)型的數(shù)據(jù)
4. 可以隨機(jī)訪問(wèn)
5. 數(shù)據(jù)操作比較低效，平均情況時(shí)間復(fù)雜度為 O(n)

數(shù)組為什么下標(biāo)從0開(kāi)始

1. 由于數(shù)組是是一種線性表數(shù)據(jù)結(jié)構(gòu)。它用一組 連續(xù)的內(nèi)存空間，來(lái)存儲(chǔ)一組具有 相同類(lèi)型的數(shù)據(jù)。 所以:

• 如果下標(biāo)從0開(kāi)始: 計(jì)算下標(biāo)為k的對(duì)象的地址的公式為：a[k]_address = base_address + k * type_size
• 如果下標(biāo)從1開(kāi)始: 計(jì)算下標(biāo)為k的對(duì)象的地址的公式為：a[k]_address = base_address + (k-1) * type_size 對(duì)于 CPU 來(lái)說(shuō)，就是多了一次減法指令。

1. C 語(yǔ)言設(shè)計(jì)者用 0 開(kāi)始計(jì)數(shù)數(shù)組下標(biāo)，之后的 Java、JavaScript 等高級(jí)語(yǔ)言都效仿了 C 語(yǔ)言。

容器能否完全替代數(shù)組？

例如Java的ArrayList，ArrayList 最大的優(yōu)勢(shì)就是可以將很多數(shù)組操作的細(xì)節(jié)封裝起來(lái)。比如前面提到的數(shù)組插入、刪除數(shù)據(jù)時(shí)需要搬移其他數(shù)據(jù)等。另外，它還有一個(gè)優(yōu)勢(shì)，就是支持動(dòng)態(tài)擴(kuò)容。

那么，作為高級(jí)語(yǔ)言編程者，是不是數(shù)組就無(wú)用武之地了呢？當(dāng)然不是，有些時(shí)候，用數(shù)組會(huì)更合適些，總的來(lái)說(shuō)，對(duì)于業(yè)務(wù)開(kāi)發(fā)，直接使用容器就足夠了，省時(shí)省力。畢竟損耗一丟丟性能，完全不會(huì)影響到系統(tǒng)整體的性能。但如果你是做一些非常底層的開(kāi)發(fā)，比如開(kāi)發(fā)網(wǎng)絡(luò)框架，性能的優(yōu)化需要做到極致，這個(gè)時(shí)候數(shù)組就會(huì)優(yōu)于容器，成為首選。

2. 鏈表 （Linked list）

不需要一塊連續(xù)的內(nèi)存空間，它通過(guò)“指針”將一組零散的內(nèi)存塊串聯(lián)起來(lái)使用。

image

幾種常見(jiàn)的鏈表形式：
1\. 單鏈表
2\. 循環(huán)鏈表
3\. 雙向鏈表 （空間換時(shí)間思想）
4\. 雙向循環(huán)列表

與數(shù)組的對(duì)比：

image

不過(guò)，數(shù)組和鏈表的對(duì)比，并不能局限于時(shí)間復(fù)雜度。而且，在實(shí)際的軟件開(kāi)發(fā)中，不能僅僅利用復(fù)雜度分析就決定使用哪個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)數(shù)據(jù)。

寫(xiě)鏈表代碼的幾個(gè)技巧：
1\. 理解指針或引用的含義、警惕指針丟失和內(nèi)存泄漏
2\. 利用哨兵簡(jiǎn)化實(shí)現(xiàn)難度
3\. 重點(diǎn)留意邊界條件處理
4\. 舉例畫(huà)圖、輔助思考
復(fù)制代碼

寫(xiě)鏈表代碼是最考驗(yàn)邏輯思維能力的。因?yàn)椋湵泶a到處都是指針的操作、邊界條件的處理，稍有不慎就容易產(chǎn)生 Bug。鏈表代碼寫(xiě)得好壞，可以看出一個(gè)人寫(xiě)代碼是否夠細(xì)心，考慮問(wèn)題是否全面，思維是否縝密。所以，這也是很多面試官喜歡讓人手寫(xiě)鏈表代碼的原因。所以，這一節(jié)講到的東西，你一定要自己寫(xiě)代碼實(shí)現(xiàn)一下，才有效果。

1. 單鏈表反轉(zhuǎn)
2. 鏈表中環(huán)的檢測(cè)
3. 兩個(gè)有序的鏈表合并
4. 刪除鏈表倒數(shù)第 n 個(gè)結(jié)點(diǎn)
5. 求鏈表的中間結(jié)點(diǎn)

3. 棧

• 用數(shù)組實(shí)現(xiàn)的 順序棧
• 用鏈表實(shí)現(xiàn)的 鏈?zhǔn)綏?/li>
• 出棧入棧時(shí)間復(fù)雜度 空間復(fù)雜度都是O（1）
• 先進(jìn)后出

應(yīng)用：

• 1，函數(shù)的臨時(shí)變量的存儲(chǔ)銷(xiāo)毀
• 2，表達(dá)式求值
• 3，瀏覽器的前進(jìn)后退

4. 隊(duì)列

特點(diǎn)：先進(jìn)先出

• 用數(shù)組實(shí)現(xiàn) 順序隊(duì)列
• 用鏈表實(shí)現(xiàn) 鏈?zhǔn)疥?duì)列

隊(duì)列拓展：

• 循環(huán)隊(duì)列 解決用數(shù)組實(shí)現(xiàn)的隊(duì)列需要數(shù)據(jù)遷移的問(wèn)題 隊(duì)空：head == tail 隊(duì)滿：(tail+1)%n=head。
• 阻塞隊(duì)列 隊(duì)列滿了時(shí)，不給入隊(duì)。 生產(chǎn)者 - 消費(fèi)者模型
• 并發(fā)隊(duì)列 線程安全的隊(duì)列我們叫作并發(fā)隊(duì)列

5. 跳表

我們知道，數(shù)組支持快速的隨機(jī)訪問(wèn)，而鏈表不支持，這樣的話，就不能用二分查找法來(lái)對(duì)鏈表進(jìn)行快速查找。實(shí)際上，我們只需要對(duì)鏈表稍加改造，就可以支持類(lèi)似“二分”的查找算法。我們把改造之后的數(shù)據(jù)結(jié)構(gòu)叫作跳表（Skip list）。

跳表，其實(shí)就是對(duì) 有序鏈表建立多級(jí)“索引”，每?jī)蓚€(gè)（也可以是其他數(shù)量）結(jié)點(diǎn)提取一個(gè)結(jié)點(diǎn)到上一級(jí)，我們把抽出來(lái)的那一級(jí)叫作索引或索引層。你可以看我畫(huà)的圖。圖中的 down 表示 down 指針，指向下一級(jí)結(jié)點(diǎn)。

image

如果我們現(xiàn)在要查找某個(gè)結(jié)點(diǎn)，比如 16。我們可以先在索引層遍歷，當(dāng)遍歷到索引層中值為 13 的結(jié)點(diǎn)時(shí)，我們發(fā)現(xiàn)下一個(gè)結(jié)點(diǎn)是 17，那要查找的結(jié)點(diǎn) 16 肯定就在這兩個(gè)結(jié)點(diǎn)之間。然后我們通過(guò)索引層結(jié)點(diǎn)的 down 指針，下降到原始鏈表這一層，繼續(xù)遍歷。這個(gè)時(shí)候，我們只需要再遍歷 2 個(gè)結(jié)點(diǎn)，就可以找到值等于 16 的這個(gè)結(jié)點(diǎn)了。這樣，原來(lái)如果要查找 16，需要遍歷 10 個(gè)結(jié)點(diǎn)，現(xiàn)在只需要遍歷 7 個(gè)結(jié)點(diǎn)。

我舉的例子數(shù)據(jù)量不大，查找效率的提升也并不明顯。為了讓你能真切地感受索引提升查詢效率。我畫(huà)了一個(gè)包含 64 個(gè)結(jié)點(diǎn)的鏈表，按照前面講的這種思路，建立了五級(jí)索引。

image

從圖中我們可以看出，原來(lái)沒(méi)有索引的時(shí)候，查找 62 需要遍歷 62 個(gè)結(jié)點(diǎn)，現(xiàn)在只需要遍歷 11 個(gè)結(jié)點(diǎn)，速度是不是提高了很多？所以，當(dāng)鏈表的長(zhǎng)度 n 比較大時(shí)，比如 1000、10000 的時(shí)候，在構(gòu)建索引之后，查找效率的提升就會(huì)非常明顯。

時(shí)間復(fù)雜度：

跳表查詢某個(gè)數(shù)據(jù)的時(shí)間復(fù)雜度是多少呢？

按照我們剛才講的，每?jī)蓚€(gè)結(jié)點(diǎn)會(huì)抽出一個(gè)結(jié)點(diǎn)作為上一級(jí)索引的結(jié)點(diǎn)，那第一級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)大約就是 n/2，第二級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)大約就是 n/4，第三級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)大約就是 n/8，依次類(lèi)推，也就是說(shuō)， 第 k 級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)是第 k-1 級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)的 1/2，那第 k級(jí)索引結(jié)點(diǎn)的個(gè)數(shù)就是 n/(2k)。

假設(shè)索引有 h 級(jí)，最高級(jí)的索引有 2 個(gè)結(jié)點(diǎn)。通過(guò)上面的公式，我們可以得到 n/(2h)=2，從而求得 h=log2n-1。如果包含原始鏈表這一層，整個(gè)跳表的高度就是 log2n。我們?cè)谔碇胁樵兡硞€(gè)數(shù)據(jù)的時(shí)候，如果每一層都要遍歷 m 個(gè)結(jié)點(diǎn)，那在跳表中查詢一個(gè)數(shù)據(jù)的時(shí)間復(fù)雜度就是 O(m*logn)。

那這個(gè) m 的值是多少呢？按照前面這種索引結(jié)構(gòu)，我們每一級(jí)索引都最多只需要遍歷 3 個(gè)結(jié)點(diǎn)，也就是說(shuō) m=3。

所以在跳表中查詢?nèi)我鈹?shù)據(jù)的時(shí)間復(fù)雜度就是  O(logn)。這個(gè)查找的時(shí)間復(fù)雜度跟二分查找是一樣的。換句話說(shuō)，我們其實(shí)是基于單鏈表實(shí)現(xiàn)了二分查找，是不是很神奇？不過(guò)，天下沒(méi)有免費(fèi)的午餐，這種查詢效率的提升，前提是建立了很多級(jí)索引，也就是我們?cè)诘?6 節(jié)講過(guò)的空間換時(shí)間的設(shè)計(jì)思路。

空間復(fù)雜度：

跳表是不是很浪費(fèi)內(nèi)存？比起單純的單鏈表，跳表需要存儲(chǔ)多級(jí)索引，肯定要消耗更多的存儲(chǔ)空間。那到底需要消耗多少額外的存儲(chǔ)空間呢？我們來(lái)分析一下跳表的空間復(fù)雜度。

跳表的空間復(fù)雜度分析并不難，我在前面說(shuō)了，假設(shè)原始鏈表大小為 n，那第一級(jí)索引大約有 n/2 個(gè)結(jié)點(diǎn)，第二級(jí)索引大約有 n/4 個(gè)結(jié)點(diǎn)，以此類(lèi)推，每上升一級(jí)就減少一半，直到剩下 2 個(gè)結(jié)點(diǎn)。如果我們把每層索引的結(jié)點(diǎn)數(shù)寫(xiě)出來(lái)，就是一個(gè)等比數(shù)列。

image

這幾級(jí)索引的結(jié)點(diǎn)總和就是 n/2+n/4+n/8…+8+4+2=n-2。所以，跳表的空間復(fù)雜度是 O(n)。也就是說(shuō)，如果將包含 n 個(gè)結(jié)點(diǎn)的單鏈表構(gòu)造成跳表，我們需要額外再用接近 n 個(gè)結(jié)點(diǎn)的存儲(chǔ)空間。那我們有沒(méi)有辦法降低索引占用的內(nèi)存空間呢？

我們前面都是每?jī)蓚€(gè)結(jié)點(diǎn)抽一個(gè)結(jié)點(diǎn)到上級(jí)索引，如果我們每三個(gè)結(jié)點(diǎn)或五個(gè)結(jié)點(diǎn)，抽一個(gè)結(jié)點(diǎn)到上級(jí)索引，是不是就不用那么多索引結(jié)點(diǎn)了呢？

第一級(jí)索引需要大約 n/3 個(gè)結(jié)點(diǎn)，第二級(jí)索引需要大約 n/9 個(gè)結(jié)點(diǎn)。每往上一級(jí)，索引結(jié)點(diǎn)個(gè)數(shù)都除以 3。為了方便計(jì)算，我們假設(shè)最高一級(jí)的索引結(jié)點(diǎn)個(gè)數(shù)是 1。我們把每級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)都寫(xiě)下來(lái)，也是一個(gè)等比數(shù)列。

image

通過(guò)等比數(shù)列求和公式，總的索引結(jié)點(diǎn)大約就是 n/3+n/9+n/27+…+9+3+1=n/2。盡管空間復(fù)雜度還是 O(n)，但比上面的每?jī)蓚€(gè)結(jié)點(diǎn)抽一個(gè)結(jié)點(diǎn)的索引構(gòu)建方法，要減少了一半的索引結(jié)點(diǎn)存儲(chǔ)空間。

實(shí)際上，在軟件開(kāi)發(fā)中，我們不必太在意索引占用的額外空間。在講數(shù)據(jù)結(jié)構(gòu)和算法時(shí)，我們習(xí)慣性地把要處理的數(shù)據(jù)看成整數(shù)，但是在實(shí)際的軟件開(kāi)發(fā)中，原始鏈表中存儲(chǔ)的有可能是很大的對(duì)象，而索引結(jié)點(diǎn)只需要存儲(chǔ)關(guān)鍵值和幾個(gè)指針，并不需要存儲(chǔ)對(duì)象， 所以當(dāng)對(duì)象比索引結(jié)點(diǎn)大很多時(shí)，那索引占用的額外空間就可以忽略了。

跳表索引動(dòng)態(tài)更新

當(dāng)我們不停地往跳表中插入數(shù)據(jù)時(shí)，如果我們不更新索引，就有可能出現(xiàn)某 2 個(gè)索引結(jié)點(diǎn)之間數(shù)據(jù)非常多的情況。極端情況下，跳表還會(huì)退化成單鏈表。

image

作為一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，我們需要某種手段來(lái)維護(hù)索引與原始鏈表大小之間的平衡，也就是說(shuō)，如果鏈表中結(jié)點(diǎn)多了，索引結(jié)點(diǎn)就相應(yīng)地增加一些，避免復(fù)雜度退化，以及查找、插入、刪除操作性能下降。

當(dāng)我們往跳表中插入數(shù)據(jù)的時(shí)候，我們可以選擇同時(shí)將這個(gè)數(shù)據(jù)插入到部分索引層中。如何選擇加入哪些索引層呢？

我們通過(guò)一個(gè)隨機(jī)函數(shù)，來(lái)決定將這個(gè)結(jié)點(diǎn)插入到哪幾級(jí)索引中，比如隨機(jī)函數(shù)生成了值 K，那我們就將這個(gè)結(jié)點(diǎn)添加到第一級(jí)到第 K 級(jí)這 K 級(jí)索引中。

image

隨機(jī)函數(shù)的選擇很有講究，從概率上來(lái)講，能夠保證跳表的索引大小和數(shù)據(jù)大小平衡性，不至于性能過(guò)度退化。

跳表特點(diǎn)：

1. 前提是有序鏈表
2. 動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)
3. 支持快速的查詢、插入、刪除操作，時(shí)間復(fù)雜度為O(logn)
4. 表面上空間復(fù)雜度是O(n)，但是因?yàn)樗饕恍枰鎯?chǔ)關(guān)鍵值和幾個(gè)指針，并不需要存儲(chǔ)對(duì)象，所以當(dāng)對(duì)象比索引結(jié)點(diǎn)大很多時(shí)，那索引占用的額外空間就可以忽略了。
5. 和紅黑樹(shù)相比的優(yōu)勢(shì)：當(dāng)需要按區(qū)間查找數(shù)據(jù)時(shí)，跳表可以做到 O(logn) 的時(shí)間復(fù)雜度定位區(qū)間的起點(diǎn)，然后在原始鏈表中順序往后遍歷就可以了。
6. 代碼實(shí)現(xiàn)比紅黑樹(shù)容易很多。

6. 散列表

image

特性：

1. 基于數(shù)組可以根據(jù)下標(biāo)快速查詢的特點(diǎn)
2. 利用散列函數(shù)，可以把key散列后得出正整數(shù)，也就是數(shù)組的下標(biāo)，進(jìn)行快速查找。
3. 插入、查找、刪除的時(shí)間復(fù)雜度都是O(1)

散列沖突：

1. 散列值很大可能會(huì)重復(fù)，所以就有了散列沖突
2. 解決散列沖突的兩種方式：  開(kāi)放尋址法：線性探測(cè)、二次探測(cè)、雙重散列 優(yōu)點(diǎn)： 散列表中的數(shù)據(jù)都存儲(chǔ)在數(shù)組中，可以有效地利用 CPU 緩存加快查詢速度。而且，這種方法實(shí)現(xiàn)的散列表，序列化起來(lái)比較簡(jiǎn)單。 缺點(diǎn)：1.刪除數(shù)據(jù)的時(shí)候比較麻煩，需要特殊標(biāo)記已經(jīng)刪除掉的數(shù)據(jù)；2.裝載因子的上限不能太大，這也導(dǎo)致這種方法比鏈表法更浪費(fèi)內(nèi)存空間。 總結(jié)：當(dāng)數(shù)據(jù)量比較小、裝載因子小的時(shí)候，適合采用開(kāi)放尋址法。這也是 Java 中的ThreadLocalMap使用開(kāi)放尋址法解決散列沖突的原因。  鏈表法 優(yōu)點(diǎn)：1.內(nèi)存的利用率比開(kāi)放尋址法要高，需要用的時(shí)候再申請(qǐng)；2.對(duì)大裝載因子的容忍度更高；3.可以用跳表、紅黑樹(shù)來(lái)代替普通的鏈表，這樣的話即使是極端情況下，時(shí)間復(fù)雜度也只是O(logn) 總結(jié)：比較適合存儲(chǔ)大對(duì)象、大數(shù)據(jù)量的散列表，而且，比起開(kāi)放尋址法，它更加靈活，支持更多的優(yōu)化策略，比如用紅黑樹(shù)代替鏈表。
3. 用裝載因子來(lái)表示空位的多少 裝載因子 = 填入表中的元素個(gè)數(shù)/散列表的長(zhǎng)度 裝載因子越大，說(shuō)明空閑位置越少，沖突越多，散列表的性能會(huì)下降。

工業(yè)級(jí)水平的散列表：

最終要求：

1. 支持快速的查詢、插入、刪除操作；
2. 內(nèi)存占用合理，不能浪費(fèi)過(guò)多的內(nèi)存空間；
3. 性能穩(wěn)定，極端情況下，散列表的性能也不會(huì)退化到無(wú)法接受的情況。

具體設(shè)計(jì)方向：

1. 散列函數(shù)要求： 盡可能要設(shè)計(jì)得讓散列值均勻分布 不能設(shè)計(jì)得太復(fù)雜計(jì)算時(shí)間太久
2. 支持動(dòng)態(tài)擴(kuò)容 根據(jù)裝載因子大小來(lái)進(jìn)行動(dòng)態(tài)擴(kuò)容，當(dāng)裝載因子超過(guò)閾值時(shí)，進(jìn)行擴(kuò)展。 合理設(shè)置裝載因子的閾值，如果太大，會(huì)導(dǎo)致沖突過(guò)多；如果太小，會(huì)導(dǎo)致內(nèi)存浪費(fèi)嚴(yán)重。 裝載因子閾值的設(shè)置要權(quán)衡時(shí)間、空間復(fù)雜度。如果內(nèi)存空間不緊張，對(duì)執(zhí)行效率要求很高，可以降低負(fù)載因子的閾值；相反，如果內(nèi)存空間緊張，對(duì)執(zhí)行效率要求又不高，可以增加負(fù)載因子的值，甚至可以大于 1。
3. 合理選擇沖突解決方法

散列表和鏈表的組合應(yīng)用

LRU 緩存淘汰算法

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

image

利用散列表，可以讓在鏈表里查找某個(gè)數(shù)據(jù)的時(shí)間復(fù)雜度為O(1)，而鏈表本身的刪除和插入操作時(shí)間復(fù)雜度為O(1)。

Redis 有序集合

舉個(gè)例子，比如用戶積分排行榜有這樣一個(gè)功能：我們可以通過(guò)用戶的 ID 來(lái)查找積分信息，也可以通過(guò)積分區(qū)間來(lái)查找用戶 ID 或者姓名信息。這里包含 ID、姓名和積分的用戶信息，就是成員對(duì)象，用戶 ID 就是 key，積分就是 score。

所以，如果我們細(xì)化一下 Redis 有序集合的操作，那就是下面這樣：

• 添加一個(gè)成員對(duì)象；
• 按照鍵值來(lái)刪除一個(gè)成員對(duì)象；
• 按照鍵值來(lái)查找一個(gè)成員對(duì)象；
• 按照分值區(qū)間查找數(shù)據(jù)，比如查找積分在 [100, 356] 之間的成員對(duì)象；
• 按照分值從小到大排序成員變量；

如果我們僅僅按照分值將成員對(duì)象組織成跳表的結(jié)構(gòu)，那按照鍵值來(lái)刪除、查詢成員對(duì)象就會(huì)很慢，解決方法與 LRU 緩存淘汰算法的解決方法類(lèi)似。我們可以再按照鍵值構(gòu)建一個(gè)散列表，這樣按照 key 來(lái)刪除、查找一個(gè)成員對(duì)象的時(shí)間復(fù)雜度就變成了 O(1)。同時(shí)，借助跳表結(jié)構(gòu)，其他操作也非常高效。

Java LinkedHashMap

如果你熟悉 Java，那你幾乎天天會(huì)用到這個(gè)容器。我們之前講過(guò)，HashMap 底層是通過(guò)散列表這種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的。而 LinkedHashMap 前面比 HashMap 多了一個(gè)“Linked”，這里的“Linked”是不是說(shuō)，LinkedHashMap 是一個(gè)通過(guò)鏈表法解決散列沖突的散列表呢？

實(shí)際上，LinkedHashMap 并沒(méi)有這么簡(jiǎn)單，其中的“Linked”也并不僅僅代表它是通過(guò)鏈表法解決散列沖突的。

你可能已經(jīng)猜到了，LinkedHashMap 也是通過(guò)散列表和鏈表組合在一起實(shí)現(xiàn)的。我們先看下面這段代碼：

// 10是初始大小，0.75是裝載因子，true是表示按照訪問(wèn)時(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。

其實(shí)，按照訪問(wèn)時(shí)間排序的 LinkedHashMap 本身就是一個(gè)支持 LRU 緩存淘汰策略的緩存系統(tǒng)？實(shí)際上，它們兩個(gè)的實(shí)現(xiàn)原理也是一模一樣的。

總結(jié)一下，實(shí)際上， LinkedHashMap 是通過(guò)雙向鏈表和散列表這兩種數(shù)據(jù)結(jié)構(gòu)組合實(shí)現(xiàn)的。LinkedHashMap 中的“Linked”實(shí)際上是指的是雙向鏈表，并非指用鏈表法解決散列沖突。

為什么散列表和鏈表經(jīng)常一塊使用？

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

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

最后

如果需要看視頻學(xué)習(xí)，可以看： https://zhuanlan.zhihu.com/p/96130186