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