1. 前言

1.1 淺談一下

• 第一次真正意義上地接觸LinkedHashMap，來(lái)自工作中的一個(gè)需求：
  • SQL查詢(xún)計(jì)劃的生成，依賴(lài)于Hive的元數(shù)據(jù)
  • 原始的做法是，通過(guò)try-with-resource語(yǔ)句，每次訪(fǎng)問(wèn)元數(shù)據(jù)都新建一個(gè)client并立即回收
  • 這樣的client連接屬于短連接，如果每次建立、釋放連接的時(shí)間占比很高，短連接的做法并不可行
  • 因此，想使用長(zhǎng)連接，例如連接池，來(lái)改造訪(fǎng)問(wèn)邏輯，提高元數(shù)據(jù)的訪(fǎng)問(wèn)效率
• 既然使用連接池，那就需要及時(shí)關(guān)閉長(zhǎng)時(shí)間空間的連接，避免占用資源
• 因此，如何實(shí)現(xiàn)空閑連接自動(dòng)釋放成為問(wèn)題
• 作為菜鳥(niǎo)：我希望在連接中增加一個(gè)accessTime字段，然后遍歷池中的連接，如果發(fā)現(xiàn)距上一次使用超過(guò)一定時(shí)間，就可以釋放連接
• 這其實(shí)就跟LRU緩存很像，最近最少使用的連接排位逐漸靠前，達(dá)到閾值就被釋放
• 同事推薦使用LinkedHashMap實(shí)現(xiàn)LRU緩存，及時(shí)清理空閑連接
• 通過(guò)簡(jiǎn)單的學(xué)習(xí)，自己了解到：LinkedHashMap實(shí)現(xiàn)LRU緩存，最重要的是重寫(xiě)removeEldestEntry()方法，實(shí)現(xiàn)清理空閑連接的邏輯

1.2 按照某種順序連接哈希表中的所有entry

• 單從類(lèi)名上看，LinkedHashMap應(yīng)該是具有鏈表特性的哈希表
• 回想一下鏈表的特性：
  • 相對(duì)數(shù)組，鏈表不需要連續(xù)的存儲(chǔ)空間，節(jié)點(diǎn)（元素）之間通過(guò)next引用連接
  • 鏈表中的元素，只能順序訪(fǎng)問(wèn)，不支持隨機(jī)訪(fǎng)問(wèn)（順著next引用查找元素）
  • 支持快速地插入或刪除元素：一旦確認(rèn)位置，只需要修改節(jié)點(diǎn)之間的引用即可，不存在元素的移位
• 那具有鏈表特性的哈希表，鏈接的不可能是桶，更可能的是entry
• 問(wèn)題1： 是桶中的entry使用鏈表連接，還是整個(gè)哈希表中的entry使用鏈表連接？
• 分析一下
  • HashMap中，同一個(gè)桶中的entry已經(jīng)使用鏈表連接了
  • 這里的鏈表更有可能是針對(duì)哈希表中的所有entry
• 問(wèn)題2： 將所有entry連接起來(lái)，有啥用？
  • 學(xué)習(xí)HashMap和TreeMap時(shí)，提到過(guò)一個(gè)關(guān)于entry是否有序的區(qū)別
  • TreeMap實(shí)現(xiàn)了SortedMap，支持按key的自然順序或自定義比較器的順序訪(fǎng)問(wèn)entry
  • HashMap既不保證entry的順序，還可能因?yàn)閿U(kuò)容導(dǎo)致entry的順序在一段時(shí)間內(nèi)發(fā)生變化
  • 如果按照entry的插入順序，將哈希表中的所有entry連接起來(lái)，那就可以實(shí)現(xiàn)支持插入順序的哈希表
  • 其實(shí)，LinkedHashMap不僅支持按照插入順序組織entry，還支持按照訪(fǎng)問(wèn)順序（LRU）組織entry：頭部是最近最少訪(fǎng)問(wèn)的entry
  • 這也是為啥，同事推薦我使用LinkedHashMap實(shí)現(xiàn)LRU

1.3 LinkedHashMap的特性

• 學(xué)習(xí)一個(gè)類(lèi)之前，如果有完善的類(lèi)注釋?zhuān)喿x類(lèi)注釋肯定是一個(gè)不錯(cuò)的選擇

