鏈表：數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)
我們通過(guò)一個(gè)簡(jiǎn)單的場(chǎng)景洋魂，了解一下鏈表的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)。那就是LRU緩存淘汰算法。

緩存是一種提高數(shù)據(jù)讀取性能的技術(shù),在硬件設(shè)計(jì)喜喂、軟件開(kāi)發(fā)中都有著非常廣泛的應(yīng)用,比如常見(jiàn)的CPU緩存究珊、數(shù)據(jù)庫(kù)緩存薪者、瀏覽器緩存等等。
緩存的大小有限,當(dāng)緩存被用滿(mǎn)時(shí),哪些數(shù)據(jù)應(yīng)該被清理出去,哪些數(shù)據(jù)應(yīng)該被保留?這就需要緩存淘汰策略來(lái)決定剿涮。常見(jiàn)的策略有三種:
1).先進(jìn)先出策略FIFO ( First In, FirstOut)言津、
2).最少使用策略LFU (Least Frequently Used)、
3).最近最少使用策略LRU ( Least Recently Used )取试。

如何使用鏈表來(lái)實(shí)現(xiàn)LRU緩存淘汰策略呢悬槽？？瞬浓？

相比數(shù)組初婆，鏈表是一種稍微復(fù)雜一點(diǎn)的數(shù)據(jù)結(jié)構(gòu)。對(duì)于初學(xué)者來(lái)說(shuō)，掌握起來(lái)也要比數(shù)組稍微難一些磅叛。這兩個(gè)非承伎龋基礎(chǔ)，非常常用的數(shù)據(jù)結(jié)構(gòu)弊琴，我們常常會(huì)放到一起比較兆龙。所以，我們先了解一下他們之間的區(qū)別吧Ｇ枚Ｗ匣省！

二者區(qū)別
首先從底層存儲(chǔ)結(jié)構(gòu)來(lái)看：
結(jié)合下圖腋寨，可以看出坝橡，數(shù)組需要一塊連續(xù)的內(nèi)存空間來(lái)存儲(chǔ)，對(duì)內(nèi)存的要求比較高精置。如果我們申請(qǐng)100MB大小的數(shù)組计寇，當(dāng)內(nèi)存中沒(méi)有連續(xù)的，足夠大的存儲(chǔ)空間時(shí)脂倦，即便內(nèi)存的剩余總可用空間大于100MB番宁，仍然會(huì)申請(qǐng)失敗
而鏈表確恰恰相反，它并不需要一塊連續(xù)的內(nèi)存空間赖阻，他通過(guò)"指針"將一組零散的內(nèi)存塊串聯(lián)起來(lái)使用蝶押，所以如果我們申請(qǐng)的是100MB大小的鏈表，根本不會(huì)有問(wèn)題

數(shù)組和鏈表的區(qū)別.png

鏈表結(jié)構(gòu)五花八門(mén)火欧，我們了解三種主要的鏈表棋电，也是最常見(jiàn)的三種鏈表結(jié)構(gòu)，它們分別是：單鏈表苇侵、雙向鏈表和循環(huán)鏈表赶盔。

單鏈表

鏈表通過(guò)指針將一組零散的內(nèi)存塊串聯(lián)在一起。其中榆浓，我們把內(nèi)存塊稱(chēng)為鏈表的“結(jié)點(diǎn)”于未。為了將所有的結(jié)點(diǎn)串起來(lái)，每個(gè)鏈表的結(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)之外陡鹃，還需要記錄鏈上的下一個(gè)結(jié)點(diǎn)的地址烘浦。如圖所示，我們把這個(gè)記錄下個(gè)結(jié)點(diǎn)地址的指針叫作后繼指針 next萍鲸。

image.png

從上圖可以看出闷叉，有兩個(gè)特殊的結(jié)點(diǎn)，分別是第一個(gè)和最后一個(gè)脊阴。我們習(xí)慣性吧第一個(gè)節(jié)點(diǎn)叫做頭結(jié)點(diǎn)握侧，把最后一個(gè)節(jié)點(diǎn)叫做尾結(jié)點(diǎn)捌肴。其中頭結(jié)點(diǎn)是用來(lái)記錄鏈表的基地址。有了它藕咏，我們就可以通過(guò)遍歷得到整條鏈表状知。而尾結(jié)點(diǎn)的特殊地方是：指針不指向下一個(gè)結(jié)點(diǎn)，而是指向一個(gè)空地址null孽查，表示這是鏈表上的最后一個(gè)結(jié)點(diǎn)

