LinkedHashMap分析

這篇文章會分析一下 LinkedHashMap。

?

LinkedHashMap是啥

首先我們看一下這個類的定義：

1 public class LinkedHashMap<K,V> 2 extends HashMap<K,V> 3 implements Map<K,V>

可以看到LinkedHashMap同樣實現(xiàn)了Map接口，但它同時還繼承了HashMap，所以天然就有HashMap自身的特性。

?

從名字上看? LinkedHashMap 比 HashMap 多了前面的“ Linked “, 那它們之間的區(qū)別在哪里呢？我們再看一段代碼：

1 /** 2 * LinkedHashMap的Entry對象，除了繼承于HashMap Node的4個屬性，額外添加了兩個屬性before,after用于維護雙向鏈表的前后結(jié)點關(guān)系 3 */ 4 static class Entry<K,V> extends HashMap.Node<K,V> { 5 Entry<K,V> before, after; 6 Entry(int hash, K key, V value, Node<K,V> next) { 7 super(hash, key, value, next); 8 } 9 }

從這里可以看到相比較于HashMap的Node，除了繼承自HashMap Node數(shù)據(jù)結(jié)構(gòu)中的hash、key、value、next四個屬性之外，LinkedHashMap的Node還多維護了兩個屬性：before，after。

這兩個屬性是用于維護一條獨立的雙向鏈表，而這個雙向鏈表中保存的僅僅是在LinkedHashMap中節(jié)點與節(jié)點的前后關(guān)系。

所以可以這么認為：LinkedHashMap是 "維護了節(jié)點之間前后順序的HashMap" 。

?

其他用到的屬性：

1 /** 2 * 雙向鏈表的頭結(jié)點（最近最少使用的結(jié)點） 3 */ 4 transient LinkedHashMap.Entry<K,V> head; 5 6 /** 7 * 雙向鏈表的尾結(jié)點(最近最多使用的結(jié)點) 8 */ 9 transient LinkedHashMap.Entry<K,V> tail; 10 11 /** 12 * LinkedHashMap核心屬性，該屬性定義了雙向鏈表中存儲結(jié)點的順序: 13 * 如果為true，則雙向鏈表按照結(jié)點的訪問順序維護前后結(jié)點關(guān)系(訪問、操作結(jié)點都會影響該結(jié)點在雙向鏈表的位置),這種方式實現(xiàn)了LRU算法 14 * 如果為false，則雙向鏈表僅僅按照結(jié)點的插入順序維護前后結(jié)點關(guān)系(只有操作結(jié)點的動作才會影響該結(jié)點在雙向鏈表的位置) 15 * 該值默認為false. 16 */ 17 final boolean accessOrder;

這里需要著重注意第17行的accessOrder這個變量，LinkedHashMap通過在構(gòu)造方法中傳入該參數(shù)的值(true/false)來控制雙向鏈表中維護節(jié)點的前后順序時是根據(jù)訪問順序維護還是插入順序維護。解釋一下這兩種順序有啥區(qū)別：

?假設(shè)一開始往Map中添加了3個節(jié)點? A、B、C，則此時雙向鏈表中維護節(jié)點的前后順序應該是? ?A -> B -> C,此時調(diào)用HashMap的get(key)方法訪問B節(jié)點：

如果 accessOrder = true, 那么按照訪問節(jié)點維護雙向鏈表中節(jié)點前后順序，此時節(jié)點的前后順序關(guān)系變更為? ?A -> C -> B；

如果accessOrder = false,那么節(jié)點的前后順序關(guān)系不變，依舊為?A -> B -> C。

當然，如果是插入、刪除節(jié)點，無論accessOrder設(shè)置為何值，雙向鏈表中節(jié)點的前后順序關(guān)系都會發(fā)生改變。比如在Map插入一個節(jié)點D

那么無論accessOrder為true還是false，雙向鏈表中節(jié)點的前后順序關(guān)系都會變更為? A -> B -> C -> D。

?

?

LinkedHashMap核心源碼分析(JDK Version 1.8)

?

1.構(gòu)造方法?

