LinkedHashMap 原始碼解析
highlight: atom-one-dark theme: vuepress
這是我參與11月更文挑戰的第10天，活動詳情檢視：2021最後一次更文挑戰。
HashMap元素插入是無序的，為了讓遍歷順序和插入順序一致，我們可以使用LinkedHashMap，其內部維護了一個雙向連結串列來儲存元素順序，並且可以通過accessOrder屬性控制遍順序為插入順序或者為訪問順序。
類結構
LinkedHashMap類層級關係圖：
LinkedHashMap繼承自HashMap，大部分方法都是直接使用HashMap的。接著檢視成員變數：
```java
// 雙向連結串列的頭部節點（最早插入的，年紀最大的節點）
transient LinkedHashMap.Entry
// 雙向連結串列的尾部節點（最新插入的，年紀最小的節點）
transient LinkedHashMap.Entry
// 用於控制訪問順序，為true時，按插入順序；為false時，按訪問順序 final boolean accessOrder; ```
head和tail使用transient修飾，原因在介紹HashMap原始碼的時候分析過。
LinkedHashMap繼承自HashMap，所以內部儲存資料的方式和HashMap一樣，使用陣列加連結串列（紅黑樹）的結構儲存資料，LinkedHashMap和HashMap相比，額外的維護了一個雙向連結串列，用於儲存節點的順序。這個雙向連結串列的型別為LinkedHashMap.Entry：
java
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);
}
}
LinkedHashMap.Entry類層級關係圖：
LinkedHashMap.Entry繼承自HashMap的Node類，新增了before和after屬性，用於維護前繼和後繼節點，以此形成雙向連結串列。
建構函式
LinkedHashMap的建構函式其實沒什麼特別的，就是呼叫父類的構造器初始化HashMap的過程，只不過額外多了初始化LinkedHashMap的accessOrder屬性的操作：
```java 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; } ```
簡單使用
在分析LinkedHashMap方法實現之前，我們先通過例子感受下LinkedHashMap的特性：
```java
LinkedHashMap
map.get("6"); System.out.println(map);
map.put("4", "d"); System.out.println(map);
//{1=a, 6=b, 3=c} //{1=a, 6=b, 3=c} //{1=a, 6=b, 3=c, 4=d} ```
可以看到元素的輸出順序就是我們插入的順序。
將accessOrder屬性改為true：
java
{1=a, 6=b, 3=c}
{1=a, 3=c, 6=b}
{1=a, 3=c, 6=b, 4=d}
可以看到，一開始輸出{1=a, 6=b, 3=c}。當我們通過get方法訪問key為6的鍵值對後，程式輸出{1=a, 3=c, 6=b}。也就是說，當accessOrder屬性為true時，元素按訪問順序排列，即最近訪問的元素會被移動到雙向列表的末尾。所謂的“訪問”並不是只有get方法，符合“訪問”一詞的操作有put、putIfAbsent、get、getOrDefault、compute、computeIfAbsent、computeIfPresent和merge方法。
下面我們通過方法原始碼的分析就能清楚地知道LinkedHashMap是如何控制元素訪問順序的。
方法解析
put(K key, V value)
LinkedHashMap並沒有重寫put(K key, V value)方法，直接使用HashMap的put(K key, V value)方法。那麼問題就來了，既然LinkedHashMap沒有重寫put(K key, V value)，那它是如何通過內部的雙向連結串列維護元素順序的？我們檢視put(K key, V value)方法原始碼就能發現原因（因為put(K key, V value)原始碼在Java-HashMap底層實現原理一節中已經剖析過，所以下面我們只在和LinkedHashMap功能相關的程式碼上添加註釋）： ```java public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node
newNode方法用於建立連結串列節點，LinkedHashMap重寫了newNode方法：
```java
Node
private void linkNodeLast(LinkedHashMap.Entry
可以看到，對於LinkedHashMap例項，put操作內部建立的的節點型別為LinkedHashMap.Entry，除了往HashMap內部table插入資料外，還往LinkedHashMap的雙向連結串列尾部插入了資料。
如果是往紅黑樹結構插入資料，那麼put將呼叫putTreeVal方法往紅黑樹裡插入節點，putTreeVal方法內部通過newTreeNode方法建立樹節點。LinkedHashMap重寫了newTreeNode方法：
java
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
// 建立TreeNode例項
TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
// 將新節點放入LinkedHashMap維護的雙向連結串列尾部
linkNodeLast(p);
return p;
}
節點型別為TreeNode，那麼這個型別是在哪裡定義的呢？其實TreeNode為HashMap裡定義的，檢視其原始碼：
java
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
......
}
TreeNode繼承自LinkedHashMap.Entry：
所以TreeNode也包含before和after屬性，即使插入的節點型別為TreeNode，依舊可以用LinkedHashMap雙向連結串列維護節點順序。
在put方法中，如果插入的key已經存在的話，還會執行afterNodeAccess操作，該方法在HashMap中為空方法：
java
void afterNodeAccess(Node<K,V> p) { }
afterNodeAccess方法顧名思義，就是當節點被訪問後執行某些操作。LinkedHashMap重寫了這個方法：
java
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// 如果accessOrder屬性為true，並且當前節點不是雙向連結串列的尾節點的話執行if內邏輯
if (accessOrder && (last = tail) != e) {
// 這部分邏輯也很好理解，就是將當前節點移動到雙向連結串列的尾部，並且改變相關節點的前繼後繼關係
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)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;
}
}
所以當accessOrder為true時候，呼叫LinkedHashMap的put方法，插入相同key值的鍵值對時，該鍵值對會被移動到尾部：
```java
LinkedHashMap
//{1=a, 6=b, 3=c} //{1=a, 3=c, 6=b} ```
在put方法尾部，還呼叫了afterNodeInsertion方法，方法顧名思義，用於插入節點後執行某些操作，該方法在HashMap中也是空方法：
java
void afterNodeInsertion(boolean evict) { }
LinkedHashMap重寫了該方法：
```java
// 這裡evict為true
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry
protected boolean removeEldestEntry(Map.Entry
基於這個特性，我們可以通過繼承LinkedHashMap的方式重寫removeEldestEntry方法，以此實現LRU，下面再做實現。
你可能會問，removeNode刪除的是HashMap的table中的節點，那麼用於維護節點順序的雙向連結串列不是也應該刪除頭部節點嗎？為什麼上面程式碼沒有看到這部分操作？其實當你檢視removeNode方法的原始碼就能看到這部分操作了：
java
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
// 節點刪除後，執行後續操作
afterNodeRemoval(node);
return node;
}
}
return null;
}
afterNodeRemoval方法顧名思義，用於節點刪除後執行後續操作。該方法在HashMap中為空方法：
java
void afterNodeRemoval(Node<K,V> p) { }
LinkedHashMap重寫了該方法：
java
// 改變節點的前繼後繼引用
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;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
通過該方法，我們就從LinkedHashMap的雙向連結串列中刪除了頭部結點。
其實通過put方法我們就已經搞清楚了LinkedHashMap內部是如何通過雙向連結串列維護鍵值對順序的，但為了讓文章更飽滿一點，下面繼續分析幾個方法原始碼。
get(Object key)
LinkedHashMap重寫了HashMap的get方法：
java
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
// 多了這一步操作，當accessOrder屬性為true時，將key對應的鍵值對節點移動到雙向列表的尾部
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
remove(Object key)
LinkedHashMap沒有重寫remove方法，檢視HashMap的remove方法：
java
public V remove(Object key) {
Node<K,V> e;
// 呼叫removeNode刪除節點，removeNode方法內部呼叫了afterNodeRemoval方法，上面介紹put
// 方法時分析過了，所以不再贅述
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
迭代器
既然LinkedHashMap內部通過雙向連結串列維護鍵值對順序的話，那麼我們可以猜測遍歷LinkedHashMap實際就是遍歷LinkedHashMap維護的雙向連結串列：
檢視LinkedHashMap類entrySet方法的實現：
```java
public Set
final class LinkedEntrySet extends AbstractSet
// LinkedEntryIterator繼承自LinkedHashIterator
final class LinkedEntryIterator extends LinkedHashIterator
implements Iterator
abstract class LinkedHashIterator {
LinkedHashMap.Entry
LinkedHashIterator() {
// 初始化時，將雙向連結串列的頭部節點賦值給next，說明遍歷LinkedHashMap是從
// LinkedHashMap的雙向連結串列頭部開始的
next = head;
// 同樣也有快速失敗的特性
expectedModCount = modCount;
current = null;
}
public final boolean hasNext() {
return next != null;
}
final LinkedHashMap.Entry<K,V> nextNode() {
LinkedHashMap.Entry<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
// 不斷獲取當前節點的after節點，遍歷
next = e.after;
return e;
}
......
} ```
上述程式碼符合我們的猜測。
LRU簡單實現
LRU（Least Recently Used）指的是最近最少使用，是一種快取淘汰演算法，哪個最近不怎麼用了就淘汰掉。
我們知道LinkedHashMap內的removeEldestEntry方法固定返回false，並不會執行元素刪除操作，所以我們可以通過繼承LinkedHashMap，重寫removeEldestEntry方法來實現LRU。
假如我們現在有如下需求：
用LinkedHashMap實現快取，快取最多隻能儲存5個元素，當元素個數超過5的時候，刪除（淘汰）那些最近最少使用的資料，僅儲存熱點資料。
新建LRUCache類，繼承LinkedHashMap：
```java
public class LRUCache
/**
* 快取允許的最大容量
*/
private final int maxSize;
public LRUCache(int initialCapacity, int maxSize) {
// accessOrder必須為true
super(initialCapacity, 0.75f, true);
this.maxSize = maxSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
// 當鍵值對個數超過最大容量時，返回true，觸發刪除操作
return size() > maxSize;
}
public static void main(String[] args) {
LRUCache<String, String> cache = new LRUCache<>(5, 5);
cache.put("1", "a");
cache.put("2", "b");
cache.put("3", "c");
cache.put("4", "d");
cache.put("5", "e");
cache.put("6", "f");
System.out.println(cache);
}
}
// {2=b, 3=c, 4=d, 5=e, 6=f} ```
可以看到最早插入的1=a已經被刪除了。
通過LinkedHashMap實現LRU還是挺常見的，比如logback框架的LRUMessageCache：
```java
class LRUMessageCache extends LinkedHashMap
private static final long serialVersionUID = 1L;
final int cacheSize;
LRUMessageCache(int cacheSize) {
super((int) (cacheSize * (4.0f / 3)), 0.75f, true);
if (cacheSize < 1) {
throw new IllegalArgumentException("Cache size cannot be smaller than 1");
}
this.cacheSize = cacheSize;
}
int getMessageCountAndThenIncrement(String msg) {
// don't insert null elements
if (msg == null) {
return 0;
}
Integer i;
// LinkedHashMap is not LinkedHashMap. See also LBCLASSIC-255
synchronized (this) {
i = super.get(msg);
if (i == null) {
i = 0;
} else {
i = i + 1;
}
super.put(msg, i);
}
return i;
}
// called indirectly by get() or put() which are already supposed to be
// called from within a synchronized block
protected boolean removeEldestEntry(Map.Entry eldest) {
return (size() > cacheSize);
}
@Override
synchronized public void clear() {
super.clear();
}
} ```