LRU（Least recently used企量，最近最少使用）算法根據(jù)數(shù)據(jù)的歷史訪問(wèn)記錄來(lái)進(jìn)行淘汰數(shù)據(jù)，
其核心思想是“如果數(shù)據(jù)最近被訪問(wèn)過(guò)，那么將來(lái)被訪問(wèn)的幾率也更高”揪利。
實(shí)現(xiàn)
最常見的實(shí)現(xiàn)是使用一個(gè)鏈表保存緩存數(shù)據(jù)歉提，詳細(xì)算法實(shí)現(xiàn)如下：
- 新數(shù)據(jù)插入到鏈表頭部笛坦；
- 每當(dāng)緩存命中（即緩存數(shù)據(jù)被訪問(wèn)）区转，則將數(shù)據(jù)移到鏈表頭部；
- 當(dāng)鏈表滿的時(shí)候版扩，將鏈表尾部的數(shù)據(jù)丟棄废离。
分析
【命中率】
當(dāng)存在熱點(diǎn)數(shù)據(jù)時(shí)，LRU的效率很好礁芦，但偶發(fā)性的蜻韭、周期性的批量操作會(huì)導(dǎo)致LRU命中率急劇下降，緩存污染情況比較嚴(yán)重柿扣。
【復(fù)雜度】
實(shí)現(xiàn)簡(jiǎn)單肖方。
【代價(jià)】
命中時(shí)需要遍歷鏈表，找到命中的數(shù)據(jù)塊索引未状，然后需要將數(shù)據(jù)移到頭部俯画。當(dāng)數(shù)據(jù)量較大時(shí)，遍歷鏈表效率較低司草。
LRU-K
原理
LRU-K中的K代表最近使用的次數(shù)艰垂，因此LRU可以認(rèn)為是LRU-1。
LRU-K的主要目的是為了解決LRU算法“緩存污染”的問(wèn)題埋虹，其核心思想是將“最近使用過(guò)1次”的判斷標(biāo)準(zhǔn)擴(kuò)展為“最近使用過(guò)K次”猜憎。
實(shí)現(xiàn)
相比LRU，LRU-K需要多維護(hù)一個(gè)隊(duì)列搔课，用于記錄所有緩存數(shù)據(jù)被訪問(wèn)的歷史胰柑。
只有當(dāng)數(shù)據(jù)的訪問(wèn)次數(shù)達(dá)到K次的時(shí)候，才將數(shù)據(jù)放入緩存辣辫。
當(dāng)需要淘汰數(shù)據(jù)時(shí)旦事，LRU-K會(huì)淘汰第K次訪問(wèn)時(shí)間距當(dāng)前時(shí)間最大的數(shù)據(jù)。詳細(xì)實(shí)現(xiàn)如下：
- 數(shù)據(jù)第一次被訪問(wèn)急灭，加入到訪問(wèn)歷史列表姐浮；
- 如果數(shù)據(jù)在訪問(wèn)歷史列表里后沒有達(dá)到K次訪問(wèn)，則按照一定規(guī)則（FIFO葬馋，LRU）淘汰卖鲤；
- 當(dāng)訪問(wèn)歷史隊(duì)列中的數(shù)據(jù)訪問(wèn)次數(shù)達(dá)到K次后，將數(shù)據(jù)索引從歷史隊(duì)列刪除畴嘶，將數(shù)據(jù)移到緩存隊(duì)列中蛋逾，并緩存此數(shù)據(jù)，緩存隊(duì)列重新按照時(shí)間排序窗悯；
- 緩存數(shù)據(jù)隊(duì)列中被再次訪問(wèn)后区匣，重新排序；
- 需要淘汰數(shù)據(jù)時(shí)蒋院，淘汰緩存隊(duì)列中排在末尾的數(shù)據(jù)亏钩，即：淘汰“倒數(shù)第K次訪問(wèn)離現(xiàn)在最久”的數(shù)據(jù)莲绰。
LRU-K具有LRU的優(yōu)點(diǎn)，同時(shí)能夠避免LRU的缺點(diǎn)姑丑，實(shí)際應(yīng)用中LRU-2是綜合各種因素后最優(yōu)的選擇蛤签，
LRU-3或者更大的K值命中率會(huì)高，但適應(yīng)性差栅哀，需要大量的數(shù)據(jù)訪問(wèn)才能將歷史訪問(wèn)記錄清除掉震肮。
分析
【命中率】
LRU-K降低了“緩存污染”帶來(lái)的問(wèn)題，命中率比LRU要高留拾。
【復(fù)雜度】
LRU-K隊(duì)列是一個(gè)優(yōu)先級(jí)隊(duì)列戳晌，算法復(fù)雜度和代價(jià)比較高。
【代價(jià)】
由于LRU-K還需要記錄那些被訪問(wèn)過(guò)痴柔、但還沒有放入緩存的對(duì)象躬厌，因此內(nèi)存消耗會(huì)比LRU要多；當(dāng)數(shù)據(jù)量很大的時(shí)候竞帽，內(nèi)存消耗會(huì)比較可觀。
LRU-K需要基于時(shí)間進(jìn)行排序（可以需要淘汰時(shí)再排序鸿捧，也可以即時(shí)排序）屹篓，CPU消耗比LRU要高。
Two queues（2Q）
原理
Two queues（以下使用2Q代替）算法類似于LRU-2匙奴，不同點(diǎn)在于2Q將LRU-2算法中的訪問(wèn)歷史隊(duì)列（注意這不是緩存數(shù)據(jù)的）改為一個(gè)FIFO緩存隊(duì)列堆巧，
即：2Q算法有兩個(gè)緩存隊(duì)列，一個(gè)是FIFO隊(duì)列泼菌，一個(gè)是LRU隊(duì)列谍肤。
實(shí)現(xiàn)
當(dāng)數(shù)據(jù)第一次訪問(wèn)時(shí)，2Q算法將數(shù)據(jù)緩存在FIFO隊(duì)列里面哗伯，當(dāng)數(shù)據(jù)第二次被訪問(wèn)時(shí)荒揣，
則將數(shù)據(jù)從FIFO隊(duì)列移到LRU隊(duì)列里面，兩個(gè)隊(duì)列各自按照自己的方法淘汰數(shù)據(jù)焊刹。詳細(xì)實(shí)現(xiàn)如下：
- 新訪問(wèn)的數(shù)據(jù)插入到FIFO隊(duì)列系任；
- 如果數(shù)據(jù)在FIFO隊(duì)列中一直沒有被再次訪問(wèn)，則最終按照FIFO規(guī)則淘汰虐块；
- 如果數(shù)據(jù)在FIFO隊(duì)列中被再次訪問(wèn)俩滥，則將數(shù)據(jù)移到LRU隊(duì)列頭部；
- 如果數(shù)據(jù)在LRU隊(duì)列再次被訪問(wèn)贺奠，則將數(shù)據(jù)移到LRU隊(duì)列頭部霜旧；
- LRU隊(duì)列淘汰末尾的數(shù)據(jù)。
注:
上圖中FIFO隊(duì)列比LRU隊(duì)列短儡率，但并不代表這是算法要求挂据，實(shí)際應(yīng)用中兩者比例沒有硬性規(guī)定以清。
分析
【命中率】
2Q算法的命中率要高于LRU。
復(fù)雜度】
需要兩個(gè)隊(duì)列棱貌，但兩個(gè)隊(duì)列本身都比較簡(jiǎn)單玖媚。
【代價(jià)】
FIFO和LRU的代價(jià)之和。
2Q算法和LRU-2算法命中率類似婚脱，內(nèi)存消耗也比較接近今魔，但對(duì)于最后緩存的數(shù)據(jù)來(lái)說(shuō)，2Q會(huì)減少一次從原始存儲(chǔ)讀取數(shù)據(jù)或者計(jì)算數(shù)據(jù)的操作障贸。
Multi Queue（MQ）
原理
MQ算法根據(jù)訪問(wèn)頻率將數(shù)據(jù)劃分為多個(gè)隊(duì)列错森，不同的隊(duì)列具有不同的訪問(wèn)優(yōu)先級(jí)，其核心思想是：優(yōu)先緩存訪問(wèn)次數(shù)多的數(shù)據(jù)篮洁。
實(shí)現(xiàn)
MQ算法將緩存劃分為多個(gè)LRU隊(duì)列涩维，每個(gè)隊(duì)列對(duì)應(yīng)不同的訪問(wèn)優(yōu)先級(jí)。訪問(wèn)優(yōu)先級(jí)是根據(jù)訪問(wèn)次數(shù)計(jì)算出來(lái)的袁波，例如
詳細(xì)的算法結(jié)構(gòu)圖如下瓦阐，Q0，Q1....Qk代表不同的優(yōu)先級(jí)隊(duì)列篷牌，Q-history代表從緩存中淘汰數(shù)據(jù)睡蟋，但記錄了數(shù)據(jù)的索引和引用次數(shù)的隊(duì)列：
如上圖，算法詳細(xì)描述如下：
- 新插入的數(shù)據(jù)放入Q0枷颊；
- 每個(gè)隊(duì)列按照LRU管理數(shù)據(jù)戳杀；
- 當(dāng)數(shù)據(jù)的訪問(wèn)次數(shù)達(dá)到一定次數(shù)，需要提升優(yōu)先級(jí)時(shí)夭苗，將數(shù)據(jù)從當(dāng)前隊(duì)列刪除信卡，加入到高一級(jí)隊(duì)列的頭部；
- 為了防止高優(yōu)先級(jí)數(shù)據(jù)永遠(yuǎn)不被淘汰题造，當(dāng)數(shù)據(jù)在指定的時(shí)間里訪問(wèn)沒有被訪問(wèn)時(shí)傍菇，需要降低優(yōu)先級(jí)，將數(shù)據(jù)從當(dāng)前隊(duì)列刪除界赔，加入到低一級(jí)的隊(duì)列頭部桥嗤；
- 需要淘汰數(shù)據(jù)時(shí)，從最低一級(jí)隊(duì)列開始按照LRU淘汰仔蝌；每個(gè)隊(duì)列淘汰數(shù)據(jù)時(shí)泛领，將數(shù)據(jù)從緩存中刪除，將數(shù)據(jù)索引加入Q-history頭部敛惊；
- 如果數(shù)據(jù)在Q-history中被重新訪問(wèn)渊鞋，則重新計(jì)算其優(yōu)先級(jí)，移到目標(biāo)隊(duì)列的頭部；
- Q-history按照LRU淘汰數(shù)據(jù)的索引锡宋。
分析
【命中率】
MQ降低了“緩存污染”帶來(lái)的問(wèn)題儡湾，命中率比LRU要高。
【復(fù)雜度】
MQ需要維護(hù)多個(gè)隊(duì)列执俩，且需要維護(hù)每個(gè)數(shù)據(jù)的訪問(wèn)時(shí)間徐钠，復(fù)雜度比LRU高。
【代價(jià)】
MQ需要記錄每個(gè)數(shù)據(jù)的訪問(wèn)時(shí)間役首，需要定時(shí)掃描所有隊(duì)列尝丐，代價(jià)比LRU要高。
注：雖然MQ的隊(duì)列看起來(lái)數(shù)量比較多衡奥，但由于所有隊(duì)列之和受限于緩存容量的大小爹袁，因此這里多個(gè)隊(duì)列長(zhǎng)度之和和一個(gè)LRU隊(duì)列是一樣的，因此隊(duì)列掃描性能也相近矮固。
LRU類算法對(duì)比
由于不同的訪問(wèn)模型導(dǎo)致命中率變化較大失息，此處對(duì)比僅基于理論定性分析，不做定量分析档址。
對(duì)比
- 命中率 LRU-2 > MQ(2) > 2Q > LRU
- 復(fù)雜度 LRU-2 > MQ(2) > 2Q > LRU
- 代價(jià) LRU-2 > MQ(2) > 2Q > LRU
實(shí)際應(yīng)用中需要根據(jù)業(yè)務(wù)的需求和對(duì)數(shù)據(jù)的訪問(wèn)情況進(jìn)行選擇盹兢，并不是命中率越高越好。例如：雖然LRU看起來(lái)命中率會(huì)低一些守伸，且存在”緩存污染“的問(wèn)題蛤迎，但由于其簡(jiǎn)單和代價(jià)小，實(shí)際應(yīng)用中反而應(yīng)用更多含友。
實(shí)現(xiàn)
有一種叫做有序字典的數(shù)據(jù)結(jié)構(gòu)，綜合了哈希表和鏈表校辩，在 Python 中為 OrderedDict,在 Java 中為 LinkedHashMap,
在javascript中的實(shí)現(xiàn)為Map
python
from collections import OrderedDict
class LRUCache(OrderedDict):
def __init__(self, capacity):
"""
:type capacity: int
"""
self.capacity = capacity
def get(self, key):
"""
:type key: int
:rtype: int
"""
if key not in self:
return - 1
self.move_to_end(key)
return self[key]
def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: void
"""
if key in self:
self.move_to_end(key)
self[key] = value
if len(self) > self.capacity:
self.popitem(last = False)
# LRUCache 對(duì)象會(huì)以如下語(yǔ)句構(gòu)造和調(diào)用:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
復(fù)雜度分析
- 時(shí)間復(fù)雜度：對(duì)于 put 和 get 操作復(fù)雜度是 O(1)O(1)窘问，
因?yàn)橛行蜃值渲械乃胁僮鳎篻et/in/set/move_to_end/popitem（get/containsKey/put/remove）都可以在常數(shù)時(shí)間內(nèi)完成。 - 空間復(fù)雜度：O(capacity)宜咒，因?yàn)榭臻g只用于有序字典存儲(chǔ)最多 capacity + 1 個(gè)元素惠赫。
java
java中最簡(jiǎn)單的LRU算法實(shí)現(xiàn)，就是利用jdk的LinkedHashMap故黑，覆寫其中的removeEldestEntry(Map.Entry)方法即可
如果你去看LinkedHashMap的源碼可知儿咱，LRU算法是通過(guò)雙向鏈表來(lái)實(shí)現(xiàn)，當(dāng)某個(gè)位置被命中场晶，通過(guò)調(diào)整鏈表的指向?qū)⒃撐恢谜{(diào)整到頭位置混埠，
新加入的內(nèi)容直接放在鏈表頭，如此一來(lái)诗轻，最近被命中的內(nèi)容就向鏈表頭移動(dòng)钳宪，需要替換時(shí)，鏈表最后的位置就是最近最少使用的位置。
golang
使用雙向鏈表 + collection 實(shí)現(xiàn)有序字典的數(shù)據(jù)結(jié)構(gòu)
javascript
內(nèi)置有序字典Map
使用javascript ES6 Map中keys的有序性來(lái)實(shí)現(xiàn)
一個(gè)Map對(duì)象在迭代時(shí)會(huì)根據(jù)對(duì)象中元素的插入順序來(lái)進(jìn)行
- get操作
如果元素存在吏颖，先delete再set, 元素便會(huì)成置為最新使用搔体；如果不存在，返回-1
- put操作
如果元素存在半醉，先delete再set, 元素便會(huì)成置為最新使用疚俱；
如果容器超限，進(jìn)行刪除末尾元素操作缩多，使用 Map{}.keys().next()得到迭代器的第一個(gè)元素呆奕，為使用時(shí)間最遠(yuǎn)的元素，進(jìn)行刪除
/**
* @param {number} capacity
*/
var LRUCache = class {
constructor(capacity) {
this.cache = new Map();
this.capacity = capacity;
}
/**
* @param {number} key
* @return {number}
*/
get(key) {
let cache = this.cache;
let temp = cache.get(key);
if (temp) {
cache.delete(key);
cache.set(key, temp);
return temp;
} else {
return -1;
}
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
put(key, value) {
let cache = this.cache;
if (cache.has(key)) {
cache.delete(key);
} else if (cache.size >= this.capacity) {
cache.delete(cache.keys().next().value);
}
cache.set(key, value);
};
};
/**
* Your LRUCache object will be instantiated and called as such:
* var obj = new LRUCache(capacity)
* var param_1 = obj.get(key)
* obj.put(key,value)
*/
雙向鏈表 + hash表
hash表作為元素的存儲(chǔ)集合瞧壮，雙向鏈表用于元素的增刪登馒，維護(hù)最近最少使用的原則
function DLinkedNode() {
this.key = null;
this.value = null;
this.prev = null
this.next = null;
}
/**
* @param {number} capacity
*/
var LRUCache = function (capacity) {
this.cache = new Map();
this.size = 0;
this.capacity = capacity;
this.head = new DLinkedNode();
this.tail = new DLinkedNode();
//一個(gè)雙向鏈表已經(jīng)建立
this.head.next = this.tail;
this.tail.prev = this.head;
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function (key) {
let node = this.cache.get(key);
if (!node) return -1;
// move the accessed node to the head;
//使用過(guò)的放在頭部
this.moveToHead(node);
return node.value;
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function (key, value) {
let node = this.cache.get(key);
if (!node) {
let newNode = new DLinkedNode();
newNode.key = key;
newNode.value = value;
this.cache.set(key, newNode);
this.addNode(newNode);
this.size++;
if (this.size > this.capacity) {
//雙向鏈表中要?jiǎng)h除, 哈希 cache 中也要?jiǎng)h除
let tailNode = this.popTail();
this.cache.delete(tailNode.key);
//計(jì)數(shù)減一
this.size = this.size--;
}
} else {
// update the value
node.value = value;
this.moveToHead(node);
}
};
LRUCache.prototype.addNode = function (node) {
//Always add the new node right after head
//添加到隊(duì)頭
//假如 head head.next 指向 nodeB
//把 node 的 prev 和 next 指針 分別指向 head, nodeB 這兩個(gè) 節(jié)點(diǎn)
node.prev = this.head;
node.next = this.head.next;
//上面我們僅僅修改了node的指針, 并沒有修改 head 的 next 指針指向, 和 nodeB 的 prev 的指針指向
//形成雙向鏈表
this.head.next.prev = node;
this.head.next = node;
}
LRUCache.prototype.removeNode = function (node) {
/**
* Remove an existing node from the linked list.
*/
//從雙向鏈表中, 刪除 node, 先記錄下 它的前驅(qū)和后繼指向的對(duì)象
let prev = node.prev;
let next = node.next;
//把兩個(gè)節(jié)點(diǎn)聯(lián)系起來(lái)
prev.next = next;
next.prev = prev;
}
LRUCache.prototype.moveToHead = function (node) {
/**
* Move certain node in between to the head.
*/
this.removeNode(node);
this.addNode(node);
}
// 一個(gè)需要注意的是，在雙向鏈表實(shí)現(xiàn)中咆槽，這里使用一個(gè)偽頭部和偽尾部標(biāo)記界限陈轿，這樣在更新的時(shí)候就不需要檢查是否是 null 節(jié)點(diǎn);
// this.tail 是偽尾部
LRUCache.prototype.popTail = function (node) {
/**
* Pop the current tail.
*/
let res = this.tail.prev;
this.removeNode(res);
return res;
}
