源碼解析帶你了解LinkedHashMap
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í),元素會被移動到隊(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)文章
Java實(shí)現(xiàn)查找當(dāng)前字符串最大回文串代碼分享
本文給大家介紹的是如何使用Java實(shí)現(xiàn)查找當(dāng)前字符串最大回文串代碼,非常的簡單實(shí)用,有需要的小伙伴可以參考下2016-07-07Java多線程并發(fā)編程 Synchronized關(guān)鍵字
現(xiàn)有一成員變量 Test,當(dāng)線程 A 調(diào)用 Test 的 synchronized 方法,線程 A 獲得 Test 的同步鎖,同時(shí),線程 B 也去調(diào)用 Test 的 synchronized 方法,此時(shí)線程 B 無法獲得 Test 的同步鎖,必須等待線程 A 釋放 Test 的同步鎖才能獲得從而執(zhí)行對應(yīng)方法的代碼2017-05-05關(guān)于文件上傳MultipartBody的使用方法
這篇文章主要介紹了關(guān)于文件上傳MultipartBody的使用方法,具有很好的參考價(jià)值,希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-06-06SpringCloud:feign對象傳參和普通傳參及遇到的坑解決
這篇文章主要介紹了SpringCloud:feign對象傳參和普通傳參及遇到的坑解決,具有很好的參考價(jià)值,希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-03-03Windows下Java調(diào)用可執(zhí)行文件代碼實(shí)例
這篇文章主要介紹了Windows下Java調(diào)用可執(zhí)行文件代碼實(shí)例,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-12-12IntelliJ IDEA語法報(bào)錯(cuò)"Usage of API documented as @since 1.6+"的解決
今天小編就為大家分享一篇關(guān)于IntelliJ IDEA語法報(bào)錯(cuò)"Usage of API documented as @since 1.6+"的解決辦法,小編覺得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來看看吧2018-10-10SpringBoot+Jpa項(xiàng)目配置雙數(shù)據(jù)源的實(shí)現(xiàn)
本文主要介紹了SpringBoot+Jpa項(xiàng)目配置雙數(shù)據(jù)庫源的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-12-12Mybatis中and和循環(huán)or混用操作(or轉(zhuǎn)換成in)
這篇文章主要介紹了Mybatis中and和循環(huán)or混用操作(or轉(zhuǎn)換成in),具有很好的參考價(jià)值,希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-07-07