前言

Map 家族數(shù)量眾多，其中 HashMap 和 ConcurrentHashMap 用的最多，而 LinkedHashMap 似乎則是不怎么用的，但是他卻有著順序。兩種，一種是添加順序，一種是訪問順序。

詳情

LinkedHashMap 繼承了 HashMap。那么如果是你，你怎么實(shí)現(xiàn)這兩個(gè)順序呢？

如果實(shí)現(xiàn)添加順序的話，我們可以在該類中，增加一個(gè)鏈表，每個(gè)節(jié)點(diǎn)對(duì)應(yīng) hash 表中的桶。這樣，循環(huán)遍歷的時(shí)候，就可以按照鏈表遍歷了。只是會(huì)增大內(nèi)存消耗。

如果實(shí)現(xiàn)訪問順序的話，同樣也可以使用鏈表，但每次讀取數(shù)據(jù)時(shí)，都需要更新一下鏈表，將最近一次讀取的放到鏈尾。這樣也就能夠?qū)崿F(xiàn)。此時(shí)也可以跟進(jìn)這個(gè)特性實(shí)現(xiàn) LRU（Least Recently Used） 緩存。

如何使用？

下面是個(gè)小 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());
}

打印結(jié)果：

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

首先構(gòu)造方法是有意思的，比 HashMap 多了一個(gè) accessOrder boolean 參數(shù)。表示，按照訪問順序來排序。最新訪問的放在鏈表尾部。

如果是默認(rèn)的，則是按照添加順序，即 accessOrder 默認(rèn)是 false。

源碼實(shí)現(xiàn)

如果看 LinkedHashMap 內(nèi)部源碼，會(huì)發(fā)現(xiàn)，內(nèi)部確實(shí)維護(hù)了一個(gè)鏈表：

    /**
     * 雙向鏈表的頭，最久訪問的
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * 雙向鏈表的尾，最新訪問的
     */
    transient LinkedHashMap.Entry<K,V> tail;

而這個(gè) LinkedHashMap.Entry 內(nèi)部也維護(hù)了雙向鏈表必須的元素，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);
        }
    }

在添加元素的時(shí)候，會(huì)追加到尾部。

    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 的時(shí)候，會(huì)根據(jù) 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;
        }
    }

同時(shí)注意：這里修改了 modCount，即使是讀操作，并發(fā)也是不安全的。

如何實(shí)現(xiàn) LRU 緩存？

LRU 緩存：LRU（Least Recently Used，最近最少使用）算法根據(jù)數(shù)據(jù)的歷史訪問記錄來進(jìn)行淘汰數(shù)據(jù)，其核心思想是“如果數(shù)據(jù)最近被訪問過，那么將來被訪問的幾率也更高”。

LinkedHashMap 并沒有幫我我們實(shí)現(xiàn)具體，需要我們自己實(shí)現(xiàn) 。具體實(shí)現(xiàn)方法是 removeEldestEntry 方法。

一起來看看原理。

首先，HashMap 在 putVal 方法最后，會(huì)調(diào)用 afterNodeInsertion 方法，其實(shí)就是留給 LinkedHashMap 的。而 LinkedHashMap 的具體實(shí)現(xiàn)則是根據(jù)一些條件，判斷是否需要?jiǎng)h除 head 節(jié)點(diǎn)。

源碼如下：

    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 參數(shù)表示是否需要?jiǎng)h除某個(gè)元素，而這個(gè) if 判斷需要滿足的條件如上：head 不能是 null，調(diào)用 removeEldestEntry 方法，返回 true 的話，就刪除這個(gè) head。而這個(gè)方法默認(rèn)是返回 false 的，等待著你來重寫。

所以，removeEldestEntry 方法的實(shí)現(xiàn)通常是這樣：

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

如果長(zhǎng)度大于容量了，那么就需要清除不經(jīng)常訪問的緩存了。afterNodeInsertion 會(huì)調(diào)用 removeNode 方法，刪除掉 head 節(jié)點(diǎn) —— 如果 accessOrder 是 true 的話，這個(gè)節(jié)點(diǎn)就是最不經(jīng)常訪問的節(jié)點(diǎn)。

拾遺

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

HashMap 使用了雙重循環(huán)，先循環(huán)外層的 hash 表，再循環(huán)內(nèi)層的 entry 鏈表。性能可想而知。

但 LinkedHashMap 內(nèi)部有個(gè)元素鏈表，直接遍歷鏈表就行。相對(duì)而言而高很多。

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

這也算一種空間換時(shí)間的策略吧。

get 方法當(dāng)然也是要重寫的。因?yàn)樾枰鶕?jù) accessOrder 更新鏈表。

總結(jié)

雪薇的總結(jié)的一下：

LinkedHashMap 內(nèi)部包含一個(gè)雙向鏈表維護(hù)順序，支持兩種順序——添加順序，訪問順序。

默認(rèn)就是按照添加順序來的，如果要改成訪問順序的話，構(gòu)造方法中的 accessOrder 需要設(shè)置成 true。這樣，每次調(diào)用 get 方法，就會(huì)將剛剛訪問的元素更新到鏈表尾部。

關(guān)于 LRU，在accessOrder 為 true 的模式下，你可以重寫 removeEldestEntry 方法，返回 size() > capacity，這樣，就可以刪除最不常訪問的元素。