前言

我們知道HashMap底層是采用數組+單向線性鏈表/紅黑樹來實現的，HashMap在擴容或者鏈表與紅黑樹轉換過程時可能會改變元素的位置和順序。如果需要保存元素存入或訪問的先后順序，那就需要采用LinkedHashMap了。

LinkedHashMap結構

LinkedHashMap繼承自HashMap，它的所有操作和HashMap類似，底層結構也和HashMap一樣，只不過為了維護元素的存入/訪問順序，增加了一個雙向鏈表。

LinkedHashMap由數組、單向線性鏈表、紅黑樹、雙向線性鏈表組成。如上圖：灰色區域為數組，藍色節點和藍色箭頭為單向鏈表的引用關系，綠色節點和綠色箭頭為紅黑樹的引用關系，節點中的數字依次表示元素的存入/訪問順序，由橙色的雙向箭頭表示雙向鏈表的引用關系。

注：在JDK1.7及之前HashMap中沒有紅黑樹，LinkedHashMap中也不存在紅黑樹。另在JDK1.6及之前，HashMap中的鏈表為單向環形鏈表，LinkedHashMap中中的單向鏈表和雙向鏈表都是環形鏈表。在JDK1.8，LinkedHashMap中可能會存在紅黑樹，同時單向鏈表和雙向鏈表都是線性的。本文是基于JDK1.8來分析的。

LinkedHashMap源碼分析

基本屬性：

transient LinkedHashMap.Entry<K,V> head;    // 雙向鏈表頭節點
transient LinkedHashMap.Entry<K,V> tail;    // 雙向鏈表尾節點
final boolean accessOrder;                    // 是否按照訪問順序排序復制代碼

head和tail分別記錄了雙向鏈表的頭節點和尾節點，遍歷時通過head或tail就可以按照存入/訪問的順序來取數據。

accessOrder用以表示LinkedHashMap是否按照訪問順序來排序，為true的話表示按照訪問順序排序，為false表示按照存入順序排序，默認為false。

構造函數：

// 無參構造
public LinkedHashMap() {super();accessOrder = false;
}
// 給定初始容量
public LinkedHashMap(int initialCapacity) {super(initialCapacity);accessOrder = false;
}
// 給定初始容量和加載因子
public LinkedHashMap(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor);accessOrder = false;
}
// 給定初始容量、加載因子、是否按訪問先后排序
public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {super(initialCapacity, loadFactor);this.accessOrder = accessOrder;
}復制代碼

構造函數都是調用父類HashMap的構造函數。前3個都默認accessOrder為false，LinkedHashMap內部按照存入順序排序。最后一個構造函數可以指定accessOrder的值。

增：

LinkedHashMap添加數據要調用了父類的HashMap的put方法，在HashMap的源碼中，put方法存入元素后，調用了afterNodeAccess和afterNodeInsertion方法，這兩個方法在HashMap中都是空方法，LinkedHashMap實現了這兩個方法：

void afterNodeAccess(Node<K,V> e) { LinkedHashMap.Entry<K,V> last;// 如果按照訪問順序排序，并且添加的元素e不是雙向鏈表的尾節點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;elseb.after = a;if (a != null)a.before = b;elselast = b;if (last == null)head = p;else {p.before = last;last.after = p;}tail = p;++modCount;}
}復制代碼

afterNodeAccess方法的邏輯就是將當前節點e移動到雙向鏈表的尾部。每次LinkedHashMap中有元素被訪問時，就會按照訪問先后來排序，先訪問的在雙向鏈表中靠前，越后訪問的越接近尾部。當然只有當accessOrder為true時，才會執行這個操作。

void afterNodeInsertion(boolean evict) { // possibly remove eldestLinkedHashMap.Entry<K,V> first;if (evict && (first = head) != null && removeEldestEntry(first)) {K key = first.key;removeNode(hash(key), key, null, false, true);}
}復制代碼

afterNodeInsertion方法意思是evict為true時刪除雙向鏈表的頭節點。

通過afterNodeAccess和afterNodeInsertion這兩個方法，如果當LinkedHashMap的容量達到一定量時，需要保存它的size不變，那么每次添加一個元素到雙向鏈表的尾部，就要刪除一個雙向鏈表頭部的元素，這相當于實現了LruCache的策略。

刪：

刪除元素同樣也是調用了HashMap的remove方法，在remove方法中，調用了afterNodeRemoval方法。

void afterNodeRemoval(Node<K,V> e) { // unlinkLinkedHashMap.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;elseb.after = a;if (a == null)tail = b;elsea.before = b;
}復制代碼

afterNodeRemoval方法就是將e節點從雙向鏈表中刪除，更改e前后節點引用關系，使之重新連成完整的雙向鏈表。

改：

LinkedHashMap更改元素的value值，仍是調用put方法，涉及到的邏輯可以看上面的afterNodeAccess和afterNodeInsertion這兩個方法。

查：

LinkedHashMap自己實現了get方法。

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;
}復制代碼

邏輯非常簡單，直接調用HashMap的getNode方法，如果需要按照訪問先后排序，調用afterNodeAccess更新雙向鏈表排序。

總結

LinkedHashMap繼承了HashMap的所有特性，唯一的區別就是LinkedHashMap是一個有序的映射集合，而HashMap則是無序的。LinkedHashMap實現排序的原理就是再內部增加了一個雙向鏈表來記錄元素的存入/訪問順序。LinkedHashMap內部是記錄的是存入還是訪問順序取決于關鍵屬性accessOrder，默認是按存入順序記錄。