根據(jù)類(lèi)注釋?zhuān)琇inkedHashMap的特性如下

• LinkedHashMap使用雙向鏈表，維護(hù)了元素的順序
  • LinkedHashMap不僅支持entry的插入順序，還支持entry的訪(fǎng)問(wèn)順序
  • 默認(rèn)為entry的插入順序，通過(guò)LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)構(gòu)造函數(shù)，可以創(chuàng)支持于訪(fǎng)問(wèn)順序的LinkedHashMap
  • 整個(gè)雙向鏈表分為head和tail，head指向最近最少訪(fǎng)問(wèn)的entry，tail指向最近剛訪(fǎng)問(wèn)的entry。
  • 一旦插入或訪(fǎng)問(wèn)entry，會(huì)引起entry的順序變化（被移動(dòng)得到末尾）
  • LinkedHashMap還提供removeEldestEntry()方法，通過(guò)重寫(xiě)該方法，可以在新增entry時(shí)，刪除老舊的entry（位于頭部）

注意：

• 如果基于插入順序，put時(shí)更新key已映射的value，不會(huì)引起順序變化；
• 如果基于訪(fǎng)問(wèn)順序，任何訪(fǎng)問(wèn)操作（如put、get）都將導(dǎo)致順序的變化。例外： 通過(guò)iterator或for-each遍歷entry，不影響entry的順序
• LinkedHashMap的優(yōu)勢(shì)：不僅解決了HashMap或HashTable中entry無(wú)序的情況，還相對(duì)TreeMap的有序?qū)崿F(xiàn)更節(jié)約成本

本人猜測(cè)是實(shí)現(xiàn)成本，LinkedHashMap是基于HashMap實(shí)現(xiàn)的，真正需要編寫(xiě)的代碼較少

• LinkedHashMap是非同步的，即非線(xiàn)程安全的
• LinkedHashMap沒(méi)有對(duì)應(yīng)的線(xiàn)程安全的替代類(lèi)，只能通過(guò)Collections.synchronizedMap()將其轉(zhuǎn)為線(xiàn)程安全的map
• LinkHashMap繼承了HashMap，同樣也允許null值：只允許一個(gè)key為null，允許多個(gè)value為null

關(guān)于性能

• 與HashMap一樣，在hash散列均勻的情況下，LinkedHashMap可以提供常數(shù)級(jí)的訪(fǎng)問(wèn)效率
• 由于需要維護(hù)entry中的雙向鏈表，LinkedHashMap的性能稍遜于HashMap
• 同時(shí)，對(duì)LinkedHashMap的遍歷直接基于雙向鏈表，而非基于桶（遍歷特指iterator或for-each遍歷，并非確定entry位置時(shí)的遍歷）
• 因此，LinkHashMap的遍歷時(shí)間，與entry的數(shù)目成正比

LinkedHashMap使用fail-fast迭代器

• 如果使用插入順序，查詢(xún)和更新操作不屬于結(jié)構(gòu)改變，新增、刪除、rehash屬于結(jié)構(gòu)改變
• 如果使用訪(fǎng)問(wèn)順序，任何尋址（查、新增、更新和rehash）或刪除操作都屬于結(jié)構(gòu)改變
• 迭代器一旦創(chuàng)建，除了迭代器自身的remove方法，任何引起map結(jié)構(gòu)改變的操作，都將使迭代器拋出ConcurrentModificationException

總結(jié)一下

• LinkedHashMap使用雙向鏈表維護(hù)了entry的順序：插入順序或訪(fǎng)問(wèn)順序
• LinkedHashMap允許null值
• LinkedHashMap是非線(xiàn)程安全的
• LinkedHashMap使用fail-fast迭代器
• 由于需要維護(hù)雙向鏈表，LinkedHashMap的性能稍遜于其父類(lèi)HashMap
• LinkedHashMap的優(yōu)勢(shì)：entry有序，且實(shí)現(xiàn)成本較低

2. LinkedHashMap概述

2.1 類(lèi)圖

LinkedHashMap類(lèi)的聲明如下

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

類(lèi)圖，如下圖所示

從類(lèi)圖來(lái)看

