手撕LFU

博主介紹：程序喵大人

35- 資深C/C++/Rust/Android/iOS客戶端開發
10年大廠工作經驗
嵌入式/人工智能/自動駕駛/音視頻/游戲開發入門級選手
《C++20高級編程》《C++23高級編程》等多本書籍著譯者
更多原創精品文章，首發gzh，見文末
👇👇記得訂閱專欄，以防走丟👇👇
😉C++基礎系列專欄
😃C語言基礎系列專欄
🤣C++大佬養成攻略專欄
🤓C++訓練營
👉🏻個人網站

最近是校招實習面試高峰期，訓練營中很多同學都在面試中，有些同學甚至被大廠要求手撕LFU，覺得很離譜。

但其實手撕LFU在面試中已經不少見了，手撕LFU、手撕LRU，在現在的面試中都很常見，大家一定要掌握，平時可以多練幾遍。

對應的力扣鏈接如下：

https://leetcode.cn/problems/lfu-cache/
https://leetcode.cn/problems/lru-cache/

相關LRU題解如下：

下面通過一個例子，來給大家說一下 LRU 的概念。

假設你是一位圖書管理員，你需要管理一個熱門書籍借閱專區，空間有限，只能存放一定數量的書籍。讀者借閱書籍后需歸還，當專區滿了，又有新的熱門書籍要上架時，你會怎么做呢？

你大概會去查看借閱記錄，看哪些書籍被頻繁借閱，頻繁被借閱（相當于被訪問）的書籍會繼續留在專區，而那些很久都沒有讀者借閱（長時間未被訪問）的書籍，會將其從專區移除，放到普通書架，把空間讓給新的熱門書籍。

上面這個例子，就是我們常說的 LRU 緩存淘汰算法。

既然知道了 LRU 原理，下面我們來看一下題目要求

那我們來拆解一下，需要做哪些工作

設計一個數據結構，用來存儲元素
維護數據結構里面的元素序列，能夠做到需要騰出空間時，可以快速逐出最久未使用的關鍵字
能夠快速的通過 key 獲取 value，也就是做到隨機訪問

需求已經很明確了，那我們此時應該選擇什么數據結構呢？因為需要快速獲取 value，并且要 put key 和 value，那么數據結構肯定要有 HashMap。

在 LRU 算法里，我們要維護元素的訪問順序，每次訪問一個節點，無論是新節點還是已有節點，都要把它移到有序序列的頭部，以此表示它是最新被訪問的。

這個有序序列會始終保持從頭部到尾部，節點未被訪問的時間依次遞增。也就是說，序列頭部的節點是剛剛被訪問過的，而尾部的節點則是最久未被訪問的，在需要淘汰元素時，就優先淘汰尾部節點。

以上所述，我們可以使用 **哈希表+鏈表 **來完成我們的需求。

那應該使用單向鏈表，還是雙向鏈表呢？

移動節點到鏈表頭部或刪除鏈表尾部節點，都需先刪除目標節點。

尋找后繼節點時，單雙向鏈表均可通過next指針在 O (1) 時間完成；但尋找前驅節點，單向鏈表需從頭遍歷，耗時 O (n)，雙向鏈表則能借前向指針在 O (1) 時間找到。因此，為保證操作均在 O (1) 時間內完成，故應選擇雙向鏈表，本質是以空間換時間。

好了，我們來看一下，具體是如何存儲元素的呢？

從上圖可知，我們的 key 為 int，value 為雙向鏈表的節點

好啦，現在我們已經清晰知道了，應該如何設計數據結構，我們進一步根據題目，來了解需求

LRUCache(int capacity) 以 正整數 作為容量 capacity 初始化 LRU 緩存

解析: HashMap 需要有 size，并初始化 map 的 key 為 int，value 為雙向鏈表的節點

int get(int key) 如果關鍵字 key 存在于緩存中，則返回關鍵字的值，否則返回 -1

