目錄

一、LRU 是什么？Cache是什么？

二、LRU Cache的實現

三、源碼

---

一、LRU 是什么？Cache是什么？

LRU 是 "Least Recently Used" 的縮寫，意思是“最近最少使用”。它是一種常用的 緩存（Cache）替換算法。

緩存（Cache）就像一個臨時的“中轉站”或“快速工作臺”，它的作用是解決兩個速度差異很大的設備之間數據交換的“瓶頸”問題。

例如

• CPU 和內存之間：?我們電腦的 CPU 速度非常快，而主內存（通常用 DRAM 技術）相對較慢。為了不讓 CPU 總是“等”內存，就在它們之間加了一個高速緩存（通常用更快的 SRAM 技術）。CPU 會優先從這個高速緩存里找數據，大大提升了效率。
• 內存和硬盤之間：硬盤速度比內存慢得多，操作系統會在內存里開辟一塊區域作為硬盤的緩存，存放最近讀寫過的數據。
• 硬盤和網絡之間：?當你瀏覽網頁時，瀏覽器會把看過的圖片、網頁文件等暫時保存在硬盤上的?“Internet 臨時文件夾”或“網絡緩存”?里。下次再訪問同一個網站，瀏覽器就可以直接從本地緩存加載，而不必每次都從慢速的網絡重新下載，讓網頁打開更快。

總之，LRU 是管理緩存空間的一種策略（當緩存滿了，優先淘汰最久沒被用過的數據）。而緩存本身，則是解決不同速度設備間協作效率問題的關鍵設計，存在于計算機系統的多個層級。Cache的容量有限，因此當Cache的容量用完后，而又有新的內容需要添加進來時， 就需要挑選 并舍棄原有的部分內容，從而騰出空間來放新內容。LRU Cache 的替換原則就是將最近最少使用 的內容替換掉。其實，LRU譯成最久未使用會更形象， 因為該算法每次替換掉的就是一段時間內 最久沒有使用過的內容。

二、LRU Cache的實現

實現LRU Cache的方法和思路很多，但是要保持高效實現O(1)的put和get，且其涉及到兩個核心問題：快速訪問數據和維護數據的使用順序，那么使用雙向鏈表和 哈希表的搭配是最高效和經典的。使用雙向鏈表是因為雙向鏈表可以實現任意位置O(1)的插入和 刪除（維護數據使用順序），使用哈希表是因為哈希表的增刪查改也是O(1)和快速訪問。

算法的思想：緩存容量有限，當緩存滿了時，優先淘汰最久未被訪問的數據，保留最近使用過的數據。?

核心的數據結構：

1. 哈希表：用于?O(1) 時間?快速查詢、插入、刪除鍵值對。
2. 雙向鏈表：用于維護數據的訪問順序：
   • 最近訪問的或者新插入的放在鏈表頭部。
   • 最久未訪問的放在鏈表尾部。
   • 當緩存滿時，直接刪除鏈表尾部的數據。

?接下來借助一個 OJ 題來幫助實現 LRU Cache 算法。題目描述、示例提示如下

?

題目分析：

題目中要求函數 get 和 put 必須以 O(1) 的平均時間復雜度運行。

題目要求我們實現一個滿足 LRU (最近最少使用) 緩存 約束的數據結構。使用雙向鏈表和哈希表的搭配是最高效和經典的。

  //hash做到查找更新/插入是O(1)unordered_map<int, LtIter> _hashmap;//LRU 默認鏈表尾部的是最久未被使用的list<pair<int, int>> _LRUList;

?但是只有這些是遠遠不夠的，更新的時候其實復雜度是O(N)，更新的情況就是調用put先在哈希表里面查找到key是已存在的，那然后我們要修改，哈希表里面我找到這個就可以直接修改。 但是，在list里也要修改，因為我們替換的時候找最久未被使用的那個值就是要從list里面找。 但是要修改list的話我們知不知道當前要修改的這個元素是list里面的哪一個元素？ 是不知道的，所以還得遍歷list去找。找到之后更新一下，然后把它移到頭部去，更新順序。