• LinkedHashMap繼承了HashMap，說(shuō)明它具有HashMap的特性（桶數(shù)組+ 鏈表 + 紅黑樹(shù)）
• LinkedHashMap實(shí)現(xiàn)了Map接口，額，暫且認(rèn)為和HashMap一樣吧，這個(gè)作者的一個(gè)小失誤，且一直沒(méi)被源代碼的維護(hù)人員校正

2.2 成員變量及數(shù)據(jù)結(jié)構(gòu)

• LinkedHashMap繼承了HashMap，那HashMap所特有的桶數(shù)組+ 鏈表 + 紅黑樹(shù)的結(jié)構(gòu)LinkedHashMap也一樣具有
• 那是如何在所有的entry中維護(hù)一個(gè)雙向鏈表的呢？從成員變量就可以解釋這個(gè)問(wèn)題
• 新增了三個(gè)成員變量

// 雙向鏈表的頭部：插入順序時(shí)，是最先插入的entry；訪(fǎng)問(wèn)順序時(shí)，是最近最少訪(fǎng)問(wèn)的entry
transient LinkedHashMap.Entry<K,V> head;
// 雙向鏈表的尾部：插入順序時(shí)，是最后插入的entry；訪(fǎng)問(wèn)順序時(shí)，是最近剛訪(fǎng)問(wèn)的entry
transient LinkedHashMap.Entry<K,V> tail;
// 是否使用訪(fǎng)問(wèn)順序，true表示使用
final boolean accessOrder;

• 其中，Entry的定義如下：增加了 before 和 after 引用，是實(shí)現(xiàn)雙向鏈表的關(guān)鍵

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

回憶之前學(xué)習(xí)HashMap時(shí)，關(guān)于數(shù)據(jù)結(jié)構(gòu)的講解

HashMap中，鏈表對(duì)應(yīng)的是Node、紅黑樹(shù)對(duì)應(yīng)的是TreeNode

TreeNode繼承了LinkedHashMap.Entry，LinkedHashMap.Entry又繼承了HashMap.Node

到現(xiàn)在，作者都還有疑問(wèn)：TreeNode為啥不直接繼承HashMap.Node？因?yàn)門(mén)reeNode的實(shí)際使用中，好像沒(méi)有用到 LinkedHashMap.Entry 中的新增屬性

在后面的學(xué)習(xí)中，通過(guò)newNode()、newTreeNode()、afterNodeAccess()、afterNodeRemoval()方法，自己體會(huì)到了這樣設(shè)計(jì)的原因

在HashMap中，節(jié)點(diǎn)無(wú)非是鏈表節(jié)點(diǎn) Node 或紅黑樹(shù)節(jié)點(diǎn)TreeNode

為了實(shí)現(xiàn)雙向鏈表，LinkedHashMap中的鏈表節(jié)點(diǎn) Entry 相對(duì)父類(lèi) Node 增加了before和after引用

接著，紅黑樹(shù)節(jié)點(diǎn)TreeNode繼承 LinkedHashMap.Entry，這樣LinkHashMap中的節(jié)點(diǎn)（鏈表節(jié)點(diǎn)或紅黑樹(shù)節(jié)點(diǎn)）具有before和after引用，使得雙向鏈表連接所有entry成為可能

除此之外，TreeNode可以向上轉(zhuǎn)型為 LinkedHashMap.Entry，這樣所有節(jié)點(diǎn)都當(dāng)做LinkedHashMap.Entry進(jìn)行處理，而無(wú)需關(guān)注是鏈表節(jié)點(diǎn)還是紅黑樹(shù)節(jié)點(diǎn)

總結(jié)

LinkedHashMap依靠Entry的 before 和 after 引用構(gòu)建雙向鏈表

同時(shí)，LinkedHashMap類(lèi)中的head和tail指出了雙向鏈表的頭尾，有助于雙向鏈表的構(gòu)建及順序的維護(hù)（尾部插入、最近剛訪(fǎng)問(wèn)位于尾部等）

如果，一個(gè)HashMap的示意圖如下

使用LinkedHashMap后，示意圖如下

2.3 構(gòu)造函數(shù)

LinkedHashMap提供如下構(gòu)造函數(shù)

