深讀源碼-java集合之LinkedHashMap源碼分析

簡介

LinkedHashMap内部維護了一個雙向連結清單，能保證元素按插入的順序通路，也能以通路順序通路，可以用來實作LRU緩存政策。

LinkedHashMap可以看成是 LinkedList + HashMap。

類繼承體系

深讀源碼-java集合之LinkedHashMap源碼分析

LinkedHashMap繼承HashMap，擁有HashMap的所有特性，并且額外增加了按一定順序通路的特性。

Entry的繼承關系

深讀源碼-java集合之LinkedHashMap源碼分析

Entry作為基本的節點，可以看到LinkedHashMap的Entry繼承自HashMap的Node，在其基礎上加上了before和after兩個指針，而TreeNode作為HashMap和LinkedHashMap的樹節點，繼承自LinkedHahsMap的Entry，并且加上了樹節點的相關指針，另外提一點：before和parent的兩個概念是不一樣的，before是相對于連結清單來的，parent是相對于樹操作來的，是以要分兩個。

Iterator的繼承關系

深讀源碼-java集合之LinkedHashMap源碼分析

LinkedHashMap的疊代器為周遊節點提供了自己的實作——LinkedHashIterator，對于Key、Value、Entry的3個疊代器，都繼承自它。而且内部采用的周遊方式就是在前面提到的Entry裡加的新的指向下一個節點的指針after，後面我們将具體看它的代碼實作。

存儲結構

深讀源碼-java集合之LinkedHashMap源碼分析

雙連結清單是連結清單的一種，由節點組成，每個資料結點中都有兩個指針，分别指向直接後繼和直接前驅

深讀源碼-java集合之LinkedHashMap源碼分析

我們知道HashMap使用（數組 + 單連結清單 + 紅黑樹）的存儲結構，那LinkedHashMap是怎麼存儲的呢？

通過上面的繼承體系，我們知道它繼承了HashMap，是以它的内部也有這三種結構，但是它還額外添加了一種“雙向連結清單”的結構存儲所有元素的順序。

添加删除元素的時候需要同時維護在HashMap中的存儲，也要維護在LinkedList中的存儲，是以性能上來說會比HashMap稍慢。

源碼解析

屬性

/**
 * 雙向連結清單頭節點 
 */
transient LinkedHashMap.Entry<K,V> head;

/**
 * 雙向連結清單尾節點 
 */
transient LinkedHashMap.Entry<K,V> tail;

/**
 * 是否需要按通路順序排序，用來指定LinkedHashMap的疊代順序。
 * true則表示按照基于通路的順序來排列，意思就是最近使用的entry，放在連結清單的最末尾
 * false則表示按照插入順序排序
 */ 
final boolean accessOrder;

（1）head

雙向連結清單的頭節點，舊資料存在頭節點。

（2）tail

雙向連結清單的尾節點，新資料存在尾節點。

（3）accessOrder

是否需要按通路順序排序， true則表示按照基于通路的順序來排列，意思就是最近使用的entry，放在連結清單的最末尾；false則表示按照插入順序排序。

注意：

accessOrder是

final關鍵字，說明我們要在構造方法裡給它初始化。

内部類

// 位于LinkedHashMap中
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);
    }
}

// 位于HashMap中
static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;
}

存儲節點，繼承自HashMap的Node類，next用于單連結清單存儲于桶中，before和after用于雙向連結清單存儲所有元素。

構造方法

public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}

public LinkedHashMap() {
    super();
    accessOrder = false;
}

public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

前四個構造方法accessOrder都等于false，說明雙向連結清單是按插入順序存儲元素。

最後一個構造方法accessOrder從構造方法參數傳入，如果傳入true，則就實作了按通路順序存儲元素，這也是實作LRU緩存政策的關鍵。

get(Object key)方法

擷取元素。