所以接下來我們就需要一個設計：
還是list和unordered_map搭配。 list里面呢還是存key-value的鍵值對pair。然后哈希表里面key還是要存的，但是不再像上面寫的那樣直接存key對應的數據value，而是存這個key對應的元素在list里面的對應的迭代器。（那這樣真正的數據就只存在list里面）

那這樣的話如果更新的話，首先我們在哈希表里面找到key，然后通過它里面存的該元素在list中的迭代器，就可以直接修改list里面存放的數據。

private:typedef list<pair<int,int>>::iterator LtIter;//hash做到查找更新/插入是O(1)unordered_map<int, LtIter> _hashmap;//LRU 默認鏈表尾部的是最久未被使用的list<pair<int, int>> _LRUList;size_t _capacity;//緩存的容量控制，當緩存大小超過此值時，需要淘汰最久未使用的元素

---

構造函數：

class LRUCache {
public:LRUCache(int capacity):_capacity(capacity){}

get() 方法實現:

int get(int key) {auto ret=_hashmap.find(key);if(ret!=_hashmap.end()){LtIter it=ret->second;//獲取哈希表中存儲的鏈表迭代器//將it對應的結點轉移到鏈表頭部_LRUList.splice(_LRUList.begin(),_LRUList,it);//操作是 O(1) 時間復雜度的，因為它只修改指針而不需要復制數據return it->second->second;}return -1;
}

上面的splice接口功能如下：它可以把一個鏈表的一部分轉移到另一個鏈表（當然也可以是同一個鏈表直接進行轉移） 所以我們就可以直接調用splice將這個結點轉移到list的頭部。?

put()接口的實現：

put的話呢無非就兩種操作 如果關鍵字 key 已經存在，則變更其數據值 value ；如果不存在，則向緩存中插入該組 key-value 。 當然插入的時候需要判斷： 如果插入操作導致關鍵字數量超過 capacity ，則應該 逐出 最久未使用的關鍵字，然后插入新值。 另外不論是插入還是更新，都應該把插入或更新的值放到鏈表頭部。

void put(int key, int value) {auto ret=_hashmap.find(key);//如果找到，更新值if(ret!=_hashmap.end()){LtIter it=ret->second;it->second=value;//將it對應的結點轉移到鏈表頭部_LRUList.splice(_LRUList.begin(),_LRUList,it);}else//找不到，插入{//如果滿了需要先刪除最久未使用的值if(_capacity==_hashmap.size()){pair<int,int> back=_LRUList.back();_hashmap.erase(back.first);_LRUList.pop_back();}//插入_LRUList.push_front(make_pair(key,value));_hashmap[key]=_LRUList.begin();}
}

三、源碼

class LRUCache {
public:LRUCache(int capacity):_capacity(capacity){}int get(int key) {auto ret=_hashmap.find(key);if(ret!=_hashmap.end()){LtIter it=ret->second;//將it對應的結點轉移到鏈表頭部_LRUList.splice(_LRUList.begin(),_LRUList,it);return it->second;}return -1;}void put(int key, int value) {auto ret=_hashmap.find(key);//如果找到，更新值if(ret!=_hashmap.end()){LtIter it=ret->second;it->second=value;//將it對應的結點轉移到鏈表頭部_LRUList.splice(_LRUList.begin(),_LRUList,it);}else//找不到，插入{//如果滿了需要先刪除最久未使用的值if(_capacity==_hashmap.size()){pair<int,int> back=_LRUList.back();_hashmap.erase(back.first);_LRUList.pop_back();}//插入_LRUList.push_front(make_pair(key,value));_hashmap[key]=_LRUList.begin();}}
private:typedef list<pair<int,int>>::iterator LtIter;//hash做到查找更新/插入是O(1)unordered_map<int, LtIter> _hashmap;//LRU 默認鏈表尾部的是最久未被使用的list<pair<int, int>> _LRUList;size_t _capacity;
};

---

感謝閱讀！?