LRU全稱是Least?Recently Used，即最近最久未使用的意思。

LRU算法的設計原則是：如果一個數據在最近一段時間沒有被訪問到，那么在將來它被訪問的可能性也很小。也就是說，當限定的空間已存滿數據時，應當把最久沒有被訪問到的數據淘汰。

實現LRU

?????
1.用一個數組來存儲數據，給每一個數據項標記一個訪問時間戳，每次插入新數據項的時候，先把數組中存在的數據項的時間戳自增，并將新數據項的時間戳置為0并插入到數組中。每次訪問數組中的數據項的時候，將被訪問的數據項的時間戳置為0。當數組空間已滿時，將時間戳最大的數據項淘汰。

2.利用一個鏈表來實現，每次新插入數據的時候將新數據插到鏈表的頭部；每次緩存命中（即數據被訪問），則將數據移到鏈表頭部；那么當鏈表滿的時候，就將鏈表尾部的數據丟棄。

3.利用鏈表和hashmap。當需要插入新的數據項的時候，如果新數據項在鏈表中存在（一般稱為命中），則把該節點移到鏈表頭部，如果不存在，則新建一個節點，放到鏈表頭部，若緩存滿了，則把鏈表最后一個節點刪除即可。在訪問數據的時候，如果數據項在鏈表中存在，則把該節點移到鏈表頭部，否則返回-1。這樣一來在鏈表尾部的節點就是最近最久未訪問的數據項。

對于第一種方法，需要不停地維護數據項的訪問時間戳，另外，在插入數據、刪除數據以及訪問數據時，時間復雜度都是O(n)。對于第二種方法，鏈表在定位數據的時候時間復雜度為O(n)。所以在一般使用第三種方式來是實現LRU算法。
實現方案

使用LinkedHashMap實現
?????LinkedHashMap底層就是用的HashMap加雙鏈表實現的，而且本身已經實現了按照訪問順序的存儲。此外，LinkedHashMap中本身就實現了一個方法removeEldestEntry用于判斷是否需要移除最不常讀取的數，方法默認是直接返回false，不會移除元素，所以需要重寫該方法。即當緩存滿后就移除最不常用的數。
????
public class LRU<K,V> {
?
? private static final float hashLoadFactory = 0.75f;
? private LinkedHashMap<K,V> map;
? private int cacheSize;
?
? public LRU(int cacheSize) {
? ? this.cacheSize = cacheSize;
? ? int capacity = (int)Math.ceil(cacheSize / hashLoadFactory) + 1;
? ? map = new LinkedHashMap<K,V>(capacity, hashLoadFactory, true){
? ? ? private static final long serialVersionUID = 1;
?
? ? ? @Override
? ? ? protected boolean removeEldestEntry(Map.Entry eldest) {
? ? ? ? return size() > LRU.this.cacheSize;
? ? ? }
? ? };
? }
?
? public synchronized V get(K key) {
? ? return map.get(key);
? }
?
? public synchronized void put(K key, V value) {
? ? map.put(key, value);
? }
?
? public synchronized void clear() {
? ? map.clear();
? }
?
? public synchronized int usedSize() {
? ? return map.size();
? }
?
? public void print() {
? ? for (Map.Entry<K, V> entry : map.entrySet()) {
? ? ? System.out.print(entry.getValue() + "--");
? ? }
? ? System.out.println();
? }
}

當存在熱點數據時，LRU的效率很好，但偶發性的、周期性的批量操作會導致LRU命中率急劇下降，緩存污染情況比較嚴重。
擴展

1.LRU-K

LRU-K中的K代表最近使用的次數，因此LRU可以認為是LRU-1。LRU-K的主要目的是為了解決LRU算法“緩存污染”的問題，其核心思想是將“最近使用過1次”的判斷標準擴展為“最近使用過K次”。
相比LRU，LRU-K需要多維護一個隊列，用于記錄所有緩存數據被訪問的歷史。只有當數據的訪問次數達到K次的時候，才將數據放入緩存。當需要淘汰數據時，LRU-K會淘汰第K次訪問時間距當前時間最大的數據。

數據第一次被訪問時，加入到歷史訪問列表，如果書籍在訪問歷史列表中沒有達到K次訪問，則按照一定的規則（FIFO,LRU）淘汰；當訪問歷史隊列中的數據訪問次數達到K次后，將數據索引從歷史隊列中刪除，將數據移到緩存隊列中，并緩存數據，緩存隊列重新按照時間排序；緩存數據隊列中被再次訪問后，重新排序，需要淘汰數據時，淘汰緩存隊列中排在末尾的數據，即“淘汰倒數K次訪問離現在最久的數據”。
LRU-K具有LRU的優點，同時還能避免LRU的缺點，實際應用中LRU-2是綜合最優的選擇。由于LRU-K還需要記錄那些被訪問過、但還沒有放入緩存的對象，因此內存消耗會比LRU要多。
2.two queue

Two?queues（以下使用2Q代替）算法類似于LRU-2，不同點在于2Q將LRU-2算法中的訪問歷史隊列（注意這不是緩存數據的）改為一個FIFO緩存隊列，即：2Q算法有兩個緩存隊列，一個是FIFO隊列，一個是LRU隊列。當數據第一次訪問時，2Q算法將數據緩存在FIFO隊列里面，當數據第二次被訪問時，則將數據從FIFO隊列移到LRU隊列里面，兩個隊列各自按照自己的方法淘汰數據。

新訪問的數據插入到FIFO隊列中，如果數據在FIFO隊列中一直沒有被再次訪問，則最終按照FIFO規則淘汰；如果數據在FIFO隊列中再次被訪問到，則將數據移到LRU隊列頭部，如果數據在LRU隊列中再次被訪問，則將數據移動LRU隊列頭部，LRU隊列淘汰末尾的數據。
3.Multi Queue(MQ)

?????MQ算法根據訪問頻率將數據劃分為多個隊列，不同的隊列具有不同的訪問優先級，其核心思想是：優先緩存訪問次數多的數據。詳細的算法結構圖如下，Q0，Q1....Qk代表不同的優先級隊列，Q-history代表從緩存中淘汰數據，但記錄了數據的索引和引用次數的隊列：

新插入的數據放入Q0，每個隊列按照LRU進行管理，當數據的訪問次數達到一定次數，需要提升優先級時，將數據從當前隊列中刪除，加入到高一級隊列的頭部；為了防止高優先級數據永遠不會被淘汰，當數據在指定的時間里沒有被訪問時，需要降低優先級，將數據從當前隊列刪除，加入到低一級的隊列頭部；需要淘汰數據時，從最低一級隊列開始按照LRU淘汰，每個隊列淘汰數據時，將數據從緩存中刪除，將數據索引加入Q-history頭部。如果數據在Q-history中被重新訪問，則重新計算其優先級，移到目標隊列頭部。Q-history按照LRU淘汰數據的索引。

MQ需要維護多個隊列，且需要維護每個數據的訪問時間，復雜度比LRU高。
LRU算法對比

對比點
對比
命中率
LRU-2?>?MQ(2)?>?2Q?>?LRU
復雜度
LRU-2?>?MQ(2)?>?2Q?>?LRU
代價
LRU-2??>?MQ(2)?>?2Q?>?LRU

?

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的LRU实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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