欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

源碼解析帶你了解LinkedHashMap

 更新時間：2021年09月15日 09:36:41   作者：JavaEdge.  
大多數(shù)情況下，只要不涉及線程安全問題，Map基本都可以使用HashMap，不過HashMap有一個問題，就是迭代HashMap的順序并不是HashMap放置的順序，也就是無序。HashMap的這一缺點往往會帶來困擾，所以LinkedHashMap就閃亮登場了，這篇文章通過源碼解析帶你了解LinkedHashMap

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

元素存儲關(guān)系

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

繼承體系

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

5088755_1577812744625_DA615EAF7757A05A68BDC4C9093BBBD8

屬性

  • 雙向鏈表的頭（最老）

  • 雙鏈表的末尾（最小）

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

此 LinkedHashMap 的迭代排序方法：

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

構(gòu)造方法

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

無參

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

有參

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

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

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

按插入順序訪問

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

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

newNode

  • HashMap

  • LinkedHashMap 重寫

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

linkNodeLast

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

`// link at the end of list`

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

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

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

`tail = p;`

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

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

`head = p;`

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

`else` `{`

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

`p.before = last;`

`last.after = p;`

`}`

`}`

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

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

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

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

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

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

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

鏈表節(jié)點的刪除

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

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

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

`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é)點的前驅(qū)后后繼引用置 null,輔助 GC`

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

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

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

`head = a;`

`else`

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

`b.after = a;`

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

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

`tail = b;`

`else`

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

`a.before = b;`

`}`

刪除元素的主要流程:

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

5088755_1583897219283_48356470140921DD4FA1E2C40982DE97

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

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

栗子

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

元素被移到隊尾

get 時，元素會被移動到隊尾：

`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)`

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

`afterNodeAccess(e);`

`return` `e.value;`

`}`

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

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

相關(guān)文章

最新評論