LRU 緩存淘汰算法就是一種常用策略搓扯。LRU 的全稱是 Least Recently Used纵刘，也就是說我們認(rèn)為最近使用過的數(shù)據(jù)應(yīng)該是是「有用的」腻豌，很久都沒用過的數(shù)據(jù)應(yīng)該是無用的引谜，內(nèi)存滿了就優(yōu)先刪那些很久沒用過的數(shù)據(jù)厦画。
因?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)：哈希鏈表。
LRU 緩存算法的核心數(shù)據(jù)結(jié)構(gòu)就是哈希鏈表夯到，雙向鏈表和哈希表的結(jié)合體嚷缭。這個(gè)數(shù)據(jù)結(jié)構(gòu)長(zhǎng)這樣：
雙向鏈表+哈希表=哈希鏈表.png
就是借助哈希表賦予了鏈表快速查找的特性嘛：可以快速查找某個(gè) key 是否存在緩存（鏈表）中，同時(shí)可以快速刪除耍贾、添加節(jié)點(diǎn)阅爽。
#include<iostream>
using namespace std;
#include <unordered_map>
#include <list>
class LRUCache {
private:
int cap;
// 雙鏈表：裝著 (key, value) 元組
list<pair<int, int>> cache;
// 哈希表：key 映射到 (key, value) 在 cache 中的位置
unordered_map<int, list<pair<int, int>>::iterator> map;
public:
LRUCache(int capacity) {
this->cap = capacity;
}
int get(int key) {
auto it = map.find(key);
// 訪問的 key 不存在
if (it == map.end()) return -1;
// key 存在，把 (k, v) 換到隊(duì)頭
pair<int, int> kv = *map[key];
cache.erase(map[key]);
cache.push_front(kv);
// 更新 (key, value) 在 cache 中的位置
map[key] = cache.begin();
return kv.second; // value
}
void put(int key, int value) {
/* 要先判斷 key 是否已經(jīng)存在 */
auto it = map.find(key);
if (it == map.end()) {
/* key 不存在荐开，判斷 cache 是否已滿 */
if (cache.size() == cap) {
// cache 已滿付翁，刪除尾部的鍵值對(duì)騰位置
// cache 和 map 中的數(shù)據(jù)都要?jiǎng)h除
auto lastPair = cache.back();
int lastKey = lastPair.first;
map.erase(lastKey);
cache.pop_back();
}
// cache 沒滿，可以直接添加
cache.push_front(make_pair(key, value));
map[key] = cache.begin();
}
else {
/* key 存在晃听，更改 value 并換到隊(duì)頭 */
cache.erase(map[key]);
cache.push_front(make_pair(key, value));
map[key] = cache.begin();
}
}
void print_it() {
list<pair<int, int>>::iterator p = cache.begin();
for (; p != cache.end(); p++) {
cout << p->first << "->";
}
cout << endl;
}
};
int main() {
LRUCache cache = LRUCache(3);
cache.put(1, 10);
cout <<cache.get(2)<<endl;
cache.put(2, 20);
cout << cache.get(2) << endl;
cache.put(3, 30);
cout<<cache.get(3) << endl;
cache.print_it();
cout << cache.get(2) << endl;
cache.print_it();
system("pause");
return 0;
}
代碼運(yùn)行結(jié)果
