知識星球（點選上方公眾號，可快速關註）
來源：SylvanasSun’s Blog ，
sylvanassun.github.io/2018/03/16/2018-03-16-map_family/
LinkedHashMap繼承HashMap並實現了Map介面，同時具有可預測的迭代順序（按照插入順序排序）。它與HashMap的不同之處在於，維護了一條貫穿其全部Entry的雙向連結串列（因為額外維護了連結串列的關係，效能上要略差於HashMap，不過集合檢視的遍歷時間與元素數量成正比，而HashMap是與buckets陣列的長度成正比的），可以認為它是散串列與連結串列的結合。
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMap.Entry
head; /**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMap.Entry
tail; /**
* 迭代順序樣式的標記位，如果為true，採用訪問排序，否則，採用插入順序
* 預設插入順序（建構式中預設設定為false）
*/
final boolean accessOrder;
/**
* Constructs an empty insertion-ordered LinkedHashMap instance
* with the default initial capacity (16) and load factor (0.75).
*/
public LinkedHashMap() {
super();
accessOrder = false;
}
LinkedHashMap的Entry實現也繼承自HashMap，只不過多了指向前後的兩個指標。
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
static class Entry
extends HashMap.Node { Entry
before, after; Entry(int hash, K key, V value, Node
next) { super(hash, key, value, next);
}
}
你也可以透過建構式來構造一個迭代順序為訪問順序（accessOrder設為true）的LinkedHashMap，這個訪問順序指的是按照最近被訪問的Entry的順序進行排序（從最近最少訪問到最近最多訪問）。基於這點可以簡單實現一個採用LRU（Least Recently Used）策略的快取。
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
LinkedHashMap復用了HashMap的大部分程式碼，所以它的查詢實現是非常簡單的，唯一稍微複雜點的操作是保證訪問順序。
public V get(Object key) {
Node
e; if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
還記得這些afterNodeXXXX命名格式的函式嗎？我們之前已經在HashMap中見識過了，這些函式在HashMap中只是一個空實現，是專門用來讓LinkedHashMap重寫實現的hook函式。
// 在HashMap.removeNode()的末尾處呼叫
// 將e從LinkedHashMap的雙向連結串列中刪除
void afterNodeRemoval(Node
e) { // unlink LinkedHashMap.Entry
p = (LinkedHashMap.Entry
)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;
}
// 在HashMap.putVal()的末尾處呼叫
// evict是一個樣式標記，如果為false代表buckets陣列處於建立樣式
// HashMap.put()函式對此標記設定為true
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry
first; // LinkedHashMap.removeEldestEntry()永遠傳回false
// 避免了最年長元素被刪除的可能（就像一個普通的Map一樣）
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
// HashMap.get()沒有呼叫此函式，所以LinkedHashMap重寫了get()
// get()與put()都會呼叫afterNodeAccess()來保證訪問順序
// 將e移動到tail，代表最近訪問到的節點
void afterNodeAccess(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;
}
}
註意removeEldestEntry()預設永遠傳回false，這時它的行為與普通的Map無異。如果你把removeEldestEntry()重寫為永遠傳回true，那麼就有可能使LinkedHashMap處於一個永遠為空的狀態（每次put()或者putAll()都會刪除頭節點）。
一個比較合理的實現示例：
protected boolean removeEldestEntry(Map.Entry eldest){
return size() > MAX_SIZE;
}
LinkedHashMap重寫了newNode()等函式，以初始化或連線節點到它內部的雙向連結串列：
// 連結節點p到連結串列尾部（或初始化連結串列）
private void linkNodeLast(LinkedHashMap.Entry
p) { LinkedHashMap.Entry
last = tail; tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
// 用dst替換掉src
private void transferLinks(LinkedHashMap.Entry
src, LinkedHashMap.Entry
dst) { LinkedHashMap.Entry
b = dst.before = src.before; LinkedHashMap.Entry
a = dst.after = src.after; // src是頭節點
if (b == null)
head = dst;
else
b.after = dst;
// src是尾節點
if (a == null)
tail = dst;
else
a.before = dst;
}
Node
newNode(int hash, K key, V value, Node e) { LinkedHashMap.Entry
p = new LinkedHashMap.Entry
(hash, key, value, e); linkNodeLast(p);
return p;
}
Node
replacementNode(Node p, Node next) { LinkedHashMap.Entry
q = (LinkedHashMap.Entry )p; LinkedHashMap.Entry
t = new LinkedHashMap.Entry
(q.hash, q.key, q.value, next); transferLinks(q, t);
return t;
}
TreeNode
newTreeNode(int hash, K key, V value, Node next) { TreeNode
p = new TreeNode (hash, key, value, next); linkNodeLast(p);
return p;
}
TreeNode
replacementTreeNode(Node p, Node next) { LinkedHashMap.Entry
q = (LinkedHashMap.Entry )p; TreeNode
t = new TreeNode (q.hash, q.key, q.value, next); transferLinks(q, t);
return t;
}
遍歷LinkedHashMap所需要的時間與Entry數量成正比，這是因為迭代器直接對雙向連結串列進行迭代，而連結串列中只會含有Entry節點。迭代的順序是從頭節點開始一直到尾節點，插入操作會將新節點連結到尾部，所以保證了插入順序，而訪問順序會透過afterNodeAccess()來保證，訪問次數越多的節點越接近尾部。
abstract class LinkedHashIterator {
LinkedHashMap.Entry
next; LinkedHashMap.Entry
current; int expectedModCount;
LinkedHashIterator() {
next = head;
expectedModCount = modCount;
current = null;
}
public final boolean hasNext() {
return next != null;
}
final LinkedHashMap.Entry
nextNode() { LinkedHashMap.Entry
e = next; if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
next = e.after;
return e;
}
public final void remove() {
Node
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;
}
}
final class LinkedKeyIterator extends LinkedHashIterator
implements Iterator
{ public final K next() { return nextNode().getKey(); }
}
final class LinkedValueIterator extends LinkedHashIterator
implements Iterator
{ public final V next() { return nextNode().value; }
}
final class LinkedEntryIterator extends LinkedHashIterator
implements Iterator
> { public final Map.Entry
next() { return nextNode(); } }
系列
【關於投稿】
如果大家有原創好文投稿，請直接給公號傳送留言。
① 留言格式：
【投稿】+《 文章標題》+ 文章連結
② 示例：
【投稿】《不要自稱是程式員，我十多年的 IT 職場總結》：http://blog.jobbole.com/94148/
③ 最後請附上您的個人簡介哈~
看完本文有收穫？請轉發分享給更多人
關註「ImportNew」，提升Java技能