// 創(chuàng)建一個(gè)指定了初始化容量和loadFactor的、基于插入順序的LinkedHashMap
// 對(duì)應(yīng)HashMap的public HashMap(int initialCapacity, float loadFactor)
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}
// 創(chuàng)建一個(gè)指定了初始化容量的、基于插入順序的LinkedHashMap
// 對(duì)應(yīng)HashMap的public HashMap(int initialCapacity) 
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
// 創(chuàng)建一個(gè)基于插入順序的LinkedHashMap，容量和loadFactor使用默認(rèn)值
// 對(duì)應(yīng)HashMap的public HashMap()
public LinkedHashMap() {
    super();
    accessOrder = false;
}
// 基于已有的map，創(chuàng)建一個(gè)基于插入順序的LinkedHashMap，容量和loadFactor使用默認(rèn)值
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}
// 指定初始化容量、loadFactor和順序的LinkedHashMap，accessOrder為true表示訪(fǎng)問(wèn)順序
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

最后一個(gè)構(gòu)造函數(shù)，是與父類(lèi)相比，多出來(lái)的一個(gè)構(gòu)函數(shù)，專(zhuān)為創(chuàng)建基于訪(fǎng)問(wèn)順序的LinkedHashMap而準(zhǔn)備

實(shí)現(xiàn)LRU緩存時(shí)，都需要使用該構(gòu)造函數(shù)

new LinkedHashMap(capacity, loadFactor, true)

3. 查找方法

LinkedHashMap中，重寫(xiě)的方法很少，查找方法幾乎都進(jìn)行了重寫(xiě)

目的： 為了支持訪(fǎng)問(wèn)順序，一旦通過(guò)查找方法訪(fǎng)問(wèn)了entry，entry的順序應(yīng)該發(fā)生變化

3.1 get方法

get() 方法的代碼如下

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

與HashMap中的方法相比，在獲取到entry后，還需要判斷是否為訪(fǎng)問(wèn)順序；如果使用訪(fǎng)問(wèn)順序，需要通過(guò) afterNodeAccess() 方法調(diào)整該entry的位置

3.1.1 afterNodeAccess()方法

afterNodeAccess() 方法在HashMap的 put() 方法中遇到過(guò)，但是當(dāng)時(shí)說(shuō)它是個(gè)空方法， LinkedHashMap 重寫(xiě)了該方法

按照本人的理解，afterNodeAccess 方法的作用：在LinkedHashMap使用訪(fǎng)問(wèn)順序時(shí)，將剛訪(fǎng)問(wèn)過(guò)的entry移到雙向鏈表末尾

如果entry本身就在末尾，則不用移動(dòng)

如果entry處于雙向鏈表的頭部，則只需要斷開(kāi)與后繼節(jié)點(diǎn)的關(guān)聯(lián)，然后將其移到末尾

如果entry處于雙向鏈表的中部，則需要先將前驅(qū)節(jié)點(diǎn)與后繼節(jié)點(diǎn)連上，然后將其移到末尾（最后一部，需要 e.after = null ）

代碼如下：不過(guò)自己覺(jué)得代碼邏輯有點(diǎn)亂，貌似還有多余的部分

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) { // 訪(fǎng)問(wèn)順序且非末尾節(jié)點(diǎn)
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null; // 首先斷開(kāi)與后繼節(jié)點(diǎn)的關(guān)聯(lián)，非常明智
        if (b == null) // 前驅(qū)節(jié)點(diǎn)為空，說(shuō)明p在頭部，直接將head指向后繼節(jié)點(diǎn)
            head = a;
        else // 否則，前驅(qū)節(jié)點(diǎn)指向后繼節(jié)點(diǎn)
            b.after = a;
        if (a != null)  // 后繼節(jié)點(diǎn)指向前驅(qū)節(jié)點(diǎn)
            a.before = b;
        else // 這里的代碼多余？如果后繼節(jié)點(diǎn)為null，那p就是末尾了，根本進(jìn)入不了if？？？
            last = b;
        if (last == null)  // 這里也是因?yàn)樯弦徊綄?dǎo)致的多余判斷
            head = p;
        else { // 將p移到末尾
            p.before = last;
            last.after = p;
        }
        tail = p; // 更新tail引用
        ++modCount;
    }
}

3.2 getOrDefault / containsValue方法

3.2.1 getOrDefault方法

與get方法一樣， getOrDefault() 方法，也增加了對(duì) accessOrder 為true的處理

public V getOrDefault(Object key, V defaultValue) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return defaultValue;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

3.2.2 containsValue方法