public V get(Object key) {
    Node<K,V> e;
    // 調用HashMap的getNode的方法，詳見上一篇HashMap源碼解析
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // 在取值後對參數accessOrder進行判斷，如果為true，執行afterNodeAccess
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

如果查找到了元素，且accessOrder為true，則調用afterNodeAccess()方法把通路的節點移到雙向連結清單的末尾。

afterNodeAccess(Node<K,V> e)方法

在節點通路之後被調用，主要在put()已經存在的元素或get()時被調用，如果accessOrder為true，調用這個方法把通路到的節點移動到雙向連結清單的末尾。

// 此函數執行的效果就是将最近使用的Node，放在連結清單的最末尾
void afterNodeAccess(Node<K,V> e) {
  LinkedHashMap.Entry<K,V> last;
  // 僅當按照LRU原則且e不在最末尾，才執行修改連結清單，将e移到連結清單最末尾的操作
  if (accessOrder && (last = tail) != e) {
    // 将e指派臨時節點p， b是e的前一個節點， a是e的後一個節點
    LinkedHashMap.Entry<K,V> p =
      (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    // 設定p的後一個節點為null，因為執行後p在連結清單末尾，after肯定為null
    p.after = null;
    // p前一個節點不存在，情況一
    if (b == null) // ①
      head = a;// p為頭部，前一個節點b不存在，那麼考慮到p要放到最後面，則設定p的後一個節點a為head
    else
      b.after = a;// P不是頭部，前一個節點b存在，重新設定b的後一個節點為a
    if (a != null) 
      a.before = b;// P不是尾部，設定a的前一個節點為b
    // p的後一個節點不存在，情況二
    else // ②
      last = b;// p為尾部，後一個節點a不存在，那麼考慮到統一操作，設定last為b
    // 情況三
    if (last == null) // ③
      head = p;// p為連結清單裡的第一個節點，head=p
    // 正常情況，将p設定為尾節點的準備工作，p的前一個節點為原先的last，last的after為p
    else {
      p.before = last;
      last.after = p;
    }
    // 将p設定為尾節點
    tail = p;
    // 修改計數器+1
    ++modCount;
  }
}

（1）如果accessOrder為true，并且通路的節點不是尾節點；

（2）從雙向連結清單中移除通路的節點；

（3）把通路的節點加到雙向連結清單的末尾；（末尾為最新通路的元素）

标注的情況如下圖所示（特别說明一下，這裡是顯示連結清單的修改後指針的情況，實際上在桶裡面的位置是不變的，隻是前後的指針指向的對象變了）：

深讀源碼-java集合之LinkedHashMap源碼分析

下面來簡單說明一下：

正常情況下：查詢的p在連結清單中間，那麼将p設定到末尾後，它原先的前節點b和後節點a就變成了前後節點。
情況一：p為頭部，前一個節點b不存在，那麼考慮到p要放到最後面，則設定p的後一個節點a為head
情況二：p為尾部，後一個節點a不存在，那麼考慮到統一操作，設定last為b
情況三：p為連結清單裡的第一個節點，head=p

put()方法

LinkedHashMap的put方法調用的還是HashMap裡的put，不同的是重寫了裡面的部分方法：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
  	...
    tab[i] = newNode(hash, key, value, null);
  	...
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  	...
    if ((e = p.next) == null) {
      p.next = newNode(hash, key, value, null);
    ...
        afterNodeAccess(e);
    ...
        afterNodeInsertion(evict);
      return null;
}

由于在之前《深讀源碼-java集合之HashMap源碼分析》分析過了put方法，這裡筆者就省略了部分代碼，LinkedHashMap将其中

newNode

方法以及之前設定下的鈎子方法

afterNodeAccess

和

afterNodeInsertion

進行了重寫，進而實作了加傳入連結表的目的：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
  // 秘密就在于 new的是自己的Entry類，然後調用了linkedNodeLast
  LinkedHashMap.Entry<K,V> p =
    new LinkedHashMap.Entry<K,V>(hash, key, value, e);
  linkNodeLast(p);
  return p;
}

// 顧名思義就是把新加的節點放在連結清單的最後面
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
  // 将tail給臨時變量last
  LinkedHashMap.Entry<K,V> last = tail;
  // 把new的Entry給tail
  tail = p;
  // 若沒有last，說明p是第一個節點，head=p
  if (last == null)
    head = p;
  // 否則就做準備工作，你懂的 (￣▽￣)"
  else {
    p.before = last;
    last.after = p;
  }
}

// 這裡筆者也把TreeNode的重寫也加了進來，因為putTreeVal裡有調用了這個
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;
}

// 插入後把最老的Entry删除，不過removeEldestEntry總是傳回false，是以不會删除，估計又是一個鈎子方法給子類用的
void afterNodeInsertion(boolean evict) {
  LinkedHashMap.Entry<K,V> first;
  if (evict && (first = head) != null && removeEldestEntry(first)) {
    K key = first.key;
    removeNode(hash(key), key, null, false, true);
  }
}

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

afterNodeInsertion(boolean evict)方法

在節點插入之後做些什麼，在HashMap中的putVal()方法中被調用，可以看到HashMap中這個方法的實作為空。

// 插入後把最老的Entry删除，不過removeEldestEntry總是傳回false，是以不會删除，估計又是一個鈎子方法給子類用的
void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

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

evict，驅逐的意思。

（1）如果evict為true，且頭節點不為空，且确定移除最老的元素，那麼就調用HashMap.removeNode()把頭節點移除（這裡的頭節點是雙向連結清單的頭節點，而不是某個桶中的第一個元素）；

（2）HashMap.removeNode()從HashMap中把這個節點移除之後，會調用afterNodeRemoval()方法；

（3）afterNodeRemoval()方法在LinkedHashMap中也有實作，用來在移除元素後修改雙向連結清單，見下文；

（4）預設removeEldestEntry()方法傳回false，也就是不删除元素。

remove()方法

remove裡面設計者也設定了一個鈎子方法：

final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
  ...
      // node即是要删除的節點
      afterNodeRemoval(node);
  ...
}

afterNodeRemoval(Node<K,V> e)方法

在節點被删除之後調用的方法。

