LinkedHashMap維護(hù)插入的順序。

元素存儲關(guān)系

紅黃箭頭:元素添加順序
藍(lán)箭頭:單鏈表各個(gè)元素的存儲順序
head:鏈表頭部
tail:鏈表尾部

繼承體系

• 繼承自 HashMap ，因此 HashMap 擁有的榮耀它也都有.
  

屬性

• 雙向鏈表的頭（最老）
  

• 雙鏈表的末尾（最小）
  

• HashMap.Node的子類:常規(guī) LinkedHashMap 節(jié)點(diǎn),增加了 before 和 after 屬性,維護(hù)雙向鏈表的結(jié)構(gòu)
  

此 LinkedHashMap 的迭代排序方法：

• true: 訪問順序
• false(默認(rèn)): 插入順序

構(gòu)造方法

構(gòu)造方法都是先執(zhí)行父類 HashMap 的構(gòu)造方法.

無參

• 構(gòu)造一個(gè)空的維護(hù)插入順序的LinkedHashMap實(shí)例，其默認(rèn)初始容量（16）和負(fù)載因子（0.75）.
  

有參

• 構(gòu)造一個(gè)空的LinkedHashMap實(shí)例，可自己指定初始容量，負(fù)載因子和排序模式.
  

• 構(gòu)造一個(gè)維護(hù)插入順序的LinkedHashMap實(shí)例，該實(shí)例具有與指定map相同的映射關(guān)系,創(chuàng)建的LinkedHashMap實(shí)例具有默認(rèn)的加載因子（0.75）和足以容納指定map中映射的初始容量.
  

下面我們開始研究該類的主要特性是如何通過代碼實(shí)現(xiàn)的.

按插入順序訪問

LinkedHashMap 默認(rèn) accessOrder 為 false，提供按照插入順序的訪問，并沒有重寫父類 HashMap 的 put 方法.但在 HashMap 中，put 的是 HashMap 的 Node 類型節(jié)點(diǎn)，LinkedHashMap 的 Entry 與其結(jié)構(gòu)并不同,又是怎樣建立起雙向鏈表的呢？下面一起看下 LinkedHashMap 插入相關(guān)代碼.

忽略未重寫的 put=>putValue代碼部分,我們直接觀察重寫的

newNode

• HashMap
  

• LinkedHashMap 重寫
  

控制新增節(jié)點(diǎn)追加到鏈表的尾部，這樣每次新節(jié)點(diǎn)都追加到尾部，即可保證插入順序了.
繼續(xù)研究 linkNodeLast

linkNodeLast

新增節(jié)點(diǎn)，并追加到鏈表的尾部.

`// link at the end of list`

`private` `void` `linkNodeLast(LinkedHashMap.Entry<K,V> p) {`

`LinkedHashMap.Entry<K,V> last = tail;`

`// 新增于尾節(jié)點(diǎn)`

`tail = p;`

`// last 為null，說明鏈表為空`

`if` `(last == ``null``)`

`head = p;`

`// 鏈表非空，建立新節(jié)點(diǎn)和上一個(gè)尾節(jié)點(diǎn)的前后關(guān)系`

`else` `{`

`// 將新節(jié)點(diǎn) p 直接接在鏈尾`

`p.before = last;`

`last.after = p;`

`}`

`}`

由此得知,通過在 HashMap 基礎(chǔ)上新增的頭尾節(jié)點(diǎn)，節(jié)點(diǎn)的 before 和 after 屬性，就能實(shí)現(xiàn)在每次新增時(shí)，把節(jié)點(diǎn)直接追加到尾節(jié)點(diǎn)，即可達(dá)到維護(hù)按照插入順序的鏈表結(jié)構(gòu)的目的!

• 圖解鏈表創(chuàng)建步驟
  

藍(lán)色部分是 HashMap 的方法
橙色部分為 LinkedHashMap 獨(dú)有方法

注意 LinkedHashMap 雖然也是雙向鏈表,但只提供單向的按插入的順序從頭到尾訪問，不及 LinkedList 般可雙向無死角訪問.