查找類(lèi)的方法，get、getOrDefault都重寫(xiě)了，按理說(shuō)containsKey和containsValue也應(yīng)該重寫(xiě)的

但LinkedHashMap只重寫(xiě)了containsValue方法

仔細(xì)想想也是有道理的：

• 判斷是否包含key，只需要通過(guò)getNode獲取到key對(duì)應(yīng)entry就行了
• 判斷是否包含value，需要遍歷桶中的每個(gè)entry（雙層循環(huán)，外層為桶，內(nèi)層為桶中的元素）
• LinkedHashMap中，所有的entry使用雙向鏈表關(guān)聯(lián)，查找value直接基于雙向鏈表順序查找即可

containsValue的代碼如下，十分簡(jiǎn)單

public boolean containsValue(Object value) {
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        V v = e.value;
        if (v == value || (value != null && value.equals(v)))
            return true;
    }
    return false;
}

4. put方法

LinkedHashMap就沒(méi)有重寫(xiě)put方法，因?yàn)镠ashMap中，put方法的核心方法 putVal() 已經(jīng)未雨綢繆了

putVal() 方法中，存在對(duì)entry被訪(fǎng)問(wèn)或新增entry后，調(diào)整雙向鏈表的空方法： afterNodeAccess() 和 afterNodeInsertion()

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // 省略一些代碼
    else {
        // 存在key的映射，則需要更新value；如果是訪(fǎng)問(wèn)順序，需要將entry移到末尾
        if (e != null) { 
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e); // 將entry移到末尾
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict); // 新增節(jié)點(diǎn)，需要調(diào)整鏈表
    return null;
}

想要實(shí)現(xiàn)LinkedHashMap，只需要重寫(xiě)上述兩個(gè)方法就可以了。

所以，這也是為啥LinkedHashMap沒(méi)有重寫(xiě)put() 方法

4.1 afterNodeInsertion方法

一開(kāi)始，自己認(rèn)為 afterNodeInsertion() 方法要完成如下事情

不管是插入順序還是訪(fǎng)問(wèn)順序，新增的entry都應(yīng)該位于雙向鏈表的尾部，由 afterNodeInsertion() 方法完成這一操作然后根據(jù) removeEldestEntry() 的結(jié)果，來(lái)決定是否刪除最老的entry

后來(lái)一看，怎么 afterNodeInsertion() 方法的定義如下：入?yún)⒍疾皇莿偛迦氲膃ntry

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // 頭節(jié)點(diǎn)不為null，且需要?jiǎng)h除最老的節(jié)點(diǎn)，則刪除頭結(jié)點(diǎn)
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

其入?yún)vict，是驅(qū)逐的意思，在 put() --> putVal() 時(shí)固定為true

也就是說(shuō)，在調(diào)用 afterNodeInsertion() 方法時(shí)，evict固定為true

是否會(huì)刪除最老的entry，由 removeEldestEntry() 方法決定

removeEldestEntry() 方法如下，總是返回false。

即：LinkedHashMap就算使用訪(fǎng)問(wèn)順序，也只是讓最老的entry位于頭部，并不會(huì)刪除這也是為什么，在使用LinkedHashMap實(shí)現(xiàn)LRU時(shí)，一般都需要重寫(xiě) removeEldestEntry() 方法，讓其在某種情況下返回true，實(shí)現(xiàn)過(guò)期元素的清理

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

4.2 newNode和newTreeNode方法

問(wèn)題來(lái)了：既然 afterNodeInsertion() 方法只負(fù)責(zé)刪除最老的元素，在哪里完成entry加入雙向鏈表的呢？仔細(xì)閱讀 putVal() 方法，發(fā)現(xiàn)新增entry時(shí)，通過(guò) newNode() 和 newTreeNode() 完成節(jié)點(diǎn)的新建LinkedHashMap重寫(xiě)了這兩個(gè)新建節(jié)點(diǎn)的方法，在這兩個(gè)方法中完成了entry加入雙向鏈表的邏輯

newNode()方法

不再是簡(jiǎn)單的 return new Node<>() ，而是新建 LinkedHashMap.Entry ，并將其加入雙向鏈表末尾

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    // 將p放到鏈表末尾
    linkNodeLast(p);
    return p;
}
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    // 原尾節(jié)點(diǎn)為null，表明p是第一個(gè)節(jié)點(diǎn)，head指向p
    if (last == null)
        head = p;
    else { // 否則，將p和原尾結(jié)點(diǎn)關(guān)聯(lián)
        p.before = last;
        last.after = p;
    }
}

