LRU原理
LRU（Least recently used，最近最少使用）算法根據資料的曆史通路記錄來進行淘汰資料，其核心思想是“如果資料最近被通路過，那麼将來被通路的幾率也更高”。
- 最常見的實作是使用一個連結清單儲存緩存資料，詳細算法實作如下
- 新資料插入到連結清單頭部；
- 每當緩存命中（即緩存資料被通路），則将資料移到連結清單頭部；
-
當連結清單滿的時候，将連結清單尾部的資料丢棄。
【命中率】
當存在熱點資料時，LRU的效率很好，但偶發性的、周期性的批量操作會導緻LRU命中率急劇下降，緩存污染情況比較嚴重。
【複雜度】
實作簡單。
【代價】
命中時需要周遊連結清單，找到命中的資料塊索引，然後需要将資料移到頭部。
代碼實作
很多程式設計語言都有内置的哈希連結清單或者類似 LRU 功能的庫函數，但是為了幫大家了解算法的細節，我們用 Java 自己造輪子實作一遍 LRU 算法。
首先，我們把雙連結清單的節點類寫出來，為了簡化，key 和 val 都認為是 int 類型：
class Node {
public int key, val;
public Node next, prev;
public Node(int k, int v) {
this.key = k;
this.val = v;
}
}
然後依靠我們的 Node 類型建構一個雙連結清單，實作幾個要用到的 API，這些操作的時間複雜度均為 O(1) ：
class DoubleList {
// 在連結清單頭部添加節點 x
public void addFirst(Node x);
// 删除連結清單中的 x 節點（x 一定存在）
public void remove(Node x);
// 删除連結清單中最後一個節點，并傳回該節點
public Node removeLast();
// 傳回連結清單長度
public int size();
}
PS：這就是普通雙向連結清單的實作，為了讓讀者集中精力了解 LRU 算法的邏輯，就省略連結清單的具體代碼。
到這裡就能回答剛才“為什麼必須要用雙向連結清單”的問題了，因為我們需要删除操作。删除一個連結清單節點不光要得到該節點本身的指針，也需要操作其前驅節點的指針，而雙向連結清單才能支援直接查找前驅，保證操作的時間複雜度 O(1)。
有了雙向連結清單的實作，我們隻需要在 LRU 算法中把它和哈希表結合起來即可。我們先把邏輯理清楚:
如果能夠看懂上述邏輯，翻譯成代碼就很容易了解了：