Map 大家族的那點事兒 ( 6 ) ：LinkedHashMap
（點擊
上方公眾號
，可快速關注）
來源：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<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> tail;
/**
* 迭代順序模式的標記位，如果為true，採用訪問排序，否則，採用插入順序
* 默認插入順序（構造函數中默認設置為false）
*/
final boolean accessOrder;
/**
* Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> 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<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);
}
}
你也可以通過構造函數來構造一個迭代順序為訪問順序（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<K,V> 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<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;
}
// 在HashMap.putVal()的末尾處調用
// evict是一個模式標記，如果為false代表buckets數組處於創建模式
// HashMap.put()函數對此標記設置為true
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> 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<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
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;
}
}
注意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<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
// 用dst替換掉src
private void transferLinks(LinkedHashMap.Entry<K,V> src,
LinkedHashMap.Entry<K,V> dst) {
LinkedHashMap.Entry<K,V> b = dst.before = src.before;
LinkedHashMap.Entry<K,V> 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<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);
linkNodeLast(p);
return p;
}
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
LinkedHashMap.Entry<K,V> t =
new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);
transferLinks(q, t);
return t;
}
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;
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
transferLinks(q, t);
return t;
}
遍歷LinkedHashMap所需要的時間與Entry數量成正比，這是因為迭代器直接對雙向鏈表進行迭代，而鏈表中只會含有Entry節點。迭代的順序是從頭節點開始一直到尾節點，插入操作會將新節點鏈接到尾部，所以保證了插入順序，而訪問順序會通過afterNodeAccess()來保證，訪問次數越多的節點越接近尾部。
abstract class LinkedHashIterator {
LinkedHashMap.Entry<K,V> next;
LinkedHashMap.Entry<K,V> current;
int expectedModCount;
LinkedHashIterator() {
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;
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;
}
}
final class LinkedKeyIterator extends LinkedHashIterator
implements Iterator<K> {
public final K next() { return nextNode().getKey(); }
}
final class LinkedValueIterator extends LinkedHashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
final class LinkedEntryIterator extends LinkedHashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
系列
Map 大家族的那點事兒 ( 1 ) ：Map
Map 大家族的那點事兒 ( 2 ) ：AbstractMap
Map 大家族的那點事兒 ( 3 ) ：TreeMap
Map 大家族的那點事兒 ( 4 ) ：HashMap
Map 大家族的那點事兒 ( 5 ) ：WeakHashMap
【關於投稿】
如果大家有原創好文投稿，請直接給公號發送留言。
① 留言格式：
【投稿】+《 文章標題》+ 文章鏈接
② 示例：
【投稿】《不要自稱是程序員，我十多年的 IT 職場總結》：http://blog.jobbole.com/94148/
③ 最後請附上您的個人簡介哈~
看完本文有收穫？請轉發分享給更多人
關注「ImportNew」，提升Java技能
※深入 Spring Boot ：實現對 Fat Jar jsp 的支持
※Map 大家族的那點事兒 ( 5 ) ：WeakHashMap
TAG:ImportNew |