newTreeNode方法

不再是簡(jiǎn)單的 return new TreeNode<>() ，而是創(chuàng)建一個(gè)TreeNode，并將其加入雙向鏈表尾部

TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
    TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
    linkNodeLast(p);
    return p;
}

5. remove方法(afterNodeRemoval)

在學(xué)習(xí)HashMap的remove方法時(shí)，兩種remove方法的核心都是通過(guò) removeNode() 方法實(shí)現(xiàn)節(jié)點(diǎn)的刪除

removeNode() 方法的末尾，有一個(gè)空的 afterNodeRemoval() 方法

學(xué)了 afterNodeAccess 和afterNodeInsertion， 應(yīng)該能觸類(lèi)旁通：LinkedHashMap會(huì)重寫(xiě) afterNodeRemoval() 方法，實(shí)現(xiàn)刪除entry后的雙向鏈表調(diào)整

afterNodeRemoval() 方法，代碼如下

void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null; // 主動(dòng)斷開(kāi)p與其他entry的關(guān)聯(lián)
    if (b == null) // p是頭節(jié)點(diǎn)，則head指向其后繼節(jié)點(diǎn)
        head = a;
    else // 否則，前驅(qū)節(jié)點(diǎn)指向后繼節(jié)點(diǎn)
        b.after = a;
    if (a == null)  // p是尾結(jié)點(diǎn)，tail指向前驅(qū)節(jié)點(diǎn)
        tail = b;
    else // 后繼節(jié)點(diǎn)指向前驅(qū)節(jié)點(diǎn)
        a.before = b;
}

要是我寫(xiě)的話(huà)，我可能會(huì)這樣實(shí)現(xiàn)

void afterNodeRemoval(Node<K,V> e) { // unlink
     LinkedHashMap.Entry<K,V> p =
         (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
     // 先斷開(kāi)p與其他節(jié)點(diǎn)的關(guān)聯(lián)
     p.before = p.after = null;
     // 情況1: p是頭結(jié)點(diǎn)也是尾節(jié)點(diǎn)
     if (head == p && head == tail) {
     	head = tail = null;
     } else if (head == p) { // 情況2：p是頭結(jié)點(diǎn)
     	a.before = null;
     	head = a;
     } else if (tail == p) { // 情況3：p是尾節(jié)點(diǎn)
     	b.after = null;
     	tail = b;
     } else { // 情況4：p是中間節(jié)點(diǎn)
     	b.after = a;
     	a.before = b;
     }
 }

按照我的思路，發(fā)現(xiàn)寫(xiě)源碼的人，腦袋就是靈活

b為空，說(shuō)明p是頭結(jié)點(diǎn)，直接將head指向a；可以涵蓋情況1（ head = a = null ）、情況2（ head = a, a != null ）否則，將 b.after 指向a；可以涵蓋情況3（ b.after = a = null ）、情況4（ b.after = a, a != null ）a為空，說(shuō)明p是尾結(jié)點(diǎn)，直接將tail指向b；可以涵蓋情況1（ tail = b = null ）、情況3（ tail = b, b! = null ）否則，將 a.before 指向b；可以涵蓋情況2（ a.before = b = null ）、情況4（ a.before = b, b! = null ）

這里就不畫(huà)圖展示了，讀者可以先畫(huà)出四種情況的圖，再結(jié)合圖閱讀源代碼

6. 總結(jié)

6.1 基于LinkedHashMap實(shí)現(xiàn)LRU緩存

在不考慮線(xiàn)程安全的情況下，基于LinkedHashMap實(shí)現(xiàn)LRU緩存，是最簡(jiǎn)單快捷的方式

只需要重寫(xiě) removeEldestEntry() 方法，使其在達(dá)到閾值時(shí)返回true，即可刪除最近最少使用的數(shù)據(jù)

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int maxSize;
    public LRUCache(int maxSize) {
        super(16, 0.75f, true);
        this.maxSize = maxSize;
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }
    public static void main(String[] args) {
        LRUCache<String, Integer> cache = new LRUCache<>(5);
        cache.put("張三", 21);
        cache.put("lucy", 24);
        cache.put("john", 30);
        cache.put("jack", 25);
        cache.put("李四", 20);
        // 插入第6個(gè)元素，最后發(fā)現(xiàn)最先插入的key-value被刪除
        cache.put("王二", 32);
        System.out.println("張三的信息已不存在: " + !cache.containsKey("張三"));
    }
}

