概述

• 通過維護(hù)一個(gè)雙向鏈表，LinkedHashMap保證了元素迭代的順序。
• 可以認(rèn)為是HashMap+LinkedList，即它既使用HashMap操作數(shù)據(jù)結(jié)構(gòu)，又使用LinkedList維護(hù)插入元素的先后順序

實(shí)現(xiàn)LRU算法緩存

1、LRU：Least Recently Used，最近最少使用，也就是說，當(dāng)緩存滿了，會(huì)優(yōu)先淘汰那些最近最不常訪問的數(shù)據(jù)
2、boolean型參數(shù)的構(gòu)造方法：LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder)
就是這個(gè)accessOrder，它表示：

false，所有的Entry按照插入的順序排列
true，所有的Entry按照訪問的順序排列

意思就是，如果有1 2 3這3個(gè)Entry，那么訪問了1，就把1移到尾部去，即2 3 1。每次訪問都把訪問的那個(gè)數(shù)據(jù)移到雙向隊(duì)列的尾部去，那么每次要淘汰數(shù)據(jù)的時(shí)候，雙向隊(duì)列最頭的那個(gè)數(shù)據(jù)不就是最不常訪問的那個(gè)數(shù)據(jù)了嗎？換句話說，雙向鏈表最頭的那個(gè)數(shù)據(jù)就是要淘汰的數(shù)據(jù)。
"訪問"，這個(gè)詞有兩層意思：

根據(jù)Key拿到Value，也就是get方法
修改Key對(duì)應(yīng)的Value，也就是put方法

還有一個(gè)判斷是否刪除最老數(shù)據(jù)的方法，默認(rèn)是返回false，即不刪除數(shù)據(jù)，我們使用LinkedHashMap實(shí)現(xiàn)LRU緩存的方法就是對(duì)LinkedHashMap實(shí)現(xiàn)簡(jiǎn)單的擴(kuò)展，擴(kuò)展方式有兩種，一種是inheritance，一種是delegation

//LinkedHashMap自帶的判斷是否刪除最老的元素方法，默認(rèn)返回false，即不刪除老數(shù)據(jù)
//我們要做的就是重寫這個(gè)方法，當(dāng)滿足一定條件時(shí)刪除老數(shù)據(jù)
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
}

LRU緩存LinkedHashMap(inheritance)實(shí)現(xiàn)

采用inheritance方式實(shí)現(xiàn)比較簡(jiǎn)單，而且實(shí)現(xiàn)了Map接口，在多線程環(huán)境使用時(shí)可以使用 Collections.synchronizedMap()方法實(shí)現(xiàn)線程安全操作

public class LRUCache2<K, V> extends LinkedHashMap<K, V> {
    private final int MAX_CACHE_SIZE;

    public LRUCache2(int cacheSize) {
        super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
        MAX_CACHE_SIZE = cacheSize;
    }

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

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<K, V> entry : entrySet()) {
            sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));
        }
        return sb.toString();
    }
}

這樣算是比較標(biāo)準(zhǔn)的實(shí)現(xiàn)吧，實(shí)際使用中這樣寫還是有些繁瑣，更實(shí)用的方法時(shí)像下面這樣寫，省去了單獨(dú)建一個(gè)類的麻煩

final int cacheSize = 100;
Map<String, String> map = new LinkedHashMap<String, String>((int) Math.ceil(cacheSize / 0.75f) + 1, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
    return size() > cacheSize;
    }
};

LRU緩存LinkedHashMap(delegation)實(shí)現(xiàn)

delegation方式實(shí)現(xiàn)更加優(yōu)雅一些，但是由于沒有實(shí)現(xiàn)Map接口，所以線程同步就需要自己搞定了

public class LRUCache3<K, V> {

    private final int MAX_CACHE_SIZE;
    private final float DEFAULT_LOAD_FACTOR = 0.75f;
    LinkedHashMap<K, V> map;

    public LRUCache3(int cacheSize) {
        MAX_CACHE_SIZE = cacheSize;
        //根據(jù)cacheSize和加載因子計(jì)算hashmap的capactiy，+1確保當(dāng)達(dá)到cacheSize上限時(shí)不會(huì)觸發(fā)hashmap的擴(kuò)容，
        int capacity = (int) Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTOR) + 1;
        map = new LinkedHashMap(capacity, DEFAULT_LOAD_FACTOR, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > MAX_CACHE_SIZE;
            }
        };
    }

    public synchronized void put(K key, V value) {
        map.put(key, value);
    }

    public synchronized V get(K key) {
        return map.get(key);
    }

    public synchronized void remove(K key) {
        map.remove(key);
    }

    public synchronized Set<Map.Entry<K, V>> getAll() {
        return map.entrySet();
    }

    public synchronized int size() {
        return map.size();
    }

    public synchronized void clear() {
        map.clear();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (Map.Entry entry : map.entrySet()) {
            sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));
        }
        return sb.toString();
    }
}

參考文獻(xiàn)

圖解集合6：LinkedHashMap
LRU緩存實(shí)現(xiàn)(Java)