與數(shù)組一樣饥悴，鏈表也支持?jǐn)?shù)據(jù)的查找，插入和刪除操作盲再。

我們知道西设，在數(shù)組進(jìn)行插入和刪除的時(shí)候，為了確保數(shù)據(jù)的連續(xù)性答朋，會(huì)涉及到大量的數(shù)據(jù)搬移操作贷揽，所以時(shí)間復(fù)雜度是O(n)。而在鏈表中插入或者刪除一個(gè)數(shù)據(jù)梦碗，我們不需要保證數(shù)據(jù)的連續(xù)性禽绪，而作大量的數(shù)據(jù)搬移工作，因?yàn)殒湵淼拇鎯?chǔ)空間本身就不是連續(xù)的洪规。所以在鏈表中刪除一個(gè)數(shù)據(jù)是非秤∑ǎ快的。

針對(duì)鏈表的插入和刪除操作斩例，我們只需要考慮相鄰結(jié)點(diǎn)的指針改變雄人，所以對(duì)應(yīng)的時(shí)間復(fù)雜度是O(n)∧罡希可以參考下圖進(jìn)行理解础钠。

image.png

但是有利就有弊。鏈表要想訪問(wèn)第k個(gè)元素叉谜，就沒(méi)有數(shù)組那么高效了旗吁。因?yàn)殒湵頂?shù)據(jù)并非連續(xù)存儲(chǔ)。所以無(wú)法像數(shù)組那樣正罢，根據(jù)首地址和下標(biāo)阵漏，通過(guò)尋址公式就能計(jì)算出對(duì)應(yīng)的內(nèi)存地址驻民，而是需要根據(jù)指針一個(gè)結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)的依次遍歷翻具，直到找到相應(yīng)的結(jié)點(diǎn)。所以鏈表的查詢(xún)操作的時(shí)間復(fù)雜度就是O(n)

循環(huán)鏈表

循環(huán)鏈表是一種特殊的單鏈表回还。其實(shí)循環(huán)鏈表也是很簡(jiǎn)單的裆泳，它和單鏈表的唯一區(qū)別就在尾結(jié)點(diǎn)上。我們知道單鏈表的尾結(jié)點(diǎn)指針是指向空地址NULL的柠硕，而循環(huán)鏈表的尾結(jié)點(diǎn)指針是指向頭結(jié)點(diǎn)的工禾。正如下圖所示：

image.png

和單鏈表相比运提，循環(huán)鏈表的優(yōu)點(diǎn)就是從鏈尾到鏈頭比較方便。當(dāng)要處理的數(shù)據(jù)具有環(huán)形的結(jié)構(gòu)特點(diǎn)時(shí)闻葵，就特別適合采用循環(huán)鏈表民泵。盡管用單鏈表也可以實(shí)現(xiàn)，但是用循環(huán)鏈表實(shí)現(xiàn)的話槽畔，代碼會(huì)簡(jiǎn)潔很多栈妆。

雙向鏈表

單向鏈表只有一個(gè)方向，結(jié)點(diǎn)只有一個(gè)后繼指針next指向后面的結(jié)點(diǎn)厢钧。而雙向鏈表鳞尔，顧名思義，它支持兩個(gè)方向早直，每個(gè)結(jié)點(diǎn)不止有一個(gè)后繼指針next指向后面的結(jié)點(diǎn)寥假，還有一個(gè)前驅(qū)指針指向前面的結(jié)點(diǎn)。

雙向鏈表

通過(guò)上圖可以看出霞扬，雙向鏈表需要額外的兩個(gè)空間來(lái)存儲(chǔ)后繼結(jié)點(diǎn)和前驅(qū)結(jié)點(diǎn)的地址糕韧。所以，存儲(chǔ)同樣多的數(shù)據(jù)喻圃，雙向鏈表就要比單鏈表占用更多的內(nèi)存空間兔沃。雖然兩個(gè)指針比較浪費(fèi)空間，但是支持雙向遍歷级及，這樣也帶來(lái)雙向鏈表操作的靈活性乒疏。

雙向鏈表可以解決那些問(wèn)題呢？饮焦？怕吴？
從結(jié)構(gòu)上看，雙向鏈表可以支持O(1)時(shí)間復(fù)雜度的情況找到前驅(qū)結(jié)點(diǎn)县踢，正是這樣的特點(diǎn)转绷，也是雙向鏈表在某些情況下的插入、刪除等操作都要比單鏈表簡(jiǎn)單硼啤、高效议经。

