LinkedHashMap是HashMap的子類，所以也具備HashMap的諸多特性痹升。不同的是建炫，LinkedHashMap還維護(hù)了一個雙向鏈表，以保證通過Iterator遍歷時順序與插入順序一致疼蛾。除此之外肛跌，它還支持Access Order，即按照元素被訪問的順序來排序察郁，我們熟知的LRUCache底層就依賴于此衍慎。以下是文檔中需要我們注意的點：
Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). Note that insertion order is not affected if a key is re-inserted into the map.
A special LinkedHashMap(int,float,boolean) constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order). This kind of map is well-suited to building LRU caches.
The removeEldestEntry(Map.Entry) method may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map.
Note, however, that the penalty for choosing an excessively high value for initial capacity is less severe for this class than for HashMap, as iteration times for this class are unaffected by capacity.
下面我們就從構(gòu)造函數(shù)和成員變量開始分析其具體實現(xiàn)。
構(gòu)造函數(shù)與成員變量
成員變量
在分析成員變量前皮钠，我們先看下其存儲元素的結(jié)構(gòu)稳捆。
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);
}
}
這個Entry在HashMap中被引用過，主要是為了能讓LinkedHashMap也支持樹化麦轰。在這里則是用來存儲元素乔夯。
// 雙向鏈表的頭，用作AccessOrder時也是最老的元素
transient LinkedHashMap.Entry<K,V> head;
// 雙向鏈表的尾款侵，用作AccessOrder時也是最新的元素
transient LinkedHashMap.Entry<K,V> tail;
// true則為訪問順序末荐，false則為插入順序
final boolean accessOrder;
構(gòu)造函數(shù)
關(guān)于LinkedHashMap的構(gòu)造函數(shù)我們只關(guān)注一個，其他的都和HashMap類似新锈，只是把accessOrder設(shè)置為了false甲脏。在上邊的文檔說過，initialCapacity并沒有在HashMap中那般重要妹笆，因為鏈表不需要像數(shù)組那樣必須先聲明足夠的空間块请。下面這個構(gòu)造函數(shù)是支持訪問順序的。
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
重要方法
LinkedHashMap并沒有再實現(xiàn)一整套增刪改查的方法晾浴，而是通過復(fù)寫HashMap在此過程中定義的幾個方法來實現(xiàn)的负乡。對此不熟悉的可以查看文末關(guān)于HashMap分析的文章，或者對照HashMap的源碼來看脊凰。
插入一個元素
HashMap在插入時，調(diào)用了newNode來新建一個節(jié)點茂腥，或者是通過replacementNode來替換值狸涌。在樹化時也有兩個對應(yīng)的方法，分別是newTreeNode和replacementTreeNode最岗。完成之后帕胆，還調(diào)用了afterNodeInsertion方法，這個方法允許我們在插入完成后做些事情般渡，默認(rèn)是空實現(xiàn)懒豹。
為了方便分析芙盘，我們會對比HashMap中的實現(xiàn)與LinkedHashMap的實現(xiàn)，來摸清它是如何做的脸秽。
// HashMap中的實現(xiàn)
Node<K, V> newNode(int hash, K key, V value, Node<K, V> next) {
return new Node<>(hash, key, value, next);
}
// LinkedHashMap中的實現(xiàn)
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;
}
// HashMap中的實現(xiàn)
Node<K, V> replacementNode(Node<K, V> p, Node<K, V> next) {
return new Node<>(p.hash, p.key, p.value, next);
}
// LinkedHashMap中的實現(xiàn)
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;
}
// newTreeNode和replacementTreeNode和此類似
通過以上對比儒老，可以發(fā)現(xiàn)，LinkedHashMap在新增時记餐，調(diào)用了linkNodeLast驮樊，再替換時調(diào)用了transferLinks。以下是這兩個方法的實現(xiàn)片酝。
// 就是將元素掛在鏈尾
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;
if (b == null)
head = dst;
else
b.after = dst;
if (a == null)
tail = dst;
else
a.before = dst;
}
最后我們看下afterNodeInsertion做了哪些事情吧：
// evict在HashMap中說過囚衔，為false表示是創(chuàng)建階段
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
// 不是創(chuàng)建階段
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
// 自動刪除最老的元素，也就是head元素
removeNode(hash(key), key, null, false, true);
}
}
removeEldestEntry是當(dāng)想要在插入元素時自動刪除最老的元素時需要復(fù)寫的方法雕沿。其默認(rèn)實現(xiàn)如下：
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
查詢
因為要支持訪問順序练湿，所以獲取元素的方法和HashMap也有所不同。下面我們看下其實現(xiàn)：
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
// 數(shù)據(jù)被訪問审轮，需要將其移動到末尾
afterNodeAccess(e);
return e.value;
}
getNode方法是在HashMap中實現(xiàn)的鞠鲜，所以這是包裝了一下HashMap的方法，并添加了一個afterNodeAccess断国，其實現(xiàn)如下：
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// e元素不在末尾
if (accessOrder && (last = tail) != e) {
// p是e贤姆，b是前一個元素，a是后一個元素
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// e要放在末尾稳衬，所以沒有after
p.after = null;
// 把e去掉霞捡，把b和a接起來
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
//把e接在末尾
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
關(guān)于LinkedHashMap的分析就到這里了，其他關(guān)于Iterator的內(nèi)容都和Collection是大同小異的薄疚，感興趣的可以去查看相關(guān)源碼碧信。
下一篇：Java集合源碼分析之Set概述
我是飛機醬，如果您喜歡我的文章街夭，可以關(guān)注我~
編程之路砰碴，道阻且長。唯板丽，路漫漫其修遠(yuǎn)兮呈枉，吾將上下而求索。
