背景

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

[[142638]]

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

實(shí)現(xiàn)

自己實(shí)現(xiàn)LRUCache只需覆蓋removeEldestEntry這個(gè)方法即可，代碼如下

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

以上代碼需要一個(gè)MAX_ELEMENTS變量限制***存儲(chǔ)節(jié)點(diǎn)個(gè)數(shù)，插入節(jié)點(diǎn)時(shí)判斷 如果當(dāng) 前節(jié)點(diǎn)個(gè)數(shù)已經(jīng)超過(guò)了這個(gè)值則會(huì)根據(jù)LRU策略將訪問(wèn)最少的那個(gè)節(jié)點(diǎn)刪除，這里需要注意，默認(rèn)LinkedHashMap保證的是插入順序，也就是節(jié)點(diǎn)按 照插入先后來(lái)排序的，所以就算刪除也是刪除***插入的節(jié)點(diǎn)，但是我們?cè)跇?gòu)造函數(shù)中傳入了一個(gè)true，這個(gè)參數(shù)決定了LinkedHashMap內(nèi)部的節(jié) 點(diǎn)按照什么方式排序，參數(shù)為true時(shí)說(shuō)明內(nèi)部節(jié)點(diǎn)按照最近訪問(wèn)的時(shí)間排序，為false時(shí)說(shuō)明按照插入順序排序。至此已完成了一個(gè)簡(jiǎn)易的 LRUCache實(shí)現(xiàn)。

注意

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