算法必知 --- LRU緩存淘汰算法
作者：_code_x
鏈接：https://www.jianshu.com/p/b7fed77324b9
寫在前
就是一種緩存淘汰策略。
計(jì)算機(jī)的緩存容量有限，如果緩存滿了就要?jiǎng)h除一些內(nèi)容，給新內(nèi)容騰位置。但問題是，刪除哪些內(nèi)容呢？我們肯定希望刪掉哪些沒什么用的緩存，而把有用的數(shù)據(jù)繼續(xù)留在緩存里，方便之后繼續(xù)使用。那么，什么樣的數(shù)據(jù)，我們判定為「有用的」的數(shù)據(jù)呢？
LRU 緩存淘汰算法就是一種常用策略。LRU 的全稱是 Least Recently Used，也就是說我們認(rèn)為最近使用過的數(shù)據(jù)應(yīng)該是是「有用的」，很久都沒用過的數(shù)據(jù)應(yīng)該是無用的，內(nèi)存滿了就優(yōu)先刪那些很久沒用過的數(shù)據(jù)。
算法描述
運(yùn)用你所掌握的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)和實(shí)現(xiàn)一個(gè) LRU (最近最少使用) 緩存機(jī)制 。
實(shí)現(xiàn) LRUCache 類：
LRUCache(int capacity) 以正整數(shù)作為容量 capacity 初始化 LRU 緩存
int get(int key) 如果關(guān)鍵字 key 存在于緩存中，則返回關(guān)鍵字的值，否則返回 -1 。
void put(int key, int value) 如果關(guān)鍵字已經(jīng)存在，則變更其數(shù)據(jù)值；如果關(guān)鍵字不存在，則插入該組「關(guān)鍵字-值」。當(dāng)緩存容量達(dá)到上限時(shí)，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。
注意哦，get 和 put 方法必須都是 O(1) 的時(shí)間復(fù)雜度！
示例：
/* 緩存容量為 2 */
LRUCache cache = new LRUCache(2);
// 你可以把 cache 理解成一個(gè)隊(duì)列
// 假設(shè)左邊是隊(duì)頭，右邊是隊(duì)尾
// 最近使用的排在隊(duì)頭，久未使用的排在隊(duì)尾
// 圓括號(hào)表示鍵值對 (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)]
// 解釋：因?yàn)樽罱L問了鍵 1，所以提前至隊(duì)頭
// 返回鍵 1 對應(yīng)的值 1
cache.put(3, 3);
// cache = [(3, 3), (1, 1)]
// 解釋：緩存容量已滿，需要?jiǎng)h除內(nèi)容空出位置
// 優(yōu)先刪除久未使用的數(shù)據(jù)，也就是隊(duì)尾的數(shù)據(jù)
// 然后把新的數(shù)據(jù)插入隊(duì)頭
cache.get(2); // 返回 -1 (未找到)
// cache = [(3, 3), (1, 1)]
// 解釋：cache 中不存在鍵為 2 的數(shù)據(jù)
cache.put(1, 4);
// cache = [(1, 4), (3, 3)]
// 解釋：鍵 1 已存在，把原始值 1 覆蓋為 4
// 不要忘了也要將鍵值對提前到隊(duì)頭
算法設(shè)計(jì)
分析上面的操作過程，要讓 put 和 get 方法的時(shí)間復(fù)雜度為 O(1)，我們可以總結(jié)出 cache 這個(gè)數(shù)據(jù)結(jié)構(gòu)必要的條件：查找快，插入快，刪除快，有順序之分。
因?yàn)轱@然 cache 必須有順序之分，以區(qū)分最近使用的和久未使用的數(shù)據(jù)；而且我們要在 cache 中查找鍵是否已存在；如果容量滿了要?jiǎng)h除最后一個(gè)數(shù)據(jù)；每次訪問還要把數(shù)據(jù)插入到隊(duì)頭。
那么，什么數(shù)據(jù)結(jié)構(gòu)同時(shí)符合上述條件呢？哈希表查找快，但是數(shù)據(jù)無固定順序；鏈表有順序之分，插入刪除快，但是查找慢。所以結(jié)合一下，形成一種新的數(shù)據(jù)結(jié)構(gòu)：哈希鏈表。
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開始，都可以很方便地訪問它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。一般我們都構(gòu)造雙向循環(huán)鏈表。
LRU 緩存算法的核心數(shù)據(jù)結(jié)構(gòu)就是哈希鏈表：雙向鏈表和哈希表的結(jié)合體。這個(gè)數(shù)據(jù)結(jié)構(gòu)長這樣：
思想很簡單，就是借助哈希表賦予了鏈表快速查找的特性嘛：可以快速查找某個(gè) key 是否存在緩存（鏈表）中，同時(shí)可以快速刪除、添加節(jié)點(diǎn)?；叵雱偛诺睦?，這種數(shù)據(jù)結(jié)構(gòu)是不是完美解決了 LRU 緩存的需求？
代碼實(shí)現(xiàn)
首先定義雙端鏈表類（包括數(shù)據(jù)和記錄前驅(qū)/后繼節(jié)點(diǎn)的指針）
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;
}
// 刪除尾結(jié)點(diǎn)，并返回頭節(jié)點(diǎn)
private DLinkedNode removeLast() {
DLinkedNode ans = tail.pre;
remove(ans);
return ans;
}
private int getSize() {
return size;
}
確定LRU緩存類的成員變量（鏈表長度、緩存容量和map映射等）和構(gòu)造函數(shù)。注意：定義虛擬頭尾結(jié)點(diǎn)便于在頭部插入元素或者尋找尾部元素！并在構(gòu)造函數(shù)初始化。
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方法，都是先根據(jù)key獲取這個(gè)映射，根據(jù)映射節(jié)點(diǎn)的情況（有無）進(jìn)行操作。注意：
get和put都在使用，所以數(shù)據(jù)要提前！
put操作如果改變了雙端鏈表長度（不是僅改變值），需要先判斷是否達(dá)到最大容量！
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
// 將該數(shù)據(jù)移到雙端隊(duì)列頭部
moveToFirst(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node != null) {
// 如果存在key，先修改值，然后移動(dòng)到頭部
node.value = value;
moveToFirst(node);
} else {
// 如果key存在，先考慮是否超過容量限制
if (capacity == cache.size()) {
// 刪除尾結(jié)點(diǎn)和hash表中對應(yīng)的映射！
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;
// 虛擬頭尾結(jié)點(diǎn)便于在頭部插入元素或者尋找尾部元素！
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
// 使用偽頭部和偽尾部節(jié)點(diǎn)
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;
}
// 將該數(shù)據(jù)移到雙端隊(duì)列頭部
moveToFirst(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node != null) {
// 如果存在key，先修改值，然后移動(dòng)到頭部
node.value = value;
moveToFirst(node);
} else {
// 如果key存在，先考慮是否超過容量限制
if (capacity == cache.size()) {
// 刪除尾結(jié)點(diǎn)和hash表中對應(yīng)的映射！
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;
}
// 刪除尾結(jié)點(diǎn)，并返回頭節(jié)點(diǎn)
private DLinkedNode removeLast() {
DLinkedNode ans = tail.pre;
remove(ans);
return ans;
}
private int getSize() {
return size;
}
}
總結(jié)與補(bǔ)充
LRU緩存機(jī)制的核心：雙向鏈表（保證元素有序，且能快速的插入和刪除）+hash表（可以快速查詢）
為什么使用雙向鏈表？因?yàn)椋簩τ趧h除操作，使用雙向鏈表，我們可以在O(1)的時(shí)間復(fù)雜度下，找到被刪除節(jié)點(diǎn)的前節(jié)點(diǎn)。
為什么要在鏈表中同時(shí)存鍵值，而不是只存值？因?yàn)椋寒?dāng)緩存容量滿了之后，我們不僅要在雙向鏈表中刪除最后一個(gè)節(jié)點(diǎn)（即最久沒有使用的節(jié)點(diǎn)），還要把cache中映射到該節(jié)點(diǎn)的key刪除，這個(gè)key只能有Node得到（即hash表不能通過值得到鍵）。
巨人的肩膀：
https://leetcode-cn.com/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/