轉載請注明出處：http://blog.csdn.net/ns_code/article/details/37867985
前言：有網友建議分析下LinkedHashMap的源碼，于是花了一晚上時間研究了下，分享出此文（這個系列的最後一篇博文了），希望大家互相學習。LinkedHashMap的源碼了解起來也不難（當然，要建立在對HashMap源碼有較好了解的基礎上）。
LinkedHashMap簡介
LinkedHashMap是HashMap的子類，與HashMap有着同樣的存儲結構，但它加入了一個雙向連結清單的頭結點，将所有put到LinkedHashmap的節點一一串成了一個雙向循環連結清單，是以它保留了節點插入的順序，可以使節點的輸出順序與輸入順序相同。
LinkedHashMap可以用來實作LRU算法（這會在下面的源碼中進行分析）。
LinkedHashMap同樣是非線程安全的，隻在單線程環境下使用。
LinkedHashMap源碼剖析
LinkedHashMap源碼如下（加入了詳細的注釋）：
package java.util;
import java.io.*;
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
private static final long serialVersionUID = 3801124242820219131L;
//雙向循環連結清單的頭結點，整個LinkedHa隻喲shMap中隻有一個header，
//它将哈希表中所有的Entry貫穿起來，header中不儲存key-value對，隻儲存前後節點的引用
private transient Entry<K,V> header;
//雙向連結清單中元素排序規則的标志位。
//accessOrder為false，表示按插入順序排序
//accessOrder為true，表示按通路順序排序
private final boolean accessOrder;
//調用HashMap的構造方法來構造底層的數組
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false; //連結清單中的元素預設按照插入順序排序
}
//加載因子取預設的0.75f
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
//加載因子取預設的0.75f，容量取預設的16
public LinkedHashMap() {
super();
accessOrder = false;
}
//含有子Map的構造方法，同樣調用HashMap的對應的構造方法
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super(m);
accessOrder = false;
}
//該構造方法可以指定連結清單中的元素排序的規則
public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
//覆寫父類的init()方法（HashMap中的init方法為空），
//該方法在父類的構造方法和Clone、readObject中在插入元素前被調用，
//初始化一個空的雙向循環連結清單，頭結點中不儲存資料，頭結點的下一個節點才開始儲存資料。
void init() {
header = new Entry<K,V>(-1, null, null, null);
header.before = header.after = header;
}
//覆寫HashMap中的transfer方法，它在父類的resize方法中被調用，
//擴容後，将key-value對重新映射到新的newTable中
//覆寫該方法的目的是為了提高複制的效率，
//這裡充分利用雙向循環連結清單的特點進行疊代，不用對底層的數組進行for循環。
void transfer(HashMap.Entry[] newTable) {
int newCapacity = newTable.length;
for (Entry<K,V> e = header.after; e != header; e = e.after) {
int index = indexFor(e.hash, newCapacity);
e.next = newTable[index];
newTable[index] = e;
}
}
//覆寫HashMap中的containsValue方法，
//覆寫該方法的目的同樣是為了提高查詢的效率，
//利用雙向循環連結清單的特點進行查詢，少了對數組的外層for循環
public boolean containsValue(Object value) {
// Overridden to take advantage of faster iterator
if (value==null) {
for (Entry e = header.after; e != header; e = e.after)
if (e.value==null)
return true;
} else {
for (Entry e = header.after; e != header; e = e.after)
if (value.equals(e.value))
return true;
}
return false;
}
//覆寫HashMap中的get方法，通過getEntry方法擷取Entry對象。
//注意這裡的recordAccess方法，
//如果連結清單中元素的排序規則是按照插入的先後順序排序的話，該方法什麼也不做，
//如果連結清單中元素的排序規則是按照通路的先後順序排序的話，則将e移到連結清單的末尾處。
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
}
//清空HashMap，并将雙向連結清單還原為隻有頭結點的空連結清單
public void clear() {
super.clear();
header.before = header.after = header;
}
//Enty的資料結構，多了兩個指向前後節點的引用
private static class Entry<K,V> extends HashMap.Entry<K,V> {
// These fields comprise the doubly linked list used for iteration.
Entry<K,V> before, after;
//調用父類的構造方法
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
//雙向循環連結清單中，删除目前的Entry
private void remove() {
before.after = after;
after.before = before;
}
//雙向循環立連結清單中，将目前的Entry插入到existingEntry的前面
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
//覆寫HashMap中的recordAccess方法（HashMap中該方法為空），
//當調用父類的put方法，在發現插入的key已經存在時，會調用該方法，
//調用LinkedHashmap覆寫的get方法時，也會調用到該方法，
//該方法提供了LRU算法的實作，它将最近使用的Entry放到雙向循環連結清單的尾部，
//accessOrder為true時，get方法會調用recordAccess方法
//put方法在覆寫key-value對時也會調用recordAccess方法
//它們導緻Entry最近使用，是以将其移到雙向連結清單的末尾
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
//如果連結清單中元素按照通路順序排序，則将目前通路的Entry移到雙向循環連結清單的尾部，
//如果是按照插入的先後順序排序，則不做任何事情。
if (lm.accessOrder) {
lm.modCount++;
//移除目前通路的Entry
remove();
//将目前通路的Entry插入到連結清單的尾部
addBefore(lm.header);
}
}
void recordRemoval(HashMap<K,V> m) {
remove();
}
}
//疊代器
private abstract class LinkedHashIterator<T> implements Iterator<T> {
Entry<K,V> nextEntry = header.after;
Entry<K,V> lastReturned = null;
/**
* The modCount value that the iterator believes that the backing
* List should have. If this expectation is violated, the iterator
* has detected concurrent modification.
*/
int expectedModCount = modCount;
public boolean hasNext() {
return nextEntry != header;
}
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
LinkedHashMap.this.remove(lastReturned.key);
lastReturned = null;
expectedModCount = modCount;
}
//從head的下一個節點開始疊代
Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (nextEntry == header)
throw new NoSuchElementException();
Entry<K,V> e = lastReturned = nextEntry;
nextEntry = e.after;
return e;
}
}
//key疊代器
private class KeyIterator extends LinkedHashIterator<K> {
public K next() { return nextEntry().getKey(); }
}
//value疊代器
private class ValueIterator extends LinkedHashIterator<V> {
public V next() { return nextEntry().value; }
}
//Entry疊代器
private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() { return nextEntry(); }
}
// These Overrides alter the behavior of superclass view iterator() methods
Iterator<K> newKeyIterator() { return new KeyIterator(); }
Iterator<V> newValueIterator() { return new ValueIterator(); }
Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }
//覆寫HashMap中的addEntry方法，LinkedHashmap并沒有覆寫HashMap中的put方法，
//而是覆寫了put方法所調用的addEntry方法和recordAccess方法，
//put方法在插入的key已存在的情況下，會調用recordAccess方法，
//在插入的key不存在的情況下，要調用addEntry插入新的Entry
void addEntry(int hash, K key, V value, int bucketIndex) {
//建立新的Entry，并插入到LinkedHashMap中
createEntry(hash, key, value, bucketIndex);
//雙向連結清單的第一個有效節點（header後的那個節點）為近期最少使用的節點
Entry<K,V> eldest = header.after;
//如果有必要，則删除掉該近期最少使用的節點，
//這要看對removeEldestEntry的覆寫,由于預設為false，是以預設是不做任何處理的。
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
} else {
//擴容到原來的2倍
if (size >= threshold)
resize(2 * table.length);
}
}
void createEntry(int hash, K key, V value, int bucketIndex) {
//建立新的Entry，并将其插入到數組對應槽的單連結清單的頭結點處，這點與HashMap中相同
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
table[bucketIndex] = e;
//每次插入Entry時，都将其移到雙向連結清單的尾部，
//這便會按照Entry插入LinkedHashMap的先後順序來疊代元素，
//同時，新put進來的Entry是最近通路的Entry，把其放在連結清單末尾 ，符合LRU算法的實作
e.addBefore(header);
size++;
}
//該方法是用來被覆寫的，一般如果用LinkedHashmap實作LRU算法，就要覆寫該方法，
//比如可以将該方法覆寫為如果設定的記憶體已滿，則傳回true，這樣當再次向LinkedHashMap中put
//Entry時，在調用的addEntry方法中便會将近期最少使用的節點删除掉（header後的那個節點）。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
}
幾點總結
關于LinkedHashMap的源碼，給出以下幾點比較重要的總結：
1、從源碼中可以看出，LinkedHashMap中加入了一個head頭結點，将所有插入到該LinkedHashMap中的Entry按照插入的先後順序依次加入到以head為頭結點的雙向循環連結清單的尾部。
實際上就是HashMap和LinkedList兩個集合類的存儲結構的結合。在LinkedHashMapMap中，所有put進來的Entry都儲存在如第一個圖所示的哈希表中，但它又額外定義了一個以head為頭結點的空的雙向循環連結清單，每次put進來Entry，除了将其儲存到對哈希表中對應的位置上外，還要将其插入到雙向循環連結清單的尾部。
2、LinkedHashMap由于繼承自HashMap，是以它具有HashMap的所有特性，同樣允許key和value為null。
3、注意源碼中的accessOrder标志位，當它false時，表示雙向連結清單中的元素按照Entry插入LinkedHashMap到中的先後順序排序，即每次put到LinkedHashMap中的Entry都放在雙向連結清單的尾部，這樣周遊雙向連結清單時，Entry的輸出順序便和插入的順序一緻，這也是預設的雙向連結清單的存儲順序；當它為true時，表示雙向連結清單中的元素按照通路的先後順序排列，可以看到，雖然Entry插傳入連結表的順序依然是按照其put到LinkedHashMap中的順序，但put和get方法均有調用recordAccess方法（put方法在key相同，覆寫原有的Entry的情況下調用recordAccess方法），該方法判斷accessOrder是否為true，如果是，則将目前通路的Entry（put進來的Entry或get出來的Entry）移到雙向連結清單的尾部（key不相同時，put新Entry時，會調用addEntry，它會調用creatEntry，該方法同樣将新插入的元素放入到雙向連結清單的尾部，既符合插入的先後順序，又符合通路的先後順序，因為這時該Entry也被通路了），否則，什麼也不做。
4、注意構造方法，前四個構造方法都将accessOrder設為false，說明預設是按照插入順序排序的，而第五個構造方法可以自定義傳入的accessOrder的值，是以可以指定雙向循環連結清單中元素的排序規則，一般要用LinkedHashMap實作LRU算法，就要用該構造方法，将accessOrder置為true。
5、LinkedHashMap并沒有覆寫HashMap中的put方法，而是覆寫了put方法中調用的addEntry方法和recordAccess方法，我們回過頭來再看下HashMap的put方法：
// 将“key-value”添加到HashMap中
public V put(K key, V value) {
// 若“key為null”，則将該鍵值對添加到table[0]中。
if (key == null)
return putForNullKey(value);
// 若“key不為null”，則計算該key的哈希值，然後将其添加到該哈希值對應的連結清單中。
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 若“該key”對應的鍵值對已經存在，則用新的value取代舊的value。然後退出！
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 若“該key”對應的鍵值對不存在，則将“key-value”添加到table中
modCount++;
//将key-value添加到table[i]處
addEntry(hash, key, value, i);
return null;
}
當要put進來的Entry的key在哈希表中已經在存在時，會調用recordAccess方法，當該key不存在時，則會調用addEntry方法将新的Entry插入到對應槽的單連結清單的頭部。
我們先來看recordAccess方法：
//覆寫HashMap中的recordAccess方法（HashMap中該方法為空），
//當調用父類的put方法，在發現插入的key已經存在時，會調用該方法，
//調用LinkedHashmap覆寫的get方法時，也會調用到該方法，
//該方法提供了LRU算法的實作，它将最近使用的Entry放到雙向循環連結清單的尾部，
//accessOrder為true時，get方法會調用recordAccess方法
//put方法在覆寫key-value對時也會調用recordAccess方法
//它們導緻Entry最近使用，是以将其移到雙向連結清單的末尾
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
//如果連結清單中元素按照通路順序排序，則将目前通路的Entry移到雙向循環連結清單的尾部，
//如果是按照插入的先後順序排序，則不做任何事情。
if (lm.accessOrder) {
lm.modCount++;
//移除目前通路的Entry
remove();
//将目前通路的Entry插入到連結清單的尾部
addBefore(lm.header);
}
}
該方法會判斷accessOrder是否為true，如果為true，它會将目前通路的Entry（在這裡指put進來的Entry）移動到雙向循環連結清單的尾部，進而實作雙向連結清單中的元素按照通路順序來排序（最近通路的Entry放到連結清單的最後，這樣多次下來，前面就是最近沒有被通路的元素，在實作、LRU算法時，當雙向連結清單中的節點數達到最大值時，将前面的元素删去即可，因為前面的元素是最近最少使用的），否則什麼也不做。
再來看addEntry方法：
//覆寫HashMap中的addEntry方法，LinkedHashmap并沒有覆寫HashMap中的put方法，
//而是覆寫了put方法所調用的addEntry方法和recordAccess方法，
//put方法在插入的key已存在的情況下，會調用recordAccess方法，
//在插入的key不存在的情況下，要調用addEntry插入新的Entry
void addEntry(int hash, K key, V value, int bucketIndex) {
//建立新的Entry，并插入到LinkedHashMap中
createEntry(hash, key, value, bucketIndex);
//雙向連結清單的第一個有效節點（header後的那個節點）為近期最少使用的節點
Entry<K,V> eldest = header.after;
//如果有必要，則删除掉該近期最少使用的節點，
//這要看對removeEldestEntry的覆寫,由于預設為false，是以預設是不做任何處理的。
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
} else {
//擴容到原來的2倍
if (size >= threshold)
resize(2 * table.length);
}
}
void createEntry(int hash, K key, V value, int bucketIndex) {
//建立新的Entry，并将其插入到數組對應槽的單連結清單的頭結點處，這點與HashMap中相同
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
table[bucketIndex] = e;
//每次插入Entry時，都将其移到雙向連結清單的尾部，
//這便會按照Entry插入LinkedHashMap的先後順序來疊代元素，
//同時，新put進來的Entry是最近通路的Entry，把其放在連結清單末尾 ，符合LRU算法的實作
e.addBefore(header);
size++;
}
同樣是将新的Entry插入到table中對應槽所對應單連結清單的頭結點中，但可以看出，在createEntry中，同樣把新put進來的Entry插入到了雙向連結清單的尾部，從插入順序的層面來說，新的Entry插入到雙向連結清單的尾部，可以實作按照插入的先後順序來疊代Entry，而從通路順序的層面來說，新put進來的Entry又是最近通路的Entry，也應該将其放在雙向連結清單的尾部。
上面還有個removeEldestEntry方法，該方法如下：
//該方法是用來被覆寫的，一般如果用LinkedHashmap實作LRU算法，就要覆寫該方法，
//比如可以将該方法覆寫為如果設定的記憶體已滿，則傳回true，這樣當再次向LinkedHashMap中put
//Entry時，在調用的addEntry方法中便會将近期最少使用的節點删除掉（header後的那個節點）。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
}
該方法預設傳回false，我們一般在用LinkedHashMap實作LRU算法時，要覆寫該方法，一般的實作是，當設定的記憶體（這裡指節點個數）達到最大值時，傳回true，這樣put新的Entry（該Entry的key在哈希表中沒有已經存在）時，就會調用removeEntryForKey方法，将最近最少使用的節點删除（head後面的那個節點，實際上是最近沒有使用）。
6、LinkedHashMap覆寫了HashMap的get方法：
//覆寫HashMap中的get方法，通過getEntry方法擷取Entry對象。
//注意這裡的recordAccess方法，
//如果連結清單中元素的排序規則是按照插入的先後順序排序的話，該方法什麼也不做，
//如果連結清單中元素的排序規則是按照通路的先後順序排序的話，則将e移到連結清單的末尾處。
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
}
先取得Entry，如果不為null，一樣調用recordAccess方法，上面已經說得很清楚，這裡不在多解釋了。
7、最後說說LinkedHashMap是如何實作LRU的。首先，當accessOrder為true時，才會開啟按通路順序排序的模式，才能用來實作LRU算法。我們可以看到，無論是put方法還是get方法，都會導緻目标Entry成為最近通路的Entry，是以便把該Entry加入到了雙向連結清單的末尾（get方法通過調用recordAccess方法來實作，put方法在覆寫已有key的情況下，也是通過調用recordAccess方法來實作，在插入新的Entry時，則是通過createEntry中的addBefore方法來實作），這樣便把最近使用了的Entry放入到了雙向連結清單的後面，多次操作後，雙向連結清單前面的Entry便是最近沒有使用的，這樣當節點個數滿的時候，删除的最前面的Entry(head後面的那個Entry)便是最近最少使用的Entry。