這樣說(shuō)可能會(huì)有一些疑問(wèn)，單鏈表的效率已經(jīng)夠高了谴返，雙鏈表還能在高到什么程度么煞肾？我們了解一下。

插入嗓袱、刪除操作
在實(shí)際的開(kāi)發(fā)中籍救，從鏈表中刪除數(shù)據(jù)，無(wú)非就兩種情況：

• 刪除結(jié)點(diǎn)中"值等于某個(gè)給定值"的結(jié)點(diǎn)渠抹。
• 刪除指定指針指向的結(jié)點(diǎn)蝙昙。

第一種情況闪萄，不管是單鏈表還是雙鏈表，為了查找值等于給定值的結(jié)點(diǎn)奇颠，都需要從頭結(jié)點(diǎn)開(kāi)始一個(gè)一個(gè)依次遍歷找到對(duì)應(yīng)的結(jié)點(diǎn)败去，這樣的時(shí)間復(fù)雜度就是O(n)。然后進(jìn)行刪除操作烈拒，時(shí)間復(fù)雜度為O(1)为迈。盡管刪除操作的時(shí)間復(fù)雜度O(1)，但是需要找到這個(gè)結(jié)點(diǎn)缺菌，那么就必須要通過(guò)遍歷找到這個(gè)結(jié)點(diǎn)葫辐，根據(jù)時(shí)間復(fù)雜度分析中的加法法則，刪除值等于給定值的結(jié)點(diǎn)對(duì)應(yīng)的鏈表操作的總時(shí)間復(fù)雜度就是O(n)

第二種情況伴郁，我們已經(jīng)找到了要?jiǎng)h除的結(jié)點(diǎn)耿战，但是刪除某個(gè)結(jié)點(diǎn)q需要知道其前驅(qū)結(jié)點(diǎn)，而單鏈表并不支持直獲取前驅(qū)結(jié)點(diǎn)焊傅，所以剂陡，為了找到前驅(qū)結(jié)點(diǎn)，我們還是要從頭結(jié)點(diǎn)開(kāi)始遍歷鏈表狐胎，知道p->next=q鸭栖，說(shuō)明p是q的前驅(qū)結(jié)點(diǎn)。
但是對(duì)于雙鏈表來(lái)講握巢，這種情況就比較有優(yōu)勢(shì)了晕鹊。因?yàn)殡p鏈表中的結(jié)點(diǎn)已經(jīng)保存了前驅(qū)結(jié)點(diǎn)的指針，不需要像單鏈表那樣遍歷查找了暴浦。這樣對(duì)于這種情況的刪除操作來(lái)講溅话，單鏈表的刪除操作的時(shí)間復(fù)雜度就是O(n)，而雙鏈表的時(shí)間復(fù)雜度就是O(1)歌焦。

插入操作同理飞几，大家可以自己思考一下。

除了插入独撇、刪除操作有優(yōu)勢(shì)之外,對(duì)于一個(gè)有序鏈表,雙向鏈表的按值查詢(xún)的效率也要比單鏈表高一些屑墨。因?yàn)椋覀兛梢杂涗浬洗尾檎业奈恢胮 ,每次查詢(xún)時(shí),根據(jù)要查找的值與p的大小關(guān)系纷铣，決定是往前還是往后查找,所以平均只需要查找一半的數(shù)據(jù)卵史。

現(xiàn)在,是不是覺(jué)得雙向鏈表要比單鏈表更加高效呢?這就是為什么在實(shí)際的軟件開(kāi)發(fā)中,雙向鏈表盡管比較費(fèi)內(nèi)存,但還是比單鏈表的應(yīng)用更加廣泛的原因。如果熟悉Java語(yǔ)言,肯定用過(guò)LinkedHashMap這個(gè)容器关炼。如果深入研究LinkedHashMap的實(shí)現(xiàn)原理,就會(huì)發(fā)現(xiàn)其中就用到了雙向鏈表這種數(shù)據(jù)結(jié)構(gòu)程腹。