解析: 如果不存在返回 -1，如果存在，則將該 value 返回，并且將該節點，移到雙向鏈表的頭部，移到鏈表頭部的操作我們可以分兩步進行

第一步：將節點從當前位置刪除

第二步：在鏈表頭部 add 該節點

具體操作如下

這樣就實現了，將某節點，移動到頭部的操作

void put(int key, int value) 如果關鍵字 key 已經存在，則變更其數據值 value 并將其移動到鏈表頭部；如果不存在，則向緩存中插入該組 key-value 同時在鏈表頭部插入該節點。如果插入操作導致關鍵字數量會超過 capacity ，則應該逐出最久未使用的關鍵字后再插入

解析：這里有兩點需要注意，第一點，put 時，假設該節點存在，則需要將其放到頭節點。第二點如果超出緩存容量，則需要先刪除節點，再在頭部插入新節點。

整體思路已經了解，我們來看代碼吧

注：代碼中也有詳細的解析，請認真閱讀代碼

class LRUCache {
private:
// 鏈表的節點結構體，因為是雙向鏈表，需要有 perv,next,value,key,
// 這里有人問了，為什么還需要添加 key 呢？
// 因為刪去最近最少使用的鍵值對時，要刪除鏈表的尾節點
// 如果節點中沒有存儲 key，那么就無法知道，被刪除的是那個節點，也無法刪除 map 中對應的 key-value
// 此時，我們是先確定要刪除的鏈表節點，再去 map 中刪除對應的 key-value
struct DouLink {
int key;
int value;
DouLink* prev;
DouLink* next;
DouLink() : key(0), value(0), prev(nullptr), next(nullptr) {}
DouLink(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};DouLink* head; // 虛擬頭節點
DouLink* tail; // 虛擬尾節點，幫助我們來完成頭插法和尾部刪除節點
int capacity; // map 的容量
int size; // 當前節點數目
// 我們不要求有序，所以使用 unordered_map 即可，提升性能
std::unordered_map<int, DouLink*> map; 
public:
// 構造函數初始化，只有虛擬頭尾節點的雙向鏈表，并配置，緩存容量
LRUCache(int capacity) : capacity(capacity), size(0) {head = new DouLink();tail = new DouLink();head->next = tail;tail->prev = head;
}// 釋放
~LRUCache() {DouLink* current = head;while (current != nullptr) {DouLink* nextNode = current->next;delete current;current = nextNode;}
}// 獲取節點內容
int get(int key) {auto it = map.find(key);// 未發現返回 -1，符合題目要求if (it == map.end()) {return -1;}// 訪問節點DouLink* temp = it->second;// 將最新被訪問的節點，移到鏈表頭部moveHead(temp);// 返回值return temp->value;
}
// put 有兩種情況，原先是否存該值
void put(int key, int value) {auto it = map.find(key);// 不存在if (it == map.end()) {// 增加新元素前，判斷是否需要清理空間（鏈表尾部節點，長時間未被訪問節點）if (size == capacity) {DouLink* newNode = removeTail();map.erase(newNode->key);delete newNode;--size;}// 初始化節點，并執行插入到鏈表頭部DouLink* test = new DouLink(key, value); addHead(test);// map 也執行對應的插入 key-valuemap[key] = test;++size; // 記錄當前存儲元素數目} else {// 存在該節點，修改節點內容DouLink* temp = it->second;temp->value = value;moveHead(temp);}
}// 封裝的操作鏈表函數，添加到鏈表頭部
void addHead(DouLink* node) {node->next = head->next;head->next->prev = node;head->next = node;node->prev = head;
}
// 封裝的操作鏈表函數，移動到鏈表頭部
void moveHead(DouLink* node) {remove(node); // 刪除節點addHead(node); // 將節點添加到頭部
}// 刪除某節點
void remove(DouLink* node) {node->prev->next = node->next;node->next->prev = node->prev;
}// 刪除鏈表尾部節點，長時間未被訪問節點
DouLink* removeTail() {DouLink* temp = tail->prev;remove(temp);return temp;
}
};