在最近的面試中，我曾被多次問到，怎么實現(xiàn)一個最近最少使用（LRU）的緩存。緩存可以通過哈希表來實現(xiàn)，然而為這個緩存增加大小限制會變成另一個有意思的問題。現(xiàn)在我們看一下怎么實現(xiàn)。

[[140419]]

最近最少使用緩存的回收

為了實現(xiàn)緩存回收，我們需要很容易做到：

• 查詢出最近最晚使用的項

• 給最近使用的項做一個標記

鏈表可以實現(xiàn)這兩個操作。檢測最近最少使用的項只需要返回鏈表的尾部。標記一項為最近使用的項只需要從當前位置移除，然后將該項放置到頭部。比較困難的事情是怎么快速的在鏈表中找到該項。

哈希表的幫助

看一下我們工具箱中的數(shù)據(jù)結構，哈希表可以在（消耗）常量的時間內索引到某個對象。如果我們創(chuàng)建一個形如key->鏈表節(jié)點的哈希表，我們就能夠在常量時間內找到最近使用的節(jié)點。更甚的是，我們也能夠在常量時間內判斷節(jié)點的是否存在（或不存在）；

找到這個節(jié)點后，我們就能將這個節(jié)點移動到鏈表的最前端，標記為最近使用的項了。

Java的捷徑

據(jù)我所知，很少有一種編程語言的標準庫中有通用的數(shù)據(jù)結構能提供上述功能的。這是一種混合的數(shù)據(jù)結構，我們需要在哈希表的基礎上建立一個鏈表。但是 Java已經為我們提供了這種形式的數(shù)據(jù)結構-LinkedHashMap！它甚至提供可覆蓋回收策略的方法（見removeEldestEntry文檔）。***需要我們注意的事情是，改鏈表的順序是插入的順序，而不是訪問的順序。但是，有一個構造函數(shù)提供了一個選項，可以使用訪問的順序（見文檔）。

無需多說：

import java.util.LinkedHashMap; 
import java.util.Map; 
 
public LRUCache<K, V> extends LinkedHashMap<K, V> { 
  private int cacheSize; 
 
  public LRUCache(int cacheSize) { 
    super(16, 0.75, true); 
    this.cacheSize = cacheSize; 
  } 
 
  protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { 
    return size() >= cacheSize; 
  } 
}