實(shí)際上,這里有一個(gè)更加重要的知識(shí)點(diǎn)需要你掌握,那就是用空間換時(shí)間的設(shè)計(jì)思想。當(dāng)內(nèi)存空間充足的時(shí)候,如果我們更加追求代碼的執(zhí)行速度,我們就可以選擇空間復(fù)雜度相對(duì)較高儒拂、但時(shí)間復(fù)雜度相對(duì)很低的算法或者數(shù)據(jù)結(jié)構(gòu)寸潦。相反,如果內(nèi)存比較緊缺,比如代碼跑在手機(jī)或者單片機(jī)上社痛，這個(gè)時(shí)候,就要反過(guò)來(lái)用時(shí)間換空間的設(shè)計(jì)思路见转。

總結(jié)：對(duì)于執(zhí)行慢的程序，可以通過(guò)消耗更多的內(nèi)存(空間換時(shí)間)來(lái)進(jìn)行優(yōu)化蒜哀；而消耗過(guò)多內(nèi)存的程序斩箫，可以通過(guò)消耗更多的時(shí)間(時(shí)間換空間)來(lái)降低內(nèi)存的消耗。

雙向循環(huán)鏈表

雙向循環(huán)鏈表：就是將雙向鏈表和循環(huán)鏈表結(jié)合到一起

雙向循環(huán)鏈表.png

鏈表VS數(shù)組性能大比拼

通過(guò)全面的學(xué)習(xí)撵儿，我們知道了數(shù)組和鏈表是兩種截然不同的內(nèi)存組織方式乘客。正式因?yàn)檫@樣內(nèi)存存儲(chǔ)的區(qū)別，它們插入淀歇、刪除易核、隨機(jī)訪問(wèn)操作的時(shí)間復(fù)雜度恰好相反。

image.png

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

數(shù)組簡(jiǎn)單易用,在實(shí)現(xiàn)上使用的是連續(xù)的內(nèi)存空間,可以借助CPU的緩存機(jī)制，預(yù)讀數(shù)組中的數(shù)據(jù)纳决，所以訪問(wèn)效率更高碰逸。而鏈表在內(nèi)存中并不是連續(xù)存儲(chǔ),所以對(duì)CPU緩存不友好,沒(méi)辦法有效預(yù)讀。

數(shù)組的缺點(diǎn)是大小固定,一經(jīng)聲明就要占用整塊連續(xù)內(nèi)存空間阔加。如果聲明的數(shù)組過(guò)大,系統(tǒng)可能沒(méi)有足夠的連續(xù)內(nèi)存空間分配給它,導(dǎo)致"內(nèi)存不足( out of memory)"饵史。如果聲明的數(shù)組過(guò)小,則可能出現(xiàn)不夠用的情況。這時(shí)只能再申請(qǐng)一個(gè)更大的內(nèi)存空間 ,把原數(shù)組拷貝進(jìn)去,非常費(fèi)時(shí)胜榔。鏈表本身沒(méi)有大小的限制,天然地支持動(dòng)態(tài)擴(kuò)容,我覺(jué)得這也是它與數(shù)組最大的區(qū)別约急。

你可能會(huì)說(shuō),我們Java中的ArrayList容器,也可以支持動(dòng)態(tài)擴(kuò)容啊?我們上一節(jié)課講過(guò),當(dāng)我們往支持動(dòng)態(tài)擴(kuò)容的數(shù)組中插入一個(gè)數(shù)據(jù)時(shí),如果數(shù)組中沒(méi)有空閑空間了,就會(huì)申請(qǐng)一個(gè)更大的空間，將數(shù)據(jù)拷貝過(guò)去,而數(shù)據(jù)拷貝的操作是非常耗時(shí)的苗分。

我舉一個(gè)稍微極端的例子厌蔽。如果我們用ArrayList存儲(chǔ)了了1GB大小的數(shù)據(jù), 這個(gè)時(shí)候已經(jīng)沒(méi)有空閑空間了,當(dāng)我們?cè)俨迦霐?shù)據(jù)的時(shí)候, ArrayList 會(huì)申請(qǐng)一個(gè)1.5GB大小的存儲(chǔ)空間,并且把原來(lái)那1GB的數(shù)據(jù)拷貝到新申請(qǐng)的空間上。聽(tīng)起來(lái)是不是就很耗時(shí)?

