LinkedHashMap，源碼解讀就是這么簡單

概述

LinkedHashMap是HashMap的子類，它的大部分實現與HashMap相同，兩者最大的區別在于，HashMap的對哈希表進行迭代時是無序的，而LinkedHashMap對哈希表迭代是有序的，LinkedHashMap默認的規則是，迭代輸出的結果保持和插入key-value pair的順序一致（當然具體迭代規則可以修改）。LinkedHashMap除了像HashMap一樣用數組、單鏈表和紅黑樹來組織數據外，還額外維護了一個雙向鏈表，每次向linkedHashMap插入鍵值對，除了將其插入到哈希表的對應位置之外，還要將其插入到雙向循環鏈表的尾部。

底層實現

先來看一下LinekedHashMap的定義：

public?class?LinkedHashMap<K,V>
????extends?HashMap<K,V>
????implements?Map<K,V>

除了繼承自HashMap以外并無太多特殊之處，這里特地標注實現了Map接口應該也只是為了醒目。

大家最關心的應該是LinkedHashMap如何實現有序迭代，下面將逐步通過源碼來解答這一問題。

先看一下一個重要的靜態內部類Entry：

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);
????}}

該類繼承自HashMap的Node內部類，前面已經介紹過，Node是一個單鏈表結構，這里Entry添加了前繼引用和后繼引用，則是一個雙向鏈表的節點。在雙向鏈表中，每個節點可以記錄自己前后插入的節點信息，以維持有序性，這也是LinkedHashMap實現有序迭代的關鍵。

按插入順序有序和按訪問順序有序

按插入有序

按插入有序即先添加的在前面，后添加的在后面，修改操作不影響順序。以如下代碼為例：

Map<String,Integer>?seqMap?=?new?LinkedHashMap<>();seqMap.put("c",?100);seqMap.put("d",?200);seqMap.put("a",?500);seqMap.put("d",?300);for(Entry<String,Integer>?entry?:?seqMap.entrySet()){
????System.out.println(entry.getKey()+"?"+entry.getValue());}運行結

運行結果是：

c?100d?300a?500

可以看到，鍵是按照”c”, “d”, “a”的順序插入的，修改”d”的值不會修改順序。

按訪問有序

按訪問有序是，序列末尾存放的是最近訪問的key-value pair，每次訪問一個key-value pair后，就會將其移動到末尾。

Map<String,Integer>?accessMap?=?new?LinkedHashMap<>(16,?0.75f,?true);accessMap.put("c",?100);accessMap.put("d",?200);accessMap.put("a",?500);accessMap.get("c");accessMap.put("d",?300);for(Entry<String,Integer>?entry?:?accessMap.entrySet()){
????System.out.println(entry.getKey()+"?"+entry.getValue());}

運行結果為：

a?500?
c?100?
d?300

針對不同的應用場景，LinkedHashMap可以在這兩種排序方式中進行抉擇。

LinkedHashMap定義了三個重要的字段：

//雙鏈表的頭節點transient?LinkedHashMap.Entry<K,V>?head;//雙鏈表的尾節點transient?LinkedHashMap.Entry<K,V>?tail;/**?*?這個字段表示哈希表的迭代順序?*?true表示按訪問順序迭代?*?false表示按插入順序迭代?*?LinkedHashMap的構造函數均將該值設為false，因此默認為false?*/final?boolean?accessOrder;

關于它們的具體作用已在注釋中標出。

LinkedHashMap有五個構造方法，其中有一個可以指定accessOrder的值：

public?LinkedHashMap(int?initialCapacity,
?????????????????????float?loadFactor,
?????????????????????boolean?accessOrder)?{
????super(initialCapacity,?loadFactor);
????this.accessOrder?=?accessOrder;}

重要方法

在HashMap中定義了幾個“鉤子”方法（關于鉤子的詳細內容，請參考筆者的博客設計模式(9)——模板方法模式），這里特地列出其中的三個：

• afterNodeRemoval(e)

• afterNodeInsertion

• afterNodeInsertion

它們與迭代有序性的實現息息相關。

此外還有兩個重要的APIget和containsValue，這里也分析一下它們的源碼實現，至于put方法，LinkedHashMap并沒有覆寫該方法，因此其實現與HashMap相同。

afterNodeRemoval(e)方法

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的removeNode方法中調用了該鉤子方法，對于LinkedHashMap，在執行完對哈希桶中單鏈表或紅黑樹節點的刪除操作后，還需要調用該方法將雙向鏈表中對應的Entry刪除。

afterNodeInsertion方法

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

在HashMap的putVal方法中調用了該方法，可以看出，在判斷條件成立的情況下，該方法會刪除雙鏈表中的頭節點（當然是在哈希桶和雙向鏈表中同步刪除該節點）。判斷條件涉及了一個removeEldestEntry(first)方法，它的源碼如下：

protected?boolean?removeEldestEntry(Map.Entry<K,V>?eldest)?{
????return?false;}

可以看到，它默認是返回false的，即不刪除頭節點。如果需要定義是否需要刪除頭節點的規則，只需覆蓋該方法并提供相關實現即可。該方法的作用在于，它提供了當一個新的entry被添加到linkedHashMap中，刪除頭節點的機會。這是非常有意義的，可以通過刪除頭節點來減少內存消耗，避免內存溢出。

afterNodeAccess(e)方法

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;
????}}

該方法在HashMap的putVal方法、LinkedHashMap的get方法中都被調用，它的作用是：如果accessOrder返回值為true（即按照訪問順序迭代），則將最近訪問的節點調整至雙向隊列的隊尾，這也就保證了按照訪問順序迭代時Entry的有序性。

get(key)方法

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;}

該方法增加了按訪問順序或插入順序進行排序的選擇功能，會根據AccessOrder的值調整雙向鏈表中節點的順序，獲取節點的過程與HashMap中一致。

containsValue(value)方法

public?boolean?containsValue(Object?value)?{
????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;}

由于LinkedHashMap維護了一個雙向鏈表，因此它的containsValue(value)方法直接遍歷雙向鏈表查找對應的Entry即可，而無需去遍歷哈希桶。

LinkedHashMap與HashMap

LinkedHashMap是HashMap的子類，它們最大的區別是，HashMap的迭代是無序的，而LinkedHashMap是有序的，并且有按插入順序和按訪問順序兩種方式。為了實現有序迭代，LinkedHashMap相比HashMap，額外維護了一個雙向鏈表，因此一般情況下，遍歷HashMap比LinkedHashMap效率要高，在沒有按序訪問key-value pair的情況下，一般建議使用HashMap（當然也有例外，當HashMap容量很大，實際數據較少時，遍歷起來可能會比 LinkedHashMap慢，因為LinkedHashMap的遍歷速度只和實際數據有關，和容量無關，而HashMap的遍歷速度和他的容量有關）。