Java簡易LRU緩存實現

背景

LinkedHashMap繼承自HashMap，內部提供了一個removeEldestEntry方法，該方法正是實現LRU策略的關鍵所在，且HashMap內部專門為LinkedHashMap提供了3個專用回調方法，afterNodeAccess、afterNodeInsertion、afterNodeRemoval，這3個方法的字面意思非常容易理解，就是節點訪問后、節點插入后、節點刪除后分別執行的行為。基于以上行為LinkedHashMap就可以實現一個LRUCache的功能了。

關于LinkedHashMap的eldest：eldest字面意思為最老的，LinkedHashMap中有個叫做accessOrder的字段，當accessOrder為true時表示LinkedHashMap內部節點按照訪問次數排序，最老的節點也就是訪問最少的節點。當accessOrder為false時表示LinkedHashMap內部節點按照插入順序排序，最老的節點也就是最早插入的節點，該值默認為false。

實現

自己實現LRUCache只需覆蓋removeEldestEntry這個方法即可，代碼如下

private static class LRUCache<K, V> extends LinkedHashMap<K, V>
    {
        private static final long serialVersionUID = -9111855653176630846L;
        private static int MAX_ELEMENTS;


    public LRUCache(int initCap, int maxSize) throws IllegalArgumentException
    {
        super(initCap, 0.75f, true);
        if (maxSize < 0)
            throw new IllegalArgumentException();
        MAX_ELEMENTS = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest)
    {
        return size() > MAX_ELEMENTS;
    }
}</pre> <p><span style="line-height:1.5;">以上代碼需要一個MAX_ELEMENTS變量限制最大存儲節點個數，插入節點時判斷 </span><span style="line-height:1.5;">如果</span><span style="line-height:1.5;">當前節點個數已經超過了這個值則會根據LRU策略將訪問最少的那個節點刪除，這里需要注意，默認LinkedHashMap保證的是插入順序，也就是節點按照插入先后來排序的，所以就算刪除也是刪除最先插入的節點，但是我們在構造函數中傳入了一個true，這個參數決定了LinkedHashMap內部的節點按照什么方式排序，參數為true時說明內部節點按照最近訪問的時間排序，為false時說明按照插入順序排序。至此已完成了一個簡易的LRUCache實現。</span> </p>

注意 

由于LinkedHahsMap本身實現不是線程安全的，也就是說這個LRUCache也不是線程安全的，如果想要能多線程訪問的話，可以這樣使用它：LRUCache cache = Collections.synchronizedMap（new LRUCache(10, 10)）。這樣cache就可以在多線程下執行get\put等操作了，但是，用這種方式得到的cache在多線程遍歷時還是不安全的。所以不能在多線程下遍歷cache，官方文檔也建議在遍歷synchronizedmap時使用map本身做同步