void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    // p已删除，前後指針都設定為null，便于GC回收
    p.before = p.after = null;
    // 與afterNodeAccess差不多邏輯
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}

經典的把節點從雙向連結清單中删除的方法。

LinkedHashMap的疊代器

abstract class LinkedHashIterator {
  // 記錄下一個Entry
  LinkedHashMap.Entry<K,V> next;
  // 記錄目前的Entry
  LinkedHashMap.Entry<K,V> current;
  // 記錄是否發生了疊代過程中的修改
  int expectedModCount;

  LinkedHashIterator() {
    // 初始化的時候把head給next
    next = head;
    expectedModCount = modCount;
    current = null;
  }

  public final boolean hasNext() {
    return next != null;
  }

  // 這裡采用的是連結清單方式的周遊方式，有興趣的讀者可以去之前的《深讀源碼-java集合之HashMap源碼分析》看看HashMap的周遊方式
  final LinkedHashMap.Entry<K,V> nextNode() {
    LinkedHashMap.Entry<K,V> e = next;
    if (modCount != expectedModCount)
      throw new ConcurrentModificationException();
    if (e == null)
      throw new NoSuchElementException();
    //記錄目前的Entry
    current = e;
    //直接拿after給next
    next = e.after;
    return e;
  }

  public final void remove() {
    Node<K,V> p = current;
    if (p == null)
      throw new IllegalStateException();
    if (modCount != expectedModCount)
      throw new ConcurrentModificationException();
    current = null;
    K key = p.key;
    removeNode(hash(key), key, null, false, false);
    expectedModCount = modCount;
  }
}

總結

（1）LinkedHashMap繼承自HashMap，具有HashMap的所有特性；

（2）LinkedHashMap内部維護了一個雙向連結清單存儲所有的元素；

（3）如果accessOrder為false，則可以按插入元素的順序周遊元素；

（4）如果accessOrder為true，則可以按通路元素的順序周遊元素；

（5）LinkedHashMap的實作非常精妙，很多方法都是在HashMap中留的鈎子（Hook），直接實作這些Hook就可以實作對應的功能了，并不需要再重寫put()等方法；

（6）預設的LinkedHashMap并不會移除舊元素，如果需要移除舊元素，則需要重寫removeEldestEntry()方法設定移除政策；

（7）LinkedHashMap可以用來實作LRU緩存淘汰政策；

彩蛋

LinkedHashMap如何實作LRU緩存淘汰政策呢？

首先，我們先來看看LRU是個什麼鬼。LRU，Least Recently Used，最近最少使用，也就是優先淘汰最近最少使用的元素。

如果使用LinkedHashMap，我們把accessOrder設定為true是不是就差不多能實作這個政策了呢？答案是肯定的。請看下面的代碼：

package cn.com.sdd.study.list;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @author suidd
 * @name LRUTest
 * @description LRU緩存淘汰政策測試
 * @date 2020/5/9 16:54
 * Version 1.0
 **/
public class LRUTest {
    public static void main(String[] args) {
        // 建立一個隻有5個元素的緩存
        LRU<Integer, Integer> lru = new LRU<>(5, 0.75f);
        lru.put(1, 1);
        lru.put(2, 2);
        lru.put(3, 3);
        lru.put(4, 4);
        lru.put(5, 5);
        lru.put(6, 6);
        lru.put(7, 7);

        System.out.println(lru.get(4));

        lru.put(6, 666);

        // 輸出: {3=3, 5=5, 7=7, 4=4, 6=666}
        // 可以看到最舊的元素被删除了，且最近通路的4被移到了後面
        // 如果LRU構造accessOrder設定為false，則輸出{3=3, 4=4, 5=5, 6=666, 7=7}
        System.out.println(lru);
    }
}

class LRU<K, V> extends LinkedHashMap<K, V> {

    // 儲存緩存的容量
    private int capacity;

    public LRU(int capacity, float loadFactor) {
        //accessOrder：true:按通路順序排序（LRU），false:按插入順序排序；
        super(capacity, loadFactor, true);
        this.capacity = capacity;
    }

    /**
     * 重寫removeEldestEntry()方法設定何時移除舊元素
     *
     * @param eldest
     * @return
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // 當元素個數大于了緩存的容量, 就移除元素
        return size() > this.capacity;
    }
}

參考連結：https://www.cnblogs.com/tong-yuan/p/10639263.html

參考連結：https://www.cnblogs.com/joemsu/p/7787043.html

深讀源碼-java集合之LinkedHashMap源碼分析

簡介

類繼承體系

Entry的繼承關系

Iterator的繼承關系

存儲結構

源碼解析

屬性

内部類

構造方法

get(Object key)方法

afterNodeAccess(Node<K,V> e)方法

put()方法

afterNodeInsertion(boolean evict)方法

remove()方法

afterNodeRemoval(Node<K,V> e)方法

LinkedHashMap的疊代器

總結

彩蛋

繼續閱讀

nginx location中斜線的位置的重要性

資料結構與算法（27）——排序（二）

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

Linux裝置模型（中）之上層容器

scala (3) Function 和 Method