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

源碼解析帶你了解LinkedHashMap

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

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

元素存儲關(guān)系

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

繼承體系

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

5088755_1577812744625_DA615EAF7757A05A68BDC4C9093BBBD8

屬性

  • 雙向鏈表的頭(最老)

  • 雙鏈表的末尾(最小)

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

5088755_1583897219283_48356470140921DD4FA1E2C40982DE97

轉(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í),元素會被移動到隊(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 移動到隊(duì)尾`

`afterNodeAccess(e);`

`return` `e.value;`

`}`

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

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

相關(guān)文章

最新評論