1 /** 2 * 帶capacity和loadFactor的構(gòu)造函數(shù) 3 * 4 * @param initialCapacity 自定義初始容量 5 * @param loadFactor 自定義負載因子 6 * @throws IllegalArgumentException 初始容量或負載因子為負數(shù)，拋出異常 7 * 8 */ 9 public LinkedHashMap(int initialCapacity, float loadFactor) { 10 super(initialCapacity, loadFactor); //調(diào)用HashMap的構(gòu)造函數(shù) 11 accessOrder = false; 12 } 13 14 /** 15 * 只帶capacity參數(shù)的構(gòu)造函數(shù)，此時loadFactor為默認的0.75 16 * 17 * @param initialCapacity 自定義初始容量 18 * @throws IllegalArgumentException 初始容量為負數(shù)，拋出異常 19 */ 20 public LinkedHashMap(int initialCapacity) { 21 super(initialCapacity); //調(diào)用HashMap的構(gòu)造函數(shù) 22 accessOrder = false; 23 } 24 25 /** 26 * 無參數(shù)構(gòu)造函數(shù)。初始容量為默認的16，負載因子為默認的0.75 27 */ 28 public LinkedHashMap() { 29 super(); //調(diào)用HashMap的構(gòu)造函數(shù) 30 accessOrder = false; 31 } 32 33 34 /** 35 * 三個參數(shù)的構(gòu)造函數(shù)，可以控制雙向鏈表的存儲方式 36 * 37 * @param initialCapacity 初始容量 38 * @param loadFactor 負載因子 39 * @param accessOrder 雙向鏈表維護的存儲順序 40 * @throws IllegalArgumentException 初始容量或負載因子為負數(shù)，拋出異常 41 */ 42 public LinkedHashMap(int initialCapacity, 43 float loadFactor, 44 boolean accessOrder) { 45 super(initialCapacity, loadFactor); //調(diào)用HashMap的構(gòu)造方法 46 this.accessOrder = accessOrder; 47 }

2.LinkedHashMap在訪問和操作節(jié)點時特有的方法

1 /** 2 * LinkedHashMap重寫了HashMap的newNode()方法 3 * 該方法在HashMap的putVal()方法中判斷需要新增結(jié)點時會被調(diào)用 4 * @param hash 5 * @param key 6 * @param value 7 * @param e 8 * @return 9 */ 10 Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { 11 LinkedHashMap.Entry<K,V> p = 12 new LinkedHashMap.Entry<K,V>(hash, key, value, e); //新增一個key-value的結(jié)點 13 linkNodeLast(p); //LinkedHashMap生成新結(jié)點時除了新增一個結(jié)點外，還將該結(jié)點在雙向鏈表中的位置移動到尾部，這個操作默認按元素插入順序維護了鏈表前后結(jié)點關(guān)系 14 return p; 15 } 16 17 18 /** 19 * 將結(jié)點在雙向鏈表中的位置移動到尾部 20 * @param p 21 */ 22 private void linkNodeLast(LinkedHashMap.Entry<K,V> p) { 23 LinkedHashMap.Entry<K,V> last = tail; //將當前雙向鏈表的尾結(jié)點保存下來 24 tail = p; //尾結(jié)點設(shè)置為傳入的結(jié)點 25 if (last == null) //如果之前鏈表中沒有結(jié)點，即這次新增的結(jié)點是鏈表的頭結(jié)點 26 head = p; 27 else { //如果這次新增的結(jié)點不是鏈表的頭結(jié)點，則將其移動到鏈表的尾部 28 p.before = last; //當前結(jié)點的前驅(qū)指向之前鏈表的尾結(jié)點 29 last.after = p; //之前鏈表尾結(jié)點后驅(qū)指向當前結(jié)點 30 } 31 } 32 33 34 /** 35 * 某個結(jié)點被刪除后的回調(diào)方法 36 * LinkedHashMap在維護的雙向鏈表中也要把該結(jié)點與前后結(jié)點的關(guān)系移除 37 * @param e 38 */ 39 void afterNodeRemoval(Node<K,V> e) { // unlink 40 LinkedHashMap.Entry<K,V> p = 41 (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; 42 p.before = p.after = null; //移除被刪除結(jié)點和前后結(jié)點之前的引用關(guān)系 43 if (b == null) //如果雙向鏈表中被移除的結(jié)點就是首結(jié)點 44 head = a; //將下一個結(jié)點變?yōu)槭捉Y(jié)點 45 else 46 b.after = a; //否則就把被刪除結(jié)點的前一個結(jié)點的后驅(qū)指向被刪除結(jié)點的后一個結(jié)點 47 if (a == null) //如果雙向鏈表中被移除的結(jié)點就是尾結(jié)點 48 tail = b; //將上一個結(jié)點變?yōu)槲步Y(jié)點 49 else 50 a.before = b; //否則就把被刪除結(jié)點的后一個結(jié)點的前驅(qū)指向被刪除結(jié)點的前一個結(jié)點 51 } 52 53 54 /** 55 * 某個結(jié)點被訪問后的回調(diào)方法 56 * 如果在創(chuàng)建LinkedHashMap時構(gòu)造方法中的accessOrder設(shè)置為true 57 * 則雙向鏈表需要按照元素訪問的順序維護雙向鏈表中結(jié)點的前后引用關(guān)系以實現(xiàn)LRU算法 58 * 在每次get/put結(jié)點后，都需要調(diào)用這個回調(diào)方法，將結(jié)點在雙向鏈表中的位置移動到尾部(因為最近這個結(jié)點被訪問了) 59 * @param e 60 */ 61 void afterNodeAccess(Node<K,V> e) { // move node to last 62 LinkedHashMap.Entry<K,V> last; 63 if (accessOrder && (last = tail) != e) { //如果指定accessOrder為true并且當前訪問的結(jié)點在雙向鏈表中不是尾結(jié)點才繼續(xù)做如下操作 64 LinkedHashMap.Entry<K,V> p = 65 (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; 66 p.after = null; //將當前被訪問結(jié)點在雙向鏈表中的后驅(qū)引用設(shè)置為null 67 if (b == null) //如果原先被訪問結(jié)點的前驅(qū)引用為null，說明這個被訪問結(jié)點原先就是雙向鏈表的頭結(jié)點 68 head = a; //將頭結(jié)點變更為被訪問結(jié)點的后一個結(jié)點 69 else 70 b.after = a; //否則將被訪問結(jié)點的前一個結(jié)點的后驅(qū)指向被訪問結(jié)點的后一個結(jié)點 71 if (a != null) //如果原先被訪問結(jié)點在雙向鏈表中有下一個結(jié)點 72 a.before = b; //那么將下一個結(jié)點的前驅(qū)引用指向被訪問結(jié)點的前一個結(jié)點 73 else 74 last = b; //否則將尾結(jié)點引用指向設(shè)置為當前被訪問結(jié)點的前一個結(jié)點 75 if (last == null) //如果原先雙向鏈表中沒有尾結(jié)點，則說明此次訪問的結(jié)點是該雙向鏈表中第一個結(jié)點 76 head = p; //將雙向頭結(jié)點設(shè)置為此次被訪問的結(jié)點 77 else { //將被訪問的結(jié)點移動到雙向鏈表的尾部 78 p.before = last; //否則將當前結(jié)點的前驅(qū)引用指向原來雙向鏈表的尾結(jié)點 79 last.after = p; //再將原先雙向鏈表尾結(jié)點的后驅(qū)引用指向當前被訪問的結(jié)點 80 } 81 tail = p; //雙向鏈表尾結(jié)點變更為當前被訪問的結(jié)點 82 ++modCount; 83 } 84 }

因為LinkedHashMap維護了雙向鏈表，所以相比HashMap在訪問、插入、刪除節(jié)點時都要額外再對雙向鏈表中維護的節(jié)點前后關(guān)系進行操作。

結(jié)合注釋看應該很好理解，就不再啰嗦了。

?

LinkedHashMap的LRU特性

先講一下LRU的定義：LRU(Least Recently Used),即最近最少使用算法，最初是用于內(nèi)存管理中將無效的內(nèi)存塊騰出而用于加載數(shù)據(jù)以提高內(nèi)存使用效率而發(fā)明的算法。

目前已經(jīng)普遍用于提高緩存的命中率，如Redis、Memcached中都有使用。

為啥說LinkedHashMap本身就實現(xiàn)了LRU算法？原因就在于它額外維護的雙向鏈表中。

在上面已經(jīng)提到過，在做get/put操作時，LinkedHashMap會將當前訪問/插入的節(jié)點移動到鏈表尾部，所以此時鏈表頭部的那個節(jié)點就是 "最近最少未被訪問"的節(jié)點。

舉個例子：

往一個空的LinkedHashMap中插入A、B、C三個結(jié)點，那么鏈表會經(jīng)歷以下三個狀態(tài)：

1.? A? ?插入A節(jié)點，此時整個鏈表只有這一個節(jié)點，既是頭節(jié)點也是尾節(jié)點

2.? A? ->? B? ?插入B節(jié)點后，此時A為頭節(jié)點，B為尾節(jié)點，而最近最常訪問的節(jié)點就是B節(jié)點（剛被插入），而最近最少使用的節(jié)點就是A節(jié)點（相對B節(jié)點來講，A節(jié)點已經(jīng)有一段時間沒有被訪問過）

3.? A? ->? B? ->? C? 插入C節(jié)點后，此時A為頭節(jié)點，C為尾節(jié)點，而最近最常訪問的節(jié)點就是C節(jié)點（剛被插入），最近最少使用的節(jié)點就是A節(jié)點 （應該很好理解了吧? : )）

那么對于緩存來講，A就是我最長時間沒訪問過的緩存，C就是最近才訪問過的緩存，所以當緩存隊列滿時就會從頭開始替換新的緩存值進去，從而保證緩存隊列中的緩存盡可能是最近一段時間訪問過的緩存，提高緩存命中率。

?

OK，到這里LinkedHashMap就分析完了，相比于HashMap還是比較容易理解的吧 ： )

下一篇文章會分析 TreeMap 的具體實現(xiàn)。

?

轉(zhuǎn)載于:https://www.cnblogs.com/smartchen/p/9016176.html

總結(jié)

以上是生活随笔為你收集整理的LinkedHashMap分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。