背景

LinkedHashMap繼承自HashMap，內(nèi)部提供了一個removeEldestEntry方法，該方法正是實現(xiàn)LRU策略的關(guān)鍵所在， 且HashMap內(nèi)部專門為LinkedHashMap提供了3個專用回調(diào)方法，afterNodeAccess、 afterNodeInsertion、afterNodeRemoval，這3個方法的字面意思非常容易理解，就是節(jié)點訪問后、節(jié)點插入后、節(jié)點刪除后 分別執(zhí)行的行為?；谝陨闲袨長inkedHashMap就可以實現(xiàn)一個LRUCache的功能了。

[[142638]]

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

實現(xiàn)

自己實現(xiàn)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變量限制***存儲節(jié)點個數(shù)，插入節(jié)點時判斷 如果當 前節(jié)點個數(shù)已經(jīng)超過了這個值則會根據(jù)LRU策略將訪問最少的那個節(jié)點刪除，這里需要注意，默認LinkedHashMap保證的是插入順序，也就是節(jié)點按 照插入先后來排序的，所以就算刪除也是刪除***插入的節(jié)點，但是我們在構(gòu)造函數(shù)中傳入了一個true，這個參數(shù)決定了LinkedHashMap內(nèi)部的節(jié) 點按照什么方式排序，參數(shù)為true時說明內(nèi)部節(jié)點按照最近訪問的時間排序，為false時說明按照插入順序排序。至此已完成了一個簡易的 LRUCache實現(xiàn)。

注意

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