LRU（Least recently used，最近最少使用）算法根據數據的歷史訪問記錄來進行淘汰數據，其核心思想是“如果數據最近被訪問過，那么將來被訪問的幾率也更高”。
LRU算法的表現
- 新數據插入到容器頭部；
- 每當緩存命中（即緩存數據被訪問），則將數據移到容器頭部；
- 當容器滿的時候，將容器尾部的數據丟棄。
實現LRU的方法
- 用一個數組來存儲數據，給每一個數據項標記一個訪問時間戳，每次插入新數據項的時候，先把數組中所有的數據項的時間戳自增，并將新數據項的時間戳置為0并插入到數組中。每次訪問數組中的數據項的時候，將被訪問的數據項的時間戳置為0。當數組空間已滿時，將時間戳最大的數據項淘汰。
- 利用一個鏈表來實現，每次新插入數據的時候將新數據插到鏈表的頭部；每次緩存命中（即數據被訪問），則將數據移到鏈表頭部；那么當鏈表滿的時候，就將鏈表尾部的數據丟棄。
- 利用鏈表和HashMap。當需要插入新的數據項的時候，如果新數據項在鏈表中存在（一般稱為命中），則把該節點移到鏈表頭部，如果不存在，則新建一個節點，放到鏈表頭部，若緩存滿了，則把鏈表最后一個節點刪除即可。在訪問數據的時候，如果數據項在鏈表中存在，則把該節點移到鏈表頭部，否則返回-1。這樣一來在鏈表尾部的節點就是最近最久未訪問的數據項。HashMap提供快速定位功能，具體可以參見下文。
比較三種方法優劣：
對于第一種方法，需要不停地維護數據項的訪問時間戳，另外，在插入數據、刪除數據以及訪問數據時，時間復雜度都是O(n)。對于第二種方法，鏈表在定位數據的時候時間復雜度為O(n)。所以在一般使用第三種方式來是實現LRU算法。
LinkedHashMap的實現方案
LinkedHashMap繼承于HashMap，來一張LinkedHashMap的結構圖
LinkedHashMap的結構圖
其中next是用于維護HashMap指定table位置上連接的Entry的順序的，before、after是用于維護Entry插入的先后順序的
LinkedHashMap底層就是用的HashMap加雙鏈表實現的。實現LRU算法主要有兩個注意的地方：
- LinkedHashMap本身已經實現了按照訪問順序的存儲。LinkedHashMap的構造函數中有一個accessOrder參數，平時使用LinkedHashMap一般該值為false。不過在LRU算法實現中我們要設置該參數為true，當構造函數中為true時，我們每次調用get方法時都會調用該方法，將我們訪問的Node移動到最后，使之成為尾部節點，從而改變了數據在LinkedHashMap中的存儲順序。
- LinkedHashMap中本身就實現了一個方法removeEldestEntry用于判斷是否需要移除最不常讀取的數，方法默認是直接返回false，不會移除元素，所以需要重寫該方法。即當緩存滿后就移除最不常用的數。
所以使用LinkedHashMap很簡單的實現了LRU算法，代碼如下。另外如果生產中使用的話，一定要記得線程安全加鎖。
class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V> {
// 定義緩存的容量
private int capacity;
// 帶參數的構造器
LRULinkedHashMap(int capacity){
// 第三個參數為accessOrder
super(16,0.75f,true);
// 傳入指定的緩存最大容量
this.capacity=capacity;
}
// 實現LRU的關鍵方法，如果map里面的元素個數大于了緩存最大容量，則刪除鏈表的頂端元素
@Override
public boolean removeEldestEntry(Map.Entry<K, V> eldest){
return size()>capacity;
}
}
更多內容，歡迎關注微信公眾號：全菜工程師小輝~
