想看我更多文章:【張旭童的博客】http://blog.csdn.net/zxt0601
想來gayhub和我gaygayup:【mcxtzhang的Github主頁】https://github.com/mcxtzhang
1 概述
在上文中仍秤，我們已經(jīng)聊過了HashMap,本篇是基于上文的基礎之上无牵。所以如果沒看過上文关划，請先閱讀面試必備：HashMap源碼解析（JDK8）
本文將從幾個常用方法下手煤蹭，來閱讀LinkedHashMap的源碼宰缤。
按照從構(gòu)造方法->常用API（增、刪衍腥、改绪穆、查）的順序來閱讀源碼，并會講解閱讀方法中涉及的一些變量的意義蓖扑。了解LinkedHashMap的特點唉铜、適用場景。
如果本文中有不正確的結(jié)論律杠、說法打毛，請大家提出和我討論，共同進步俩功，謝謝幻枉。
2 概要
概括的說，LinkedHashMap 是一個關聯(lián)數(shù)組诡蜓、哈希表熬甫，它是線程不安全的，允許key為null,value為null蔓罚。
它繼承自HashMap椿肩，實現(xiàn)了Map<K,V>接口瞻颂。其內(nèi)部還維護了一個雙向鏈表，在每次插入數(shù)據(jù)郑象，或者訪問贡这、修改數(shù)據(jù)時，會增加節(jié)點厂榛、或調(diào)整鏈表的節(jié)點順序盖矫。以決定迭代時輸出的順序。
默認情況击奶，遍歷時的順序是按照插入節(jié)點的順序辈双。這也是其與HashMap最大的區(qū)別。
也可以在構(gòu)造時傳入accessOrder參數(shù)柜砾，使得其遍歷順序按照訪問的順序輸出湃望。
因繼承自HashMap,所以HashMap上文分析的特點，除了輸出無序痰驱，其他LinkedHashMap都有证芭，比如擴容的策略，哈希桶長度一定是2的N次方等等担映。
LinkedHashMap在實現(xiàn)時檩帐，就是重寫override了幾個方法。以滿足其輸出序列有序的需求另萤。
示例代碼:
根據(jù)這段實例代碼湃密，先從現(xiàn)象看一下LinkedHashMap的特征：
在每次插入數(shù)據(jù)，或者訪問四敞、修改數(shù)據(jù)時泛源，會增加節(jié)點、或調(diào)整鏈表的節(jié)點順序忿危。以決定迭代時輸出的順序达箍。
Map<String, String> map = new LinkedHashMap<>();
map.put("1", "a");
map.put("2", "b");
map.put("3", "c");
map.put("4", "d");
Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
System.out.println("以下是accessOrder=true的情況:");
map = new LinkedHashMap<String, String>(10, 0.75f, true);
map.put("1", "a");
map.put("2", "b");
map.put("3", "c");
map.put("4", "d");
map.get("2");//2移動到了內(nèi)部的鏈表末尾
map.get("4");//4調(diào)整至末尾
map.put("3", "e");//3調(diào)整至末尾
map.put(null, null);//插入兩個新的節(jié)點 null
map.put("5", null);//5
iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
輸出：
1=a
2=b
3=c
4=d
以下是accessOrder=true的情況:
1=a
2=b
4=d
3=e
null=null
5=null
3 節(jié)點
LinkedHashMap的節(jié)點Entry<K,V>繼承自HashMap.Node<K,V>，在其基礎上擴展了一下铺厨。改成了一個雙向鏈表缎玫。
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);
}
}
同時類里有兩個成員變量head tail,分別指向內(nèi)部雙向鏈表的表頭、表尾解滓。
//雙向鏈表的頭結(jié)點
transient LinkedHashMap.Entry<K,V> head;
//雙向鏈表的尾節(jié)點
transient LinkedHashMap.Entry<K,V> tail;
4 構(gòu)造函數(shù)
//默認是false赃磨，則迭代時輸出的順序是插入節(jié)點的順序。若為true洼裤，則輸出的順序是按照訪問節(jié)點的順序邻辉。
//為true時，可以在這基礎之上構(gòu)建一個LruCach
final boolean accessOrder;
public LinkedHashMap() {
super();
accessOrder = false;
}
//指定初始化時的容量，
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
//指定初始化時的容量值骇，和擴容的加載因子
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
//指定初始化時的容量莹菱，和擴容的加載因子，以及迭代輸出節(jié)點的順序
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
//利用另一個Map 來構(gòu)建吱瘩，
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
//該方法上文分析過道伟，批量插入一個map中的所有數(shù)據(jù)到 本集合中。
putMapEntries(m, false);
}
小結(jié)：
構(gòu)造函數(shù)和HashMap相比使碾，就是增加了一個accessOrder參數(shù)蜜徽。用于控制迭代時的節(jié)點順序。
5 增
LinkedHashMap并沒有重寫任何put方法部逮。但是其重寫了構(gòu)建新節(jié)點的newNode()方法.
newNode()會在HashMap的putVal()方法里被調(diào)用娜汁，putVal()方法會在批量插入數(shù)據(jù)putMapEntries(Map<? extends K, ? extends V> m, boolean evict)或者插入單個數(shù)據(jù)public V put(K key, V value)時被調(diào)用嫂易。
LinkedHashMap重寫了newNode(),在每次構(gòu)建新節(jié)點時兄朋，通過linkNodeLast(p);將新節(jié)點鏈接在內(nèi)部雙向鏈表的尾部。
//在構(gòu)建新節(jié)點時怜械，構(gòu)建的是`LinkedHashMap.Entry` 不再是`Node`.
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;
}
//將新增的節(jié)點颅和，連接在鏈表的尾部
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
//集合之前是空的
if (last == null)
head = p;
else {//將新節(jié)點連接在鏈表的尾部
p.before = last;
last.after = p;
}
}
以及HashMap專門預留給LinkedHashMap的afterNodeAccess() afterNodeInsertion() afterNodeRemoval() 方法。
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
//回調(diào)函數(shù)缕允，新節(jié)點插入之后回調(diào) 峡扩， 根據(jù)evict 和 判斷是否需要刪除最老插入的節(jié)點。如果實現(xiàn)LruCache會用到這個方法障本。
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
//LinkedHashMap 默認返回false 則不刪除節(jié)點
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
//LinkedHashMap 默認返回false 則不刪除節(jié)點教届。 返回true 代表要刪除最早的節(jié)點。通常構(gòu)建一個LruCache會在達到Cache的上限是返回true
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
void afterNodeInsertion(boolean evict)以及boolean removeEldestEntry(Map.Entry<K,V> eldest)是構(gòu)建LruCache需要的回調(diào)驾霜，在LinkedHashMap里可以忽略它們案训。
6 刪
LinkedHashMap也沒有重寫remove()方法，因為它的刪除邏輯和HashMap并無區(qū)別粪糙。
但它重寫了afterNodeRemoval()這個回調(diào)方法强霎。該方法會在Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable)方法中回調(diào)，removeNode()會在所有涉及到刪除節(jié)點的方法中被調(diào)用蓉冈，上文分析過城舞，是刪除節(jié)點操作的真正執(zhí)行者。
//在刪除節(jié)點e時寞酿，同步將e從雙向鏈表上刪除
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//待刪除節(jié)點 p 的前置后置節(jié)點都置空
p.before = p.after = null;
//如果前置節(jié)點是null家夺，則現(xiàn)在的頭結(jié)點應該是后置節(jié)點a
if (b == null)
head = a;
else//否則將前置節(jié)點b的后置節(jié)點指向a
b.after = a;
//同理如果后置節(jié)點時null ，則尾節(jié)點應是b
if (a == null)
tail = b;
else//否則更新后置節(jié)點a的前置節(jié)點為b
a.before = b;
}
7 查
LinkedHashMap重寫了get()和getOrDefault()方法：
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;
}
public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return defaultValue;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
對比HashMap中的實現(xiàn),LinkedHashMap只是增加了在成員變量(構(gòu)造函數(shù)時賦值)accessOrder為true的情況下伐弹，要去回調(diào)void afterNodeAccess(Node<K,V> e)函數(shù)秦踪。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
在afterNodeAccess()函數(shù)中，會將當前被訪問到的節(jié)點e，移動至內(nèi)部的雙向鏈表的尾部椅邓。
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;//原尾節(jié)點
//如果accessOrder 是true 柠逞，且原尾節(jié)點不等于e
if (accessOrder && (last = tail) != e) {
//節(jié)點e強轉(zhuǎn)成雙向鏈表節(jié)點p
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//p現(xiàn)在是尾節(jié)點， 后置節(jié)點一定是null
p.after = null;
//如果p的前置節(jié)點是null景馁，則p以前是頭結(jié)點板壮，所以更新現(xiàn)在的頭結(jié)點是p的后置節(jié)點a
if (b == null)
head = a;
else//否則更新p的前直接點b的后置節(jié)點為 a
b.after = a;
//如果p的后置節(jié)點不是null，則更新后置節(jié)點a的前置節(jié)點為b
if (a != null)
a.before = b;
else//如果原本p的后置節(jié)點是null合住，則p就是尾節(jié)點绰精。 此時 更新last的引用為 p的前置節(jié)點b
last = b;
if (last == null) //原本尾節(jié)點是null 則，鏈表中就一個節(jié)點
head = p;
else {//否則 更新 當前節(jié)點p的前置節(jié)點為 原尾節(jié)點last透葛， last的后置節(jié)點是p
p.before = last;
last.after = p;
}
//尾節(jié)點的引用賦值成p
tail = p;
//修改modCount笨使。
++modCount;
}
}
值得注意的是，afterNodeAccess()函數(shù)中僚害，會修改modCount,因此當你正在accessOrder=true的模式下,迭代LinkedHashMap時硫椰，如果同時查詢訪問數(shù)據(jù)，也會導致fail-fast萨蚕，因為迭代的順序已經(jīng)改變靶草。
7.2 containsValue
它重寫了該方法，相比HashMap的實現(xiàn)岳遥，更為高效奕翔。
public boolean containsValue(Object value) {
//遍歷一遍鏈表，去比較有沒有value相等的節(jié)點浩蓉，并返回
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
V v = e.value;
if (v == value || (value != null && value.equals(v)))
return true;
}
return false;
}
對比HashMap派继，是用兩個for循環(huán)遍歷，相對低效捻艳。
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
8 遍歷
重寫了entrySet()如下：
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
//返回LinkedEntrySet
return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
}
final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
public final Iterator<Map.Entry<K,V>> iterator() {
return new LinkedEntryIterator();
}
}
最終的EntryIterator:
final class LinkedEntryIterator extends LinkedHashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
abstract class LinkedHashIterator {
//下一個節(jié)點
LinkedHashMap.Entry<K,V> next;
//當前節(jié)點
LinkedHashMap.Entry<K,V> current;
int expectedModCount;
LinkedHashIterator() {
//初始化時驾窟，next 為 LinkedHashMap內(nèi)部維護的雙向鏈表的扁頭
next = head;
//記錄當前modCount，以滿足fail-fast
expectedModCount = modCount;
//當前節(jié)點為null
current = null;
}
//判斷是否還有next
public final boolean hasNext() {
//就是判斷next是否為null讯泣，默認next是head 表頭
return next != null;
}
//nextNode() 就是迭代器里的next()方法 纫普。
//該方法的實現(xiàn)可以看出，迭代LinkedHashMap好渠，就是從內(nèi)部維護的雙鏈表的表頭開始循環(huán)輸出昨稼。
final LinkedHashMap.Entry<K,V> nextNode() {
//記錄要返回的e。
LinkedHashMap.Entry<K,V> e = next;
//判斷fail-fast
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
//如果要返回的節(jié)點是null拳锚，異常
if (e == null)
throw new NoSuchElementException();
//更新當前節(jié)點為e
current = e;
//更新下一個節(jié)點是e的后置節(jié)點
next = e.after;
//返回e
return e;
}
//刪除方法 最終還是調(diào)用了HashMap的removeNode方法
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;
}
}
值得注意的就是：nextNode() 就是迭代器里的next()方法 假栓。
該方法的實現(xiàn)可以看出，迭代LinkedHashMap霍掺，就是從內(nèi)部維護的雙鏈表的表頭開始循環(huán)輸出匾荆。
而雙鏈表節(jié)點的順序在LinkedHashMap的增拌蜘、刪、改牙丽、查時都會更新简卧。以滿足按照插入順序輸出，還是訪問順序輸出烤芦。
總結(jié)
LinkedHashMap相對于HashMap的源碼比举娩，是很簡單的。因為大樹底下好乘涼构罗。它繼承了HashMap铜涉，僅重寫了幾個方法，以改變它迭代遍歷時的順序遂唧。這也是其與HashMap相比最大的不同芙代。
在每次插入數(shù)據(jù)，或者訪問盖彭、修改數(shù)據(jù)時纹烹，會增加節(jié)點、或調(diào)整鏈表的節(jié)點順序谬泌。以決定迭代時輸出的順序滔韵。
-
accessOrder,默認是false逻谦，則迭代時輸出的順序是插入節(jié)點的順序掌实。若為true，則輸出的順序是按照訪問節(jié)點的順序邦马。為true時贱鼻，可以在這基礎之上構(gòu)建一個LruCache. -
LinkedHashMap并沒有重寫任何put方法。但是其重寫了構(gòu)建新節(jié)點的newNode()方法.在每次構(gòu)建新節(jié)點時滋将，將新節(jié)點鏈接在內(nèi)部雙向鏈表的尾部 -
accessOrder=true的模式下,在afterNodeAccess()函數(shù)中邻悬，會將當前被訪問到的節(jié)點e，移動至內(nèi)部的雙向鏈表的尾部随闽。值得注意的是父丰，afterNodeAccess()函數(shù)中，會修改modCount,因此當你正在accessOrder=true的模式下,迭代LinkedHashMap時掘宪，如果同時查詢訪問數(shù)據(jù)蛾扇，也會導致fail-fast，因為迭代的順序已經(jīng)改變魏滚。 -
nextNode()就是迭代器里的next()方法 镀首。
該方法的實現(xiàn)可以看出，迭代LinkedHashMap鼠次，就是從內(nèi)部維護的雙鏈表的表頭開始循環(huán)輸出更哄。
而雙鏈表節(jié)點的順序在LinkedHashMap的增芋齿、刪、改成翩、查時都會更新觅捆。以滿足按照插入順序輸出，還是訪問順序輸出麻敌。 - 它與
HashMap比惠拭，還有一個小小的優(yōu)化，重寫了containsValue()方法庸论，直接遍歷內(nèi)部鏈表去比對value值是否相等职辅。
那么，還有最后一個小問題聂示？為什么它不重寫containsKey()方法域携，也去循環(huán)比對內(nèi)部鏈表的key是否相等呢？