6.2 LinkedHashMap如何維護(hù)順序的？

首先，LinkedHashMap基于HashMap實(shí)現(xiàn)了有序的哈希表

其次，LinkedHashMap的有序是通過(guò)雙向鏈表維護(hù)的，其在數(shù)據(jù)結(jié)構(gòu)上就做了工作

節(jié)點(diǎn)類(lèi)型為L(zhǎng)inkedHashMap.Entry，相對(duì)父類(lèi)HashMap.Node，多了 before 和 after 引用，用于在entry間構(gòu)建雙向鏈表為了更好地維護(hù)entry的順序、更快地查找entry，LinkedHashMap類(lèi)中，增加了 head 和 tail 引用LinkedHashMap類(lèi)中，還增加了 accessOrder 變量，以決定是維護(hù)插入順序還是訪(fǎng)問(wèn)順序

然后，LinkedHashMap還通過(guò)重寫(xiě)以下方法，維護(hù)entry在雙向鏈表中的順序

void afterNodeAccess(Node<K,V> p)
void afterNodeRemoval(Node<K,V> p)
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next)
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next)

除此之外，提供了刪除最近最少訪(fǎng)問(wèn)entry的方法，有助于實(shí)現(xiàn)LRU

void afterNodeInsertion(boolean evict) // 關(guān)鍵需要重寫(xiě)removeEldestEntry()

6.3 LinkedHashMap與HashMap的聯(lián)系

二者的聯(lián)系：LinkedHashMap繼承了HashMap，基于雙向鏈表維護(hù)了entry的順序

數(shù)據(jù)結(jié)構(gòu)上：Entry增加before和after引用，LinkedHashMap增加head、tail引用

繼承與重載上：LinkedHashMap相當(dāng)于站在巨人的肩膀上做事，只實(shí)現(xiàn)了一些關(guān)鍵的方法

get() 和getOrDefault() ，增加了維護(hù)訪(fǎng)問(wèn)順序的代碼

containsValue()，不再基于桶遍歷entry，而是直接基于雙向鏈表遍歷entry

putVal()中，新增節(jié)點(diǎn)的newNode() 和newTreeNode() 方法都重寫(xiě)了，實(shí)現(xiàn)了節(jié)點(diǎn)上鏈

同時(shí)，putVal()中，afterNodeInsertion()被重寫(xiě)，可以在removeEldestEntry() 返回true時(shí)，實(shí)現(xiàn)LRU緩存

removeNode()方法中，最后調(diào)用的afterNodeRemoval() 方法以刪除雙向鏈表中的對(duì)應(yīng)節(jié)點(diǎn)

6.4 LinkedHashMap與HashMap的異同

相同點(diǎn)：

都實(shí)現(xiàn)了Map接口，允許null值

都是非線(xiàn)程安全的map類(lèi)，需要通過(guò)Collections.synchronizedMap()轉(zhuǎn)為安全的map類(lèi)，或使用已有的、線(xiàn)程安全的替代類(lèi)

都使用fail-fast迭代器，一旦創(chuàng)建好迭代器，除非使用迭代器自身的remove方法，其他任何改變map結(jié)構(gòu)的方法，都將觸發(fā)ConcurrentModificationException

其他的，擴(kuò)容、鏈表轉(zhuǎn)紅黑樹(shù)、紅黑樹(shù)退回鏈表等，LinkHashMap都和HashMap一樣

不同點(diǎn)

最大的不同點(diǎn)：LinkedHashMap通過(guò)雙向鏈表為了entry的順序，插入順序或訪(fǎng)問(wèn)順序；HashMap中的entry不僅無(wú)序，迭代結(jié)果還可能在一段時(shí)間內(nèi)發(fā)生變化

其他的，無(wú)非是實(shí)現(xiàn)上的不同，例如，containsValue()，不再基于桶遍歷entry，而是直接基于雙向鏈表遍歷entry

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

最新評(píng)論