• LinkedHashMap 通過迭代器訪問，而且默認(rèn)是從頭節(jié)點(diǎn)開始訪問
  

迭代過程中，不斷訪問 after 節(jié)點(diǎn)即可完成遍歷.

1 處進(jìn)行校驗(yàn)
2 處通過節(jié)點(diǎn)的 after 屬性，找到后繼節(jié)點(diǎn)

鏈表節(jié)點(diǎn)的刪除

• HashMap 中保存的允許 LinkedHashMap 后處理的回調(diào)
  

與插入操作一樣，LinkedHashMap 刪除操作相關(guān)的代碼也是直接用父類的實(shí)現(xiàn). 在刪除節(jié)點(diǎn)時(shí)，父類不會修復(fù) LinkedHashMap 的雙向鏈表。那么刪除及節(jié)點(diǎn)后，被刪除的節(jié)點(diǎn)該如何從雙鏈表中安全移除呢？其實(shí)在刪除節(jié)點(diǎn)后，回調(diào)方法 afterNodeRemoval 會被調(diào)用。LinkedHashMap 重寫了該方法.

`// e 為已經(jīng)刪除的節(jié)點(diǎn)`

`void` `afterNodeRemoval(Node<K,V> e) { ``// unlink`

`LinkedHashMap.Entry<K,V> p =`

`(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;`

`// 將 p 節(jié)點(diǎn)的前驅(qū)后后繼引用置 null,輔助 GC`

`p.before = p.after = ``null``;`

`// p.before 為 null，表明 p 是頭節(jié)點(diǎn)`

`if` `(b == ``null``)`

`head = a;`

`else`

`// 否則將 p 的前驅(qū)節(jié)點(diǎn)連接到 p 的后繼節(jié)點(diǎn)`

`b.after = a;`

`// a 為 null，表明 p 是尾節(jié)點(diǎn)`

`if` `(a == ``null``)`

`tail = b;`

`else`

`// 否則將 a 的前驅(qū)節(jié)點(diǎn)連接到 b`

`a.before = b;`

`}`

刪除元素的主要流程:

• 根據(jù) hash 定位到桶位置
• 遍歷鏈表或調(diào)用紅黑樹相關(guān)的刪除方法
• 從 LinkedHashMap 維護(hù)的雙鏈表中移除要?jiǎng)h除的節(jié)點(diǎn)
  

轉(zhuǎn)存失敗重新上傳取消

LRU（Least recently used,最近最少使用）

栗子

經(jīng)常訪問的元素會被追加到隊(duì)尾，這樣不經(jīng)常訪問的數(shù)據(jù)自然就靠近隊(duì)頭，然后可以通過設(shè)置刪除策略，比如當(dāng) Map 元素個(gè)數(shù)大于多少時(shí)，把頭節(jié)點(diǎn)刪除

元素被移到隊(duì)尾

get 時(shí)，元素會被移動(dòng)到隊(duì)尾：

`public` `V get(Object key) {`

`Node<K,V> e;`

`// 調(diào)用 HashMap  get 方法`

`if` `((e = getNode(hash(key), key)) == ``null``)`

`return` `null``;`

`// 如果設(shè)置了 LRU 策略`

`if` `(accessOrder)`

`// 這個(gè)方法把當(dāng)前 key 移動(dòng)到隊(duì)尾`

`afterNodeAccess(e);`

`return` `e.value;`

`}`

從上述源碼中，可以看到，通過 afterNodeAccess 方法把當(dāng)前訪問節(jié)點(diǎn)移動(dòng)到了隊(duì)尾，其實(shí)不僅僅是 get 方法，執(zhí)行 getOrDefault、compute、computeIfAbsent、computeIfPresent、merge 方法時(shí)，也會這么做，通過不斷的把經(jīng)常訪問的節(jié)點(diǎn)移動(dòng)到隊(duì)尾，那么靠近隊(duì)頭的節(jié)點(diǎn)，自然就是很少被訪問的元素了。

到此這篇關(guān)于源碼解析帶你了解LinkedHashMap的文章就介紹到這了,更多相關(guān)Java LinkedHashMap內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論