Java類集架構 —— LinkedHashMap源碼分析

前言

我們知道

HashMap

底層是采用數組+單向線性連結清單/紅黑樹來實作的，

HashMap

在擴容或者連結清單與紅黑樹轉換過程時可能會改變元素的位置和順序。如果需要儲存元素存入或通路的先後順序，那就需要采用

LinkedHashMap

了。

LinkedHashMap結構

LinkedHashMap

繼承自

HashMap

，它的所有操作和

HashMap

類似，底層結構也和

HashMap

一樣，隻不過為了維護元素的存入/通路順序，增加了一個雙向連結清單。

LinkedHashMap結構圖

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

afterNodeAccess

方法的邏輯就是将目前節點

e

移動到雙向連結清單的尾部。每次

LinkedHashMap

中有元素被通路時，就會按照通路先後來排序，先通路的在雙向連結清單中靠前，越後通路的越接近尾部。當然隻有當

accessOrder

為

true

時，才會執行這個操作。

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

afterNodeInsertion

方法意思是

evict

為

true

時删除雙向連結清單的頭節點。

通過

afterNodeAccess

和

afterNodeInsertion

這兩個方法，如果當

LinkedHashMap

的容量達到一定量時，需要儲存它的

size

不變，那麼每次添加一個元素到雙向連結清單的尾部，就要删除一個雙向連結清單頭部的元素，這相當于實作了

LruCache

的政策。

删：

删除元素同樣也是調用了

HashMap

的

remove

方法，在

remove

方法中，調用了

afterNodeRemoval

方法。

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

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

，預設是按存入順序記錄。