除此之外,如果你的代碼對(duì)內(nèi)存的使用非乘ぱⅲ苛刻,那數(shù)組就更適合你奴饮。因?yàn)殒湵碇械拿總€(gè)結(jié)點(diǎn)都需要消耗額外的存儲(chǔ)空間去存儲(chǔ)一份指向下一 個(gè)結(jié)點(diǎn)的指針,所以?xún)?nèi)存消耗會(huì)翻倍。而且, 對(duì)鏈表進(jìn)行頻繁的插入择浊、刪除操作,還會(huì)導(dǎo)致頻繁的內(nèi)存申請(qǐng)和釋放,容易造成內(nèi)存碎片,如果是Java語(yǔ)言,就有可能會(huì) 導(dǎo)致頻繁的GC ( Garbage Collection ,垃圾回收)戴卜。

所以，在我們實(shí)際的開(kāi)發(fā)中,針對(duì)不同類(lèi)型的項(xiàng)目,要根據(jù)具體情況,權(quán)衡究竟是選擇數(shù)組還是鏈表琢岩。

解笞開(kāi)篇投剥，如何基于鏈表實(shí)現(xiàn)LRU緩存淘汰算法?

我的思路是這樣的:我們維護(hù)一個(gè)有序單鏈表,越靠近鏈表尾部的結(jié)點(diǎn)是越早之前訪問(wèn)的。當(dāng)有一個(gè) 新的數(shù)據(jù)被訪問(wèn)時(shí),我們從鏈表頭開(kāi)始順序遍歷鏈表担孔。

1.如果此數(shù)據(jù)之前已經(jīng)被緩存在鏈表中了,我們遍歷得到這個(gè)數(shù)據(jù)對(duì)應(yīng)的結(jié)點(diǎn),并將其從原來(lái)的位置刪除, 然后再插入到鏈表的頭部江锨。

2.如果此數(shù)據(jù)沒(méi)有在緩存鏈表中,又可以分為兩種情況:

• 如果此時(shí)緩存未滿(mǎn),則將此結(jié)點(diǎn)直接插入到鏈表的頭部;
• 如果此時(shí)緩存已滿(mǎn),則鏈表尾結(jié)點(diǎn)刪除,將新的數(shù)據(jù)結(jié)點(diǎn)插入鏈表的頭部吃警。

這樣我們就用鏈表實(shí)現(xiàn)了一個(gè)LRU緩存,是不是很簡(jiǎn)單?
現(xiàn)在我們來(lái)看下m緩存訪問(wèn)的時(shí)間復(fù)雜度是多少。因?yàn)椴还芫彺嬗袥](méi)有滿(mǎn),我們都需要遍歷一遍鏈表,所以這種基于鏈表的實(shí)現(xiàn)思路,緩存訪問(wèn)的時(shí)間復(fù)雜度為O(n)啄育。

實(shí)際上,我們可以繼續(xù)優(yōu)化這個(gè)實(shí)現(xiàn)思路,比如引入散列表( Hash table )來(lái)記錄每個(gè)數(shù)據(jù)的位置,將緩存訪問(wèn)的時(shí)間復(fù)雜度降到0(1)酌心。涉及到的數(shù)據(jù)結(jié)構(gòu)散列表,在后面的文章會(huì)有所解析。

知識(shí)延伸挑豌，如何基于數(shù)組實(shí)現(xiàn)LRU緩存淘汰策略安券？

方式一：首位置保存最新訪問(wèn)數(shù)據(jù)，末尾位置優(yōu)先清理
當(dāng)訪問(wèn)的數(shù)據(jù)未存在于緩存的數(shù)組中時(shí)氓英，直接將數(shù)據(jù)插入數(shù)組第一個(gè)元素位置侯勉，此時(shí)數(shù)組所有元素需要向后移動(dòng)1個(gè)位置，時(shí)間復(fù)雜度為O(n)铝阐；當(dāng)訪問(wèn)的數(shù)據(jù)存在于緩存的數(shù)組中時(shí)址貌，查找到數(shù)據(jù)并將其插入數(shù)組的第一個(gè)位置，此時(shí)亦需移動(dòng)數(shù)組元素饰迹，時(shí)間復(fù)雜度為O(n)芳誓。緩存用滿(mǎn)時(shí)，則清理掉末尾的數(shù)據(jù)啊鸭，時(shí)間復(fù)雜度為O(1)锹淌。

