Map 大家族的那點事兒 ( 6 ) ：LinkedHashMap
2018-09-13 來源：importnew
LinkedHashMap繼承HashMap并實現(xiàn)了Map接口，同時具有可預測的迭代順序（按照插入順序排序）。它與HashMap的不同之處在于，維護了一條貫穿其全部Entry的雙向鏈表（因為額外維護了鏈表的關(guān)系，性能上要略差于HashMap，不過集合視圖的遍歷時間與元素數(shù)量成正比，而HashMap是與buckets數(shù)組的長度成正比的），可以認為它是散列表與鏈表的結(jié)合。
/**
* 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，采用訪問排序，否則，采用插入順序
* 默認插入順序（構(gòu)造函數(shù)中默認設置為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實現(xiàn)也繼承自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);
}
}
你也可以通過構(gòu)造函數(shù)來構(gòu)造一個迭代順序為訪問順序（accessOrder設為true）的LinkedHashMap，這個訪問順序指的是按照最近被訪問的Entry的順序進行排序（從最近最少訪問到最近最多訪問）�；谶@點可以簡單實現(xiàn)一個采用LRU（Least Recently Used）策略的緩存。
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
LinkedHashMap復用了HashMap的大部分代碼，所以它的查找實現(xiàn)是非常簡單的，唯一稍微復雜點的操作是保證訪問順序。
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命名格式的函數(shù)嗎？我們之前已經(jīng)在HashMap中見識過了，這些函數(shù)在HashMap中只是一個空實現(xiàn)，是專門用來讓LinkedHashMap重寫實現(xiàn)的hook函數(shù)。
// 在HashMap.removeNode()的末尾處調(diào)用
// 將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()的末尾處調(diào)用
// evict是一個模式標記，如果為false代表buckets數(shù)組處于創(chuàng)建模式
// HashMap.put()函數(shù)對此標記設置為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()沒有調(diào)用此函數(shù)，所以LinkedHashMap重寫了get()
// get()與put()都會調(diào)用afterNodeAccess()來保證訪問順序
// 將e移動到tail，代表最近訪問到的節(jié)點
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處于一個永遠為空的狀態(tài)（每次put()或者putAll()都會刪除頭節(jié)點）。
一個比較合理的實現(xiàn)示例：
protected boolean removeEldestEntry(Map.Entry eldest){
return size() > MAX_SIZE;
}
LinkedHashMap重寫了newNode()等函數(shù)，以初始化或連接節(jié)點到它內(nèi)部的雙向鏈表：
// 鏈接節(jié)點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是頭節(jié)點
if (b == null)
head = dst;
else
b.after = dst;
// src是尾節(jié)點
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數(shù)量成正比，這是因為迭代器直接對雙向鏈表進行迭代，而鏈表中只會含有Entry節(jié)點。迭代的順序是從頭節(jié)點開始一直到尾節(jié)點，插入操作會將新節(jié)點鏈接到尾部，所以保證了插入順序，而訪問順序會通過afterNodeAccess()來保證，訪問次數(shù)越多的節(jié)點越接近尾部。
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(); }
}
標簽： 代碼
版權(quán)申明：本站文章部分自網(wǎng)絡，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。
