之前寫過一篇關于LRU緩存淘汰策略的博客，那時候還在俄羅斯。在面試深信服的時候面試官有問到，面試官特別的nice，雖然好多問題沒有答上來，但是從面試官那里學到不少的東西。今天再總結下LRU

首先是寫LRU緩存淘汰策略的邏輯。

LRU緩存淘汰策略分為訪問和新建兩個方面

訪問：如果最近有訪問直接把它提到最前面。

新建：新建的時候應該考慮到兩個方面

（1）程序是新打開的之前沒有打開過這個時候需要判斷存放緩存的容器是否已滿，如果滿了的話就需要把最后一個緩存刪掉。

。如果沒有滿的話直接插入就可以

（2）程序之前打開過，再次打開，這個時候只需要把這個程序的緩存調到最前面即可。

LRU緩存淘汰策略實現的數據結構是哈希表加雙向鏈表。

原因：

哈希表的查找速度比較快，雙向鏈表的插入和刪除速度比較快。把兩者結合起來使用，時間復雜度位o（1）

具體代碼如下

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) 換到隊頭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 是否已經存在 */ auto it = map.find(key);if (it == map.end()) {/* key 不存在，判斷 cache 是否已滿 */ if (cache.size() == cap) {// cache 已滿，刪除尾部的鍵值對騰位置// cache 和 map 中的數據都要刪除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 并換到隊頭 */cache.erase(map[key]);cache.push_front(make_pair(key, value));map[key] = cache.begin();}} };

?

總結

以上是生活随笔為你收集整理的LRU缓存淘汰策略的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。