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;
}
}
以上代碼需要一個MAX_ELEMENTS變量限制***存儲節點個數，插入節點時判斷 如果當 前節點個數已經超過了這個值則會根據LRU策略將訪問最少的那個節點刪除，這里需要注意，默認LinkedHashMap保證的是插入順序，也就是節點按 照插入先后來排序的，所以就算刪除也是刪除***插入的節點，但是我們在構造函數中傳入了一個true，這個參數決定了LinkedHashMap內部的節 點按照什么方式排序，參數為true時說明內部節點按照最近訪問的時間排序，為false時說明按照插入順序排序。至此已完成了一個簡易的 LRUCache實現。
注意
由于LinkedHahsMap本身實現不是線程安全的，也就是說這個LRUCache也不是線程安全的，如果想要能多線程訪問的話，可以這樣使用 它：LRUCache cache = Collections.synchronizedMap（new LRUCache(10, 10)）。這樣cache就可以在多線程下執行get/put等操作了，但是，用這種方式得到的cache在多線程遍歷時還是不安全的。所以不能在多線程 下遍歷cache，官方文檔也建議在遍歷synchronizedmap時使用map本身做同步。
