Java中最大的資料結構：LinkedHashMap 了解一下？

作者：莫那一魯道 https://www.jianshu.com/p/06a0fd962e0b

Map 家族數量衆多，其中 HashMap 和 ConcurrentHashMap 用的最多，而 LinkedHashMap 似乎則是不怎麼用的，但是他卻有着順序。兩種，一種是添加順序，一種是通路順序。

LinkedHashMap 繼承了 HashMap。那麼如果是你，你怎麼實作這兩個順序呢？

如果實作添加順序的話，我們可以在該類中，增加一個連結清單，每個節點對應 hash 表中的桶。這樣，循環周遊的時候，就可以按照連結清單周遊了。隻是會增大記憶體消耗。

如果實作通路順序的話，同樣也可以使用連結清單，但每次讀取資料時，都需要更新一下連結清單，将最近一次讀取的放到鍊尾。這樣也就能夠實作。此時也可以跟進這個特性實作 LRU（Least Recently Used） 緩存。

如何使用？

下面是個小 demo

LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>(16, 0.75f, true);
for (int i = 0; i < 10; i++) {
  map.put(i, i);
}

for (Map.Entry entry : map.entrySet()) {
  System.out.println(entry.getKey() + ":" + entry.getValue());
}
map.get(3);
System.out.println();
for (Map.Entry entry : map.entrySet()) {
  System.out.println(entry.getKey() + ":" + entry.getValue());
}      

列印結果：

0:0
1:1
2:2
3:3
4:4
5:5
6:6
7:7
8:8
9:9

0:0
1:1
2:2
4:4
5:5
6:6
7:7
8:8
9:9
3:3      

首先構造方法是有意思的，比 HashMap 多了一個 accessOrder boolean 參數。表示，按照通路順序來排序。最新通路的放在連結清單尾部。

如果是預設的，則是按照添加順序，即 accessOrder 預設是 false。

源碼實作

如果看 LinkedHashMap 内部源碼，會發現，内部确實維護了一個連結清單：

/**
 * 雙向連結清單的頭，最久通路的
 */
transient LinkedHashMap.Entry<K,V> head;

/**
 * 雙向連結清單的尾，最新通路的
 */
transient LinkedHashMap.Entry<K,V> tail;      

而這個 LinkedHashMap.Entry 内部也維護了雙向連結清單必須的元素，before，after：

/**
 * HashMap.Node subclass for normal LinkedHashMap entries.
 */
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);
    }
}      

在添加元素的時候，會追加到尾部。

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

// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}      

在 get 的時候，會根據 accessOrder 屬性，修改連結清單順序：

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

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

同時注意：這裡修改了 modCount，即使是讀操作，并發也是不安全的。

如何實作 LRU 緩存？

LRU 緩存：LRU（Least Recently Used，最近最少使用）算法根據資料的曆史通路記錄來進行淘汰資料，其核心思想是“如果資料最近被通路過，那麼将來被通路的幾率也更高”。

LinkedHashMap 并沒有幫我我們實作具體，需要我們自己實作 。具體實作方法是 removeEldestEntry 方法。

一起來看看原理。

首先，HashMap 在 putVal 方法最後，會調用 afterNodeInsertion 方法，其實就是留給 LinkedHashMap 的。而 LinkedHashMap 的具體實作則是根據一些條件，判斷是否需要删除 head 節點。

關注微信公衆号：Java技術棧，在背景回複：Java，可以擷取我整理的 N 篇最新Java 技術教程，都是幹貨。

源碼如下：

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

evict 參數表示是否需要删除某個元素，而這個 if 判斷需要滿足的條件如上：head 不能是 null，調用 removeEldestEntry 方法，傳回 true 的話，就删除這個 head。而這個方法預設是傳回 false 的，等待着你來重寫。

是以，removeEldestEntry 方法的實作通常是這樣：

public boolean removeEldestEntry(Map.Entry<K, V> eldest){
   return size() > capacity;
}      

如果長度大于容量了，那麼就需要清除不經常通路的緩存了。afterNodeInsertion 會調用 removeNode 方法，删除掉 head 節點 —— 如果 accessOrder 是 true 的話，這個節點就是最不經常通路的節點。

拾遺

LinkedHashMap 重寫了一些 HashMap 的方法，例如 containsValue 方法，這個方法大家猜一猜，怎麼重寫比較合理？

HashMap 使用了雙重循環，先循環外層的 hash 表，再循環内層的 entry 連結清單。性能可想而知。

但 LinkedHashMap 内部有個元素連結清單，直接周遊連結清單就行。相對而言而高很多。

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

這也算一種空間換時間的政策吧。

get 方法當然也是要重寫的。因為需要根據 accessOrder 更新連結清單。

總結

雪薇的總結的一下：

LinkedHashMap 内部包含一個雙向連結清單維護順序，支援兩種順序——添加順序，通路順序。

預設就是按照添加順序來的，如果要改成通路順序的話，構造方法中的 accessOrder 需要設定成 true。這樣，每次調用 get 方法，就會将剛剛通路的元素更新到連結清單尾部。

關于 LRU，在accessOrder 為 true 的模式下，你可以重寫 removeEldestEntry 方法，傳回 size() > capacity，這樣，就可以删除最不常通路的元素。