算法必知 --- LRU 緩存淘汰算法
作者：_code_x
鏈接：https://www.jianshu.com/p/b7fed77324b9
寫在前
就是一種緩存淘汰策略。
計算機的緩存容量有限，如果緩存滿了就要刪除一些內容，給新內容騰位置。但問題是，刪除哪些內容呢？我們肯定希望刪掉哪些沒什麼用的緩存，而把有用的數據繼續留在緩存裏，方便之後繼續使用。那麼，什麼樣的數據，我們判定爲「有用的」的數據呢？
LRU 緩存淘汰算法就是一種常用策略。LRU 的全稱是 Least Recently Used，也就是說我們認爲最近使用過的數據應該是是「有用的」，很久都沒用過的數據應該是無用的，內存滿了就優先刪那些很久沒用過的數據。
算法描述
運用你所掌握的數據結構，設計和實現一個 LRU (最近最少使用) 緩存機制 。
實現 LRUCache 類：
-
LRUCache(int capacity) 以正整數作爲容量 capacity 初始化 LRU 緩存
-
int get(int key) 如果關鍵字 key 存在於緩存中，則返回關鍵字的值，否則返回 -1 。
-
void put(int key, int value) 如果關鍵字已經存在，則變更其數據值；如果關鍵字不存在，則插入該組「關鍵字 - 值」。當緩存容量達到上限時，它應該在寫入新數據之前刪除最久未使用的數據值，從而爲新的數據值留出空間。
注意哦，get 和 put 方法必須都是 O(1) 的時間複雜度！
示例：
/* 緩存容量爲 2 */
LRUCache cache = new LRUCache(2);
// 你可以把 cache 理解成一個隊列
// 假設左邊是隊頭，右邊是隊尾
// 最近使用的排在隊頭，久未使用的排在隊尾
// 圓括號表示鍵值對 (key, val)
cache.put(1, 1);
// cache = [(1, 1)]
cache.put(2, 2);
// cache = [(2, 2), (1, 1)]
cache.get(1); // 返回 1
// cache = [(1, 1), (2, 2)]
// 解釋：因爲最近訪問了鍵 1，所以提前至隊頭
// 返回鍵 1 對應的值 1
cache.put(3, 3);
// cache = [(3, 3), (1, 1)]
// 解釋：緩存容量已滿，需要刪除內容空出位置
// 優先刪除久未使用的數據，也就是隊尾的數據
// 然後把新的數據插入隊頭
cache.get(2); // 返回 -1 (未找到)
// cache = [(3, 3), (1, 1)]
// 解釋：cache 中不存在鍵爲 2 的數據
cache.put(1, 4);
// cache = [(1, 4), (3, 3)]
// 解釋：鍵 1 已存在，把原始值 1 覆蓋爲 4
// 不要忘了也要將鍵值對提前到隊頭算法設計
分析上面的操作過程，要讓 put 和 get 方法的時間複雜度爲 O(1)，我們可以總結出 cache 這個數據結構必要的條件：查找快，插入快，刪除快，有順序之分。
因爲顯然 cache 必須有順序之分，以區分最近使用的和久未使用的數據；而且我們要在 cache 中查找鍵是否已存在；如果容量滿了要刪除最後一個數據；每次訪問還要把數據插入到隊頭。
那麼，什麼數據結構同時符合上述條件呢？哈希表查找快，但是數據無固定順序；鏈表有順序之分，插入刪除快，但是查找慢。所以結合一下，形成一種新的數據結構：哈希鏈表。
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接後繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和後繼結點。一般我們都構造雙向循環鏈表。
**LRU 緩存算法的核心數據結構就是哈希鏈表：雙向鏈表和哈希表的結合體。**這個數據結構長這樣：
思想很簡單，就是藉助哈希表賦予了鏈表快速查找的特性嘛：可以快速查找某個 key 是否存在緩存（鏈表）中，同時可以快速刪除、添加節點。回想剛纔的例子，這種數據結構是不是完美解決了 LRU 緩存的需求？
代碼實現
- 首先定義雙端鏈表類（包括數據和記錄前驅 / 後繼節點的指針）
class DLinkedNode {
int key;
int value;
DLinkedNode pre;
DLinkedNode next;
public DLinkedNode() {};
public DLinkedNode(int key, int value) {
this.key = key;
this.value = value;
}
}- 雙向鏈表需要提供一些接口 api，便於我們操作，主要就是鏈表的一些操作，畫圖理解！
private void addFirst(DLinkedNode node) {
node.pre = head;
node.next = head.next;
head.next.pre = node;
head.next = node;
}
private void moveToFirst(DLinkedNode node) {
remove(node);
addFirst(node);
}
private void remove(DLinkedNode node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
// 刪除尾結點，並返回頭節點
private DLinkedNode removeLast() {
DLinkedNode ans = tail.pre;
remove(ans);
return ans;
}
private int getSize() {
return size;
}- 確定 LRU 緩存類的成員變量（鏈表長度、緩存容量和 map 映射等）和構造函數。注意：定義虛擬頭尾結點便於在頭部插入元素或者尋找尾部元素！並在構造函數初始化。
private Map<Integer, DLinkedNode> cache = new HashMap<>();
private int size;
private int capacity;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.pre = head;
}-
核心代碼：get 和 put 方法，都是先根據 key 獲取這個映射，根據映射節點的情況（有無）進行操作。注意：
-
get 和 put 都在使用，所以數據要提前！
-
put 操作如果改變了雙端鏈表長度（不是僅改變值），需要先判斷是否達到最大容量！
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
// 將該數據移到雙端隊列頭部
moveToFirst(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node != null) {
// 如果存在key，先修改值，然後移動到頭部
node.value = value;
moveToFirst(node);
} else {
// 如果key存在，先考慮是否超過容量限制
if (capacity == cache.size()) {
// 刪除尾結點和hash表中對應的映射！
DLinkedNode tail = removeLast();
cache.remove(tail.key);
--size;
}
DLinkedNode newNode = new DLinkedNode(key, value);
// 建立映射，並更新雙向鏈表頭部
cache.put(key, newNode);
addFirst(newNode);
++size;
}
}完整代碼如下：
class LRUCache {
class DLinkedNode {
int key;
int value;
DLinkedNode pre;
DLinkedNode next;
public DLinkedNode() {};
public DLinkedNode(int key, int value) {
this.key = key;
this.value = value;
}
}
private Map<Integer, DLinkedNode> cache = new HashMap<>();
private int size;
private int capacity;
// 虛擬頭尾結點便於在頭部插入元素或者尋找尾部元素！
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
// 使用僞頭部和僞尾部節點
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.pre = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
// 將該數據移到雙端隊列頭部
moveToFirst(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node != null) {
// 如果存在key，先修改值，然後移動到頭部
node.value = value;
moveToFirst(node);
} else {
// 如果key存在，先考慮是否超過容量限制
if (capacity == cache.size()) {
// 刪除尾結點和hash表中對應的映射！
DLinkedNode tail = removeLast();
cache.remove(tail.key);
--size;
}
DLinkedNode newNode = new DLinkedNode(key, value);
// 建立映射，並更新雙向鏈表頭部
cache.put(key, newNode);
addFirst(newNode);
++size;
}
}
private void addFirst(DLinkedNode node) {
node.pre = head;
node.next = head.next;
head.next.pre = node;
head.next = node;
}
private void moveToFirst(DLinkedNode node) {
remove(node);
addFirst(node);
}
private void remove(DLinkedNode node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
// 刪除尾結點，並返回頭節點
private DLinkedNode removeLast() {
DLinkedNode ans = tail.pre;
remove(ans);
return ans;
}
private int getSize() {
return size;
}
}總結與補充
-
LRU 緩存機制的核心：雙向鏈表（保證元素有序，且能快速的插入和刪除）+hash 表（可以快速查詢）
-
爲什麼使用雙向鏈表？因爲：對於刪除操作，使用雙向鏈表，我們可以在 O(1) 的時間複雜度下，找到被刪除節點的前節點。
-
**爲什麼要在鏈表中同時存鍵值，而不是隻存值？**因爲：當緩存容量滿了之後，我們不僅要在雙向鏈表中刪除最後一個節點（即最久沒有使用的節點），還要把 cache 中映射到該節點的 key 刪除，這個 key 只能有 Node 得到（即 hash 表不能通過值得到鍵）。
巨人的肩膀：
https://leetcode-cn.com/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/p4V_Clgngyq8ip75r7qNbQ