方式二：首位置優(yōu)先清理，末尾位置保存最新訪問(wèn)數(shù)據(jù)
當(dāng)訪問(wèn)的數(shù)據(jù)未存在于緩存的數(shù)組中時(shí)赠制，直接將數(shù)據(jù)添加進(jìn)數(shù)組作為當(dāng)前最后一個(gè)元素時(shí)間復(fù)雜度為O(1)赂摆；當(dāng)訪問(wèn)的數(shù)據(jù)存在于緩存的數(shù)組中時(shí)，查找到數(shù)據(jù)并將其插入當(dāng)前數(shù)組最后一個(gè)元素的位置钟些，此時(shí)亦需移動(dòng)數(shù)組元素烟号，時(shí)間復(fù)雜度為O(n)。緩存用滿(mǎn)時(shí)政恍，則清理掉數(shù)組首位置的元素汪拥，且剩余數(shù)組元素需整體前移一位，時(shí)間復(fù)雜度為O(n)篙耗。（優(yōu)化：清理的時(shí)候可以考慮一次性清理一定數(shù)量迫筑，從而降低清理次數(shù)，提高性能宗弯。）

知識(shí)拓展：
“數(shù)組簡(jiǎn)單易用脯燃，在實(shí)現(xiàn)上使用的是連續(xù)的內(nèi)存空間，可以借助 CPU 的緩存機(jī)制蒙保，預(yù)讀數(shù)組中的數(shù)據(jù)辕棚，所以訪問(wèn)效率更高。而鏈表在內(nèi)存中并不是連續(xù)存儲(chǔ)，所以對(duì) CPU 緩存不友好逝嚎，沒(méi)辦法有效預(yù)讀扁瓢。” 這里的CPU緩存機(jī)制指的是什么懈糯？為什么就數(shù)組更好了涤妒？
CPU在從內(nèi)存讀取數(shù)據(jù)的時(shí)候单雾，會(huì)先把讀取到的數(shù)據(jù)加載到CPU的緩存中赚哗。而CPU每次從內(nèi)存讀取數(shù)據(jù)并不是只讀取那個(gè)特定要訪問(wèn)的地址，而是讀取一個(gè)數(shù)據(jù)塊(這個(gè)大小我不太確定硅堆。屿储。)并保存到CPU緩存中，然后下次訪問(wèn)內(nèi)存數(shù)據(jù)的時(shí)候就會(huì)先從CPU緩存開(kāi)始查找渐逃，如果找到就不需要再?gòu)膬?nèi)存中取够掠。這樣就實(shí)現(xiàn)了比內(nèi)存訪問(wèn)速度更快的機(jī)制，也就是CPU緩存存在的意義:為了彌補(bǔ)內(nèi)存訪問(wèn)速度過(guò)慢與CPU執(zhí)行速度快之間的差異而引入茄菊。
對(duì)于數(shù)組來(lái)說(shuō)疯潭，存儲(chǔ)空間是連續(xù)的，所以在加載某個(gè)下標(biāo)的時(shí)候可以把以后的幾個(gè)下標(biāo)元素也加載到CPU緩存這樣執(zhí)行速度會(huì)快于存儲(chǔ)空間不連續(xù)的鏈表存儲(chǔ)面殖。

HashMap采用Entry數(shù)組來(lái)存儲(chǔ)key-value對(duì)竖哩，每一個(gè)鍵值對(duì)組成了一個(gè)Entry實(shí)體，Entry類(lèi)實(shí)際上是一個(gè)單向的鏈表結(jié)構(gòu)脊僚，它具有Next指針相叁，可以連接下一個(gè)Entry實(shí)體，依次來(lái)解決Hash沖突的問(wèn)題辽幌，因?yàn)镠ashMap是按照Key的hash值來(lái)計(jì)算Entry在HashMap中存儲(chǔ)的位置的增淹，如果hash值相同，而key內(nèi)容不相等乌企，那么就用鏈表來(lái)解決這種hash沖突虑润。
【HashMap是單鏈表結(jié)構(gòu)】

LinkedHashMap繼承了HashMap，比其多了兩個(gè)屬性head 和tail加酵，加了一種鏈表的數(shù)據(jù)拳喻。LinkedHashMap其實(shí)沒(méi)有重寫(xiě)HashMap的put方法，它并有放棄HashMap的散列鏈表虽画，只是在這個(gè)基礎(chǔ)上加上了自己的鏈表舞蔽。 來(lái)看HashMap的源碼，put方法調(diào)用了newNode方法码撰，LinkedHashMap只需要重寫(xiě)此方法就可以在put時(shí)把元素也放在自己的鏈表中渗柿，新節(jié)點(diǎn)變成尾節(jié)點(diǎn)
【LinkedHashMap是雙鏈表結(jié)構(gòu)】