1. 前言

最近在慕課網(wǎng)挑一些視頻學(xué)習(xí)的時(shí)候，剛好看到了LinkedHashMap來(lái)實(shí)現(xiàn)LRU，覺(jué)得還是一波比較秀的操作，特此記錄一下。

2. Demo

LinkedHashMap的輸出順序有倆種：

• 插入順序
• 訪問(wèn)順序

2.1 插入順序

插入順序顧名思義，就是按照插入的順序展示，比如：

    public static void main(String[] args) {

        LinkedHashMap<String, String> inserOrderMap = new LinkedHashMap<>();
        inserOrderMap.put("k1", "v1");
        inserOrderMap.put("k2", "v1");
        inserOrderMap.put("k3", "v1");
        inserOrderMap.put("k4", "v1");
        inserOrderMap.put("k5", "v1");
        inserOrderMap.put("k6", "v1");
        inserOrderMap.put("k7", "v1");
        inserOrderMap.put("k8", "v1");
        System.out.println(inserOrderMap);
}

結(jié)果：

{k1=v1, k2=v1, k3=v1, k4=v1, k5=v1, k6=v1, k7=v1, k8=v1}

可以看到，輸出的順序和插入的順序是保持一致的

2.2 訪問(wèn)順序

訪問(wèn)順序，就是如果元素被訪問(wèn)（比如說(shuō)通過(guò)get方法調(diào)用），那么該元素將被排序至最后：

    public static void main(String[] args) {
        LinkedHashMap<String, String> accessOrderMap = new LinkedHashMap<>(16,0.75F,true);
        accessOrderMap.put("k1", "v1");
        accessOrderMap.put("k2", "v1");
        accessOrderMap.put("k3", "v1");
        accessOrderMap.get("k2");
        System.out.println(accessOrderMap);
}

結(jié)果：

{k1=v1, k3=v1, k2=v1}

可以看到，這里在構(gòu)造LinkedHashMap的時(shí)候，傳入了三個(gè)構(gòu)造參數(shù)：

• 16：初始容量
• 0.75F：擴(kuò)容因子
• true：訪問(wèn)順序，true代表訪問(wèn)順序，false代表插入順序

而代碼中，我們首先依次插入k1、k2、k3，并且使用了k2，從結(jié)果可以看到，使用的k2元素被排到了最后

2.3 實(shí)現(xiàn)LRU

    public static void main(String[] args) {
        LruMap<String, String> lruMap = new LruMap<>(3);
        lruMap.put("k1","v1");
        lruMap.put("k2","v2");
        lruMap.put("k3","v3");

        lruMap.get("k1");
        lruMap.get("k2");
        lruMap.put("k4", "v4");
        System.out.println(lruMap);
    }

    private static class LruMap<K,V> extends LinkedHashMap {
        private int maxSize;
        LruMap(int maxSize) {
            super(16,0.75F, true);
            this.maxSize = maxSize;
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry eldest) {
            return this.size() > maxSize;
        }
    }

結(jié)果：

{k1=v1, k2=v2, k4=v4}

思路主要如下：首先創(chuàng)建一個(gè)LruMap，底層為一個(gè)訪問(wèn)順序的LinkeHashMap，并且指定了最大元素個(gè)數(shù)maxSize。之后重寫removeEldestEntry方法，指定淘汰最老的元素（也就是最靠前的元素），淘汰策略為元素大小超過(guò)maxSize。由于LinkeHashMap指定為訪問(wèn)順序，那么元素一旦被訪問(wèn)，就會(huì)被排到后面，自然不會(huì)被淘汰，這就符合LRU的思想了。

3. 源碼

只知道表面的使用方法是不夠的，還需要深入研究一下這騷操作的底層是如何實(shí)現(xiàn)的。

設(shè)想一下，當(dāng)訪問(wèn)元素的時(shí)候，元素會(huì)被排到最后面，那么，調(diào)整順序的操作應(yīng)該是發(fā)生在get方法中，查看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;
    }

可以看到，在獲取到e之后，并且accessOrder為true的情況下（accessOrder便是構(gòu)造LinkedHashMap的時(shí)候的第三個(gè)構(gòu)造參數(shù)），調(diào)用了afterNodeAccess方法，查看afterNodeAccess方法：

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

邏輯有點(diǎn)復(fù)雜，但其作用就是將e節(jié)點(diǎn)調(diào)整為尾節(jié)點(diǎn)。

4. 總結(jié)

學(xué)了多年java，也是第一次知道LinkedHashMap還可以指定輸出順序，知識(shí)還是不夠充足，還需要好好學(xué)習(xí)。