LRU 全稱是 Least Recently Used梁沧，即最近最久未使用算法檀何，它是頁面置換算法的一種。

原理

如果一個數(shù)據(jù)在最近一段時間沒有被訪問到廷支，那么在將來它被訪問的可能性也很小频鉴。也就是說，當(dāng)限定的空間已存滿數(shù)據(jù)時恋拍，應(yīng)當(dāng)把最久沒有被訪問到的數(shù)據(jù)淘汰垛孔。

LinkedHashMap介紹

LinkedHashMap繼承于HashMap，與HashMap的區(qū)別是LinkedHashMap是有序的施敢。

LinkedHashMap內(nèi)部采用雙向鏈表來記錄插入順序：

transient LinkedHashMapEntry<K,V> head;
transient LinkedHashMapEntry<K,V> tail;

LinkedHashMap并沒有重寫HashMap的put(key, value)方法周荐，而是重寫了newNode(hash, key, value, e),replacementNode(p, next),newTreeNode(hash, key, value, next),replacementTreeNode(p, next)方法，將key value插入到雙向鏈表中僵娃。

LinkedHashMap重寫了HashMap的get(key)方法概作，當(dāng)accessOrder為true時，會將Node移至鏈表尾默怨。

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

LruCache

LruCache內(nèi)部使用LinkedHashMap實現(xiàn)讯榕。

在LruCache的構(gòu)造方法中會創(chuàng)建LinkedHashMap，其中accessOrder默認(rèn)為true，這也就保證了在get(key)過程后會將結(jié)點放置隊尾愚屁。

public class LruCache<K, V> {

    private final LinkedHashMap<K, V> map;

    public LruCache(int maxSize) {
        this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
    }

    public void resize(int maxSize) {}

    public final V get(K key) {}

    public final V put(K key, V value) {}

    public void trimToSize(int maxSize) {}

    public void V remove(K key) {}

    protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}

    protected V create(K key) {}

    protected int sizeOf(K key, V value) {}
}

這里主要介紹下put(key, value)和get(key)兩個方法济竹。

put的過程很簡單，如果map中有舊值霎槐，則回調(diào)entryRemoved(evicted, key, oldValue, newValue)方法送浊。

最后會調(diào)用trimToSize(maxSize)方法，如果大小超過maxSize值丘跌，則會從頭部移除結(jié)點袭景。

public final V put(K key, V value) {
    V previous;
    synchronized (this) {
        size += safeSizeOf(key, value);
        previous = map.put(key, value);
        if (previous != null) {
            size -= safeSizeOf(key, previous);
        }
    }

    if (previous != null) {
        entryRemoved(false, key, previous, value);
    }

    trimToSize(maxSize);
    return previous;
}

get的過程稍微復(fù)雜些，如果取到了value則直接返回碍岔。如果沒取到浴讯，則調(diào)用create(key)方法嘗試創(chuàng)建默認(rèn)值，還要規(guī)避下沖突的情況蔼啦。

public final V get(K key) {
    if (key == null) {
        throw new NullPointerException("key == null");
    }

    V mapValue;
    synchronized (this) {
        mapValue = map.get(key);
        if (mapValue != null) {
            hitCount++;
            return mapValue;
        }
        missCount++;
    }

    /*
     * Attempt to create a value. This may take a long time, and the map
     * may be different when create() returns. If a conflicting value was
     * added to the map while create() was working, we leave that value in
     * the map and release the created value.
     */

    V createdValue = create(key);
    if (createdValue == null) {
        return null;
    }

    synchronized (this) {
        createCount++;
        mapValue = map.put(key, createdValue);

        if (mapValue != null) {
            // There was a conflict so undo that last put
            map.put(key, mapValue);
        } else {
            size += safeSizeOf(key, createdValue);
        }
    }

    if (mapValue != null) {
        entryRemoved(false, key, createdValue, mapValue);
        return mapValue;
    } else {
        trimToSize(maxSize);
        return createdValue;
    }
}