聽說同學(xué)你搞不懂Java的LinkedHashMap，可笑
同學(xué)們好啊，還記得 HashMap 那篇嗎？我自己感覺寫得非常棒啊，既通俗易懂，又深入源碼，真的是分析得透透徹徹、清清楚楚、明明白白的。（一不小心又上仨成語？）HashMap 哪哪都好，真的，只要你想用鍵值對，第一時間就應(yīng)該想到它。
但俗話說了，“金無足赤人無完人”，HashMap 也不例外。有一種需求它就滿足不了，假如我們需要一個按照插入順序來排列的鍵值對集合，那 HashMap 就無能為力了。因為為了提高查找效率，HashMap 在插入的時候?qū)︽I做了一次哈希算法，這就導(dǎo)致插入的元素是無序的。
對這一點還不太明白的同學(xué)，可以再回到 HashMap 那一篇，看看我對 put() 方法的講解。
final?V?putVal(int?hash,?K?key,?V?value,?boolean?onlyIfAbsent,
???????????????boolean?evict)?{
????HashMap.Node[]?tab;?HashMap.Node?p;?int?n,?i;
????//?①、數(shù)組?table?為?null?時，調(diào)用?resize?方法創(chuàng)建默認大小的數(shù)組
????if?((tab?=?table)?==?null?||?(n?=?tab.length)?==?0)
????????n?=?(tab?=?resize()).length;
????//?②、計算下標(biāo)，如果該位置上沒有值，則填充
????if?((p?=?tab[i?=?(n?-?1)?&?hash])?==?null)
????????tab[i]?=?newNode(hash,?key,?value,?null);
}
這個公式 i = (n - 1) & hash 計算后的值并不是按照 0、1、2、3、4、5 這樣有序的下標(biāo)將鍵值對插入到數(shù)組當(dāng)中的，而是有一定的隨機性。
那 LinkedHashMap 就是為這個需求應(yīng)運而生的。LinkedHashMap 繼承了 HashMap，所以 HashMap 有的關(guān)于鍵值對的功能，它也有了。
public?class?LinkedHashMap<K,V>
????extends?HashMap<K,V>
????implements?Map<K,V>{}
此外，LinkedHashMap 內(nèi)部又追加了雙向鏈表，來維護元素的插入順序。注意下面代碼中的 before 和 after，它倆就是用來維護當(dāng)前元素的前一個元素和后一個元素的順序的。
static?class?Entry<K,V>?extends?HashMap.Node<K,V>?{
????LinkedHashMap.Entry?before,?after;
????Entry(int?hash,?K?key,?V?value,?HashMap.Node?next)?{
????????super(hash,?key,?value,?next);
????}
}
關(guān)于雙向鏈表，同學(xué)們可以回頭看一遍我寫的 LinkedList 那篇文章，會對理解本篇的 LinkedHashMap 有很大的幫助。
在繼續(xù)下面的內(nèi)容之前，我先貼一張圖片，給大家增添一點樂趣——看我這心操的。UUID 那篇文章的標(biāo)題里用了“可笑”和“你”，結(jié)果就看到了下面這么樂呵的留言。
（到底是知道還是不知道，我搞不清楚了。。。）那 LinkedHashMap 這篇也用了“你”和“可笑”，不知道到時候會不會有人繼續(xù)對號入座啊，想想就覺得特別歡樂。
01、插入順序
在 HashMap 那篇文章里，我有講解到一點，不知道同學(xué)們記不記得，就是 null 會插入到 HashMap 的第一位。
Map?hashMap?=?new?HashMap<>();
hashMap.put("沉",?"沉默王二");
hashMap.put("默",?"沉默王二");
hashMap.put("王",?"沉默王二");
hashMap.put("二",?"沉默王二");
hashMap.put(null,?null);
for?(String?key?:?hashMap.keySet())?{
????System.out.println(key?+?"?:?"?+?hashMap.get(key));
}
輸出的結(jié)果是：
null?:?null
默?:?沉默王二
沉?:?沉默王二
王?:?沉默王二
二?:?沉默王二
雖然 null 最后一位 put 進去的，但在遍歷輸出的時候，跑到了第一位。
那再來對比看一下 LinkedHashMap。
Map?linkedHashMap?=?new?LinkedHashMap<>();
linkedHashMap.put("沉",?"沉默王二");
linkedHashMap.put("默",?"沉默王二");
linkedHashMap.put("王",?"沉默王二");
linkedHashMap.put("二",?"沉默王二");
linkedHashMap.put(null,?null);
for?(String?key?:?linkedHashMap.keySet())?{
????System.out.println(key?+?"?:?"?+?linkedHashMap.get(key));
}
輸出結(jié)果是：
沉?:?沉默王二
默?:?沉默王二
王?:?沉默王二
二?:?沉默王二
null?:?null
null 在最后一位插入，在最后一位輸出。
輸出結(jié)果可以再次證明，HashMap 是無序的，LinkedHashMap 是可以維持插入順序的。
那 LinkedHashMap 是如何做到這一點呢？我相信同學(xué)們和我一樣，非常希望知道原因。
要想搞清楚，就需要深入研究一下 LinkedHashMap 的源碼。LinkedHashMap 并未重寫 HashMap 的 put() 方法，而是重寫了 put() 方法需要調(diào)用的內(nèi)部方法 newNode()。
HashMap.Node?newNode(int?hash,?K?key,?V?value,?HashMap.Node?e) ? {
????LinkedHashMap.Entry?p?=
????????????new?LinkedHashMap.Entry<>(hash,?key,?value,?e);
????linkNodeLast(p);
????return?p;
}
前面說了，LinkedHashMap.Entry 繼承了 HashMap.Node，并且追加了兩個字段 before 和 after。
那，緊接著來看看 linkNodeLast() 方法：
private?void?linkNodeLast(LinkedHashMap.Entry?p) ?{
????LinkedHashMap.Entry?last?=?tail;
????tail?=?p;
????if?(last?==?null)
????????head?=?p;
????else?{
????????p.before?=?last;
????????last.after?=?p;
????}
}
看到了吧，LinkedHashMap 在添加第一個元素的時候，會把 head 賦值為第一個元素，等到第二個元素添加進來的時候，會把第二個元素的 before 賦值為第一個元素，第一個元素的 afer 賦值為第二個元素。
這就保證了鍵值對是按照插入順序排列的，明白了吧？
注：我用到的 JDK 版本為 14。
02、訪問順序
LinkedHashMap 不僅能夠維持插入順序，還能夠維持訪問順序。訪問包括調(diào)用 get() 方法、remove() 方法和 put() 方法。
要維護訪問順序，需要我們在聲明 LinkedHashMap 的時候指定三個參數(shù)。
LinkedHashMap?map?=?new?LinkedHashMap<>(16,?.75f,?true);
第一個參數(shù)和第二個參數(shù)，看過 HashMap 的同學(xué)們應(yīng)該很熟悉了，指的是初始容量和負載因子。
第三個參數(shù)如果為 true 的話，就表示 LinkedHashMap 要維護訪問順序；否則，維護插入順序。默認是 false。
Map?linkedHashMap?=?new?LinkedHashMap<>(16,?.75f,?true);
linkedHashMap.put("沉",?"沉默王二");
linkedHashMap.put("默",?"沉默王二");
linkedHashMap.put("王",?"沉默王二");
linkedHashMap.put("二",?"沉默王二");
System.out.println(linkedHashMap);
linkedHashMap.get("默");
System.out.println(linkedHashMap);
linkedHashMap.get("王");
System.out.println(linkedHashMap);
輸出的結(jié)果如下所示：
{沉=沉默王二,?默=沉默王二,?王=沉默王二,?二=沉默王二}
{沉=沉默王二,?王=沉默王二,?二=沉默王二,?默=沉默王二}
{沉=沉默王二,?二=沉默王二,?默=沉默王二,?王=沉默王二}
當(dāng)我們使用 get() 方法訪問鍵位“默”的元素后，輸出結(jié)果中，默=沉默王二 在最后；當(dāng)我們訪問鍵位“王”的元素后，輸出結(jié)果中，王=沉默王二 在最后，默=沉默王二 在倒數(shù)第二位。
也就是說，最不經(jīng)常訪問的放在頭部，這就有意思了。有意思在哪呢？
我們可以使用 LinkedHashMap 來實現(xiàn) LRU 緩存，LRU 是 Least Recently Used 的縮寫，即最近最少使用，是一種常用的頁面置換算法，選擇最近最久未使用的頁面予以淘汰。
public?class?MyLinkedHashMap<K,?V>?extends?LinkedHashMap<K,?V>?{
????private?static?final?int?MAX_ENTRIES?=?5;
????public?MyLinkedHashMap(
????????????int?initialCapacity,?float?loadFactor,?boolean?accessOrder)?{
????????super(initialCapacity,?loadFactor,?accessOrder);
????}
????@Override
????protected?boolean?removeEldestEntry(Map.Entry?eldest)?{
????????return?size()?>?MAX_ENTRIES;
????}
}
MyLinkedHashMap 是一個自定義類，它繼承了 LinkedHashMap，并且重寫了 removeEldestEntry() 方法——使 Map 最多可容納 5 個元素，超出后就淘汰。
我們來測試一下。
MyLinkedHashMap?map?=?new?MyLinkedHashMap<>(16,0.75f,true);
map.put("沉",?"沉默王二");
map.put("默",?"沉默王二");
map.put("王",?"沉默王二");
map.put("二",?"沉默王二");
map.put("一枚有趣的程序員",?"一枚有趣的程序員");
System.out.println(map);
map.put("一枚有顏值的程序員",?"一枚有顏值的程序員");
System.out.println(map);
map.put("一枚有才華的程序員","一枚有才華的程序員");
System.out.println(map);
輸出結(jié)果如下所示：
{沉=沉默王二,?默=沉默王二,?王=沉默王二,?二=沉默王二,?一枚有趣的程序員=一枚有趣的程序員}
{默=沉默王二,?王=沉默王二,?二=沉默王二,?一枚有趣的程序員=一枚有趣的程序員,?一枚有顏值的程序員=一枚有顏值的程序員}
{王=沉默王二,?二=沉默王二,?一枚有趣的程序員=一枚有趣的程序員,?一枚有顏值的程序員=一枚有顏值的程序員,?一枚有才華的程序員=一枚有才華的程序員}
沉=沉默王二 和 默=沉默王二 依次被淘汰出局。
假如在 put “一枚有才華的程序員”之前 get 了鍵位為“默”的元素：
MyLinkedHashMap?map?=?new?MyLinkedHashMap<>(16,0.75f,true);
map.put("沉",?"沉默王二");
map.put("默",?"沉默王二");
map.put("王",?"沉默王二");
map.put("二",?"沉默王二");
map.put("一枚有趣的程序員",?"一枚有趣的程序員");
System.out.println(map);
map.put("一枚有顏值的程序員",?"一枚有顏值的程序員");
System.out.println(map);
map.get("默");
map.put("一枚有才華的程序員","一枚有才華的程序員");
System.out.println(map);
那輸出結(jié)果就變了，對吧？
{沉=沉默王二,?默=沉默王二,?王=沉默王二,?二=沉默王二,?一枚有趣的程序員=一枚有趣的程序員}
{默=沉默王二,?王=沉默王二,?二=沉默王二,?一枚有趣的程序員=一枚有趣的程序員,?一枚有顏值的程序員=一枚有顏值的程序員}
{二=沉默王二,?一枚有趣的程序員=一枚有趣的程序員,?一枚有顏值的程序員=一枚有顏值的程序員,?默=沉默王二,?一枚有才華的程序員=一枚有才華的程序員}
沉=沉默王二 和 王=沉默王二 被淘汰出局了。
那 LinkedHashMap 是如何來維持訪問順序呢？同學(xué)們感興趣的話，可以研究一下下面這三個方法。
void?afterNodeAccess(Node?p) ?{?}
void?afterNodeInsertion(boolean?evict)?{?}
void?afterNodeRemoval(Node?p) ?{?}
afterNodeAccess() 會在調(diào)用 get() 方法的時候被調(diào)用，afterNodeInsertion() 會在調(diào)用 put() 方法的時候被調(diào)用，afterNodeRemoval() 會在調(diào)用 remove() 方法的時候被調(diào)用。
我來以 afterNodeAccess() 為例來講解一下。
void?afterNodeAccess(HashMap.Node?e) ?{?//?move?node?to?last
????LinkedHashMap.Entry?last;
????if?(accessOrder?&&?(last?=?tail)?!=?e)?{
????????LinkedHashMap.Entry?p?=
????????????????(LinkedHashMap.Entry)e,?b?=?p.before,?a?=?p.after;
????????p.after?=?null;
????????if?(b?==?null)
????????????head?=?a;
????????else
????????????b.after?=?a;
????????if?(a?!=?null)
????????????a.before?=?b;
????????else
????????????last?=?b;
????????if?(last?==?null)
????????????head?=?p;
????????else?{
????????????p.before?=?last;
????????????last.after?=?p;
????????}
????????tail?=?p;
????????++modCount;
????}
}
哪個元素被 get 就把哪個元素放在最后。了解了吧？
那同學(xué)們可能還想知道，為什么 LinkedHashMap 能實現(xiàn) ?LRU 緩存，把最不經(jīng)常訪問的那個元素淘汰？
在插入元素的時候，需要調(diào)用 put() 方法，該方法最后會調(diào)用 afterNodeInsertion() 方法，這個方法被 LinkedHashMap 重寫了。
void?afterNodeInsertion(boolean?evict)?{?//?possibly?remove?eldest
????LinkedHashMap.Entry?first;
????if?(evict?&&?(first?=?head)?!=?null?&&?removeEldestEntry(first))?{
????????K?key?=?first.key;
????????removeNode(hash(key),?key,?null,?false,?true);
????}
}
removeEldestEntry() 方法會判斷第一個元素是否超出了可容納的最大范圍，如果超出，那就會調(diào)用 removeNode() 方法對最不經(jīng)常訪問的那個元素進行刪除。
03、最后
由于 LinkedHashMap 要維護雙向鏈表，所以 LinkedHashMap 在插入、刪除操作的時候，花費的時間要比 HashMap 多一些。
這也是沒辦法的事，對吧，欲戴皇冠必承其重嘛。既然想要維護元素的順序，總要付出點代價才行。
那這篇文章就到此戛然而止了，同學(xué)們要覺得意猶未盡，請肆無忌憚地留言告訴我哦。（一不小心又在文末甩仨成語，有點文化底蘊，對吧？）
公眾號：沉默王二（ID：cmower）
CSDN：沉默王二
這是一個有顏值卻靠才華吃飯的程序員，你知道，他的文章風(fēng)趣幽默，讀起來就好像花錢一樣爽快。
長按下圖二維碼關(guān)注，你將感受到一個有趣的靈魂，且每篇文章都有干貨。
------------------
原創(chuàng)不易，莫要白票，如果覺得有點用的話，請毫不留情地素質(zhì)三連吧，分享、點贊、在看，我不挑，因為這將是我寫作更多優(yōu)質(zhì)文章的最強動力。