更多內容，歡迎關注微信公眾號：全菜工程師小輝~

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 extends LinkedHashMap { // 定義緩存的容量 private int capacity; // 帶參數的構造器 LRULinkedHashMap(int capacity){ // 第三個參數為accessOrder super(16,0.75f,true); // 傳入指定的緩存最大容量 this.capacity=capacity; } // 實現LRU的關鍵方法，如果map里面的元素個數大于了緩存最大容量，則刪除鏈表的頂端元素 @Override public boolean removeEldestEntry(Map.Entry eldest){ return size()>capacity; } }

更多內容，歡迎關注微信公眾號：全菜工程師小輝~

總結

以上是生活随笔為你收集整理的java 最少使用(lru)置换算法_LRU算法详解及最简单的Java实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。