1. 什么是LRU Cache

LRU是Least Recently Used的縮寫，意思是最近最少使用，它是一種Cache替換算法。
什么是Cache？
狹義的Cache指的是位于CPU和主存間的快速RAM， 通常它不像系統(tǒng)主存那樣使用DRAM技術(shù)，而使用昂貴但較快速的SRAM技術(shù)。 廣義上的Cache指的是位于速度相差較大的兩種硬件之間， 用于協(xié)調(diào)兩者數(shù)據(jù)傳輸速度差異的結(jié)構(gòu)。除了CPU與主存之間有Cache， 內(nèi)存與硬盤之間也有Cache，乃至在硬盤與網(wǎng)絡(luò)之間也有某種意義上的Cache── 稱為Internet臨時(shí)文件夾或網(wǎng)絡(luò)內(nèi)容緩存等。

而Cache的容量有限，那如果cache滿了怎么辦？
當(dāng)Cache的容量用完后，而又有新的內(nèi)容需要添加進(jìn)來時(shí)， 就需要挑選并舍棄原有的部分內(nèi)容，從而騰出空間來放新內(nèi)容。
那應(yīng)該選取那一部分的內(nèi)容和新內(nèi)容進(jìn)行替換呢？這就涉及到cache的替換算法，而LRU Cache就是cache替換算法中的一種！
LRU Cache 的替換原則就是將最近最少使用的內(nèi)容替換掉。其實(shí)，LRU譯成最久未使用會(huì)更形象， 因?yàn)樵撍惴看翁鎿Q掉的就是一段時(shí)間內(nèi)最久沒有使用過的內(nèi)容。

2. LRU Cache的實(shí)現(xiàn)

那要實(shí)現(xiàn)一個(gè)LRU Cache其實(shí)并不難，方法和思路有很多；但是想要實(shí)現(xiàn)一個(gè)高效（所有操作都是O(1) ）的LRU Cache是有難度的

實(shí)現(xiàn)LRU Cache的方法和思路很多，但是要保持高效實(shí)現(xiàn)O(1)的put和get，那么使用雙向鏈表和哈希表的搭配是最高效和經(jīng)典的。
使用雙向鏈表是因?yàn)殡p向鏈表可以實(shí)現(xiàn)任意位置O(1)的插入和刪除，使用哈希表是因?yàn)楣１淼脑鰟h查改也是O(1)。

那具體到底應(yīng)該應(yīng)該怎么做呢？

下面我們借助LeetCode上的一道OJ來給大家進(jìn)行一個(gè)詳細(xì)的講解。

3. LRU Cache的OJ

題目鏈接: link

我們來看一下題目：


大家可以自己先看一下題目，我們看到題目中要求函數(shù) get 和 put 必須以 O(1) 的平均時(shí)間復(fù)雜度運(yùn)行。

那我們來分析一下要如何實(shí)現(xiàn)

題目分析

題目要求我們實(shí)現(xiàn)一個(gè)滿足 LRU (最近最少使用) 緩存 約束的數(shù)據(jù)結(jié)構(gòu)。
這個(gè) LRUCache 類的要求是這樣的：

那我們要如何實(shí)現(xiàn)呢？

其實(shí)分析完題目我們很容易能想到用哈希表，那當(dāng)然C++里面我們就用unordered_map去搞，那這樣的話get函數(shù)（其實(shí)就是查找嘛）就能達(dá)到O(1)；然后put呢，put也是要查找嘛，找到就更新，找不到就插入。那這樣就也是O(1)。
但是呢我們真正還要考慮還有——如果插入操作導(dǎo)致關(guān)鍵字?jǐn)?shù)量超過 capacity ，我們此時(shí)就要進(jìn)行LRU替換，則應(yīng)該 逐出 最久未使用的關(guān)鍵字。
那我們要如何實(shí)現(xiàn)LRU的替換呢？滿的話應(yīng)該逐出誰啊？如何找到最久未被使用的那個(gè)呢？

🆗，那上面也提到了，使用雙向鏈表和哈希表的搭配是最高效和經(jīng)典的：

我們?cè)俑阋粋€(gè)list（list底層就是帶頭雙向循環(huán)鏈表），讓它里面也存儲(chǔ)數(shù)據(jù)（相當(dāng)于數(shù)據(jù)存儲(chǔ)兩份），然后我們可以默認(rèn)認(rèn)為尾部的那個(gè)元素就是最近最少用（最久未被使用）的（按頭部實(shí)現(xiàn)也可）。
然后如果有新插入的元素或者被訪問（get一個(gè)已有的值）的元素我就把它移到鏈表頭部。
這樣我們需要替換的時(shí)候，那么鏈表尾部的那個(gè)就是最久未被使用的那個(gè)。

但是呢？

如果我們就這樣設(shè)計(jì)的話，還存在一個(gè)問題。
就是更新的時(shí)候其實(shí)復(fù)雜度是O(N)。
為什么呢？
更新的情況就是調(diào)用put先在哈希表里面查找到key是已存在的，那然后我們要修改，哈希表里面我找到這個(gè)就可以直接修改。
但是，在list里面我們是不是也要修改啊，因?yàn)槲覀兲鎿Q的時(shí)候找最久未被使用的那個(gè)值就是要從list里面找呢。
但是要修改list的話我們知不知道當(dāng)前要修改的這個(gè)元素是list里面的哪一個(gè)元素？
是不知道的，所以還得遍歷list去找。找到之后更新一下，然后把它移到頭部去，更新順序。
那這里遍歷查找的話不就是O(N)了嘛。

那這個(gè)問題我們?nèi)绾谓鉀Q一下呢？

如何做到在哈希表里面找到這個(gè)key之后，就直接能獲取到他在list中的位置，而不需要去遍歷查找呢？

那這里有一個(gè)非常巧的設(shè)計(jì)是這樣來解決的：

還是list和unordered_map搭配。
list里面呢還是存key-value的鍵值對(duì)pair。然后哈希表里面key還是要存的，但是不再像上面寫的那樣直接存key對(duì)應(yīng)的數(shù)據(jù)value，而是存這個(gè)key對(duì)應(yīng)的元素在list里面的對(duì)應(yīng)的迭代器。（那這樣真正的數(shù)據(jù)就只存在list里面）

那這樣的話如果更新的話，首先我們?cè)诠１砝锩嬲业絢ey，然后通過它里面存的該元素在list中的迭代器，就可以直接修改list里面存放的數(shù)據(jù)。
然后再把它放到鏈表頭部（兩種方法，后面會(huì)提到）。
當(dāng)然list<pair<int,int>>::iterator這個(gè)類型比較長，我們也可以typedef一下

那下面我們來嘗試寫一下代碼：

AC代碼

那首先我們應(yīng)該還要再增加一個(gè)成員變量：

即cache的容量capactity，因?yàn)橛袝r(shí)候我們還需要判斷cache滿不滿。

然后我們來逐一實(shí)現(xiàn)一下它的3個(gè)成員函數(shù)：

首先是它的構(gòu)造函數(shù)LRUCache：

那這個(gè)很簡單，就是初始化一下capacity就行了。
剩下兩個(gè)成員變量是自定義類型，有默認(rèn)構(gòu)造。

那然后是get函數(shù)：

get呢也很簡單，就是通過key判斷在不在嘛。
如果在的話，就返回key對(duì)應(yīng)的值；如果不在，返回-1。
那我們就可以直接調(diào)用unordered_map的find函數(shù)，根據(jù)find的返回結(jié)果判斷，如果找到了，我們要返回什么呢？

🆗，首先這里的ret是啥啊，這里find返回的是迭代器，找到的話返回的就是key對(duì)應(yīng)的這個(gè)元素的迭代器。
那我們要返回這個(gè)key對(duì)應(yīng)的那個(gè)有效的值，那真正的數(shù)據(jù)是存在list里面的。
我們通過誰可以找到list里面存儲(chǔ)的這個(gè)key對(duì)應(yīng)的元素呢？
🆗，現(xiàn)在unordered_map里面的value存的是list里面這個(gè)key對(duì)應(yīng)元素的迭代器（有點(diǎn)繞了這里😂）。

所以ret->second就是list里面這個(gè)元素的迭代器，但是我們想要拿到的是這個(gè)元素的key對(duì)應(yīng)的值，即ret->second->second，這里要取兩次second。

🆗，那這樣就完了嘛？

還沒有。
如果get的時(shí)候成功找到了這個(gè)數(shù)據(jù)，那相當(dāng)于訪問了它，那cache里面存儲(chǔ)數(shù)據(jù)的順序是不是就要調(diào)整了。是不是要把這個(gè)剛被訪問的元素放到鏈表頭部啊。

那如何在list里面調(diào)整這個(gè)順序呢？我們上面提到有兩種方式：

首先第一種方法我們可以先把這個(gè)元素刪除掉，然后在頭插到頭部。
但是這樣的話記得還要更新一下unordered_map里面存的對(duì)應(yīng)的那個(gè)迭代器，因?yàn)閯h完之后這個(gè)迭代器就失效了。之前的文章我們模擬實(shí)現(xiàn)過list，我們知道list的迭代器其實(shí)就是對(duì)結(jié)點(diǎn)指針的封裝嘛，這個(gè)結(jié)點(diǎn)刪除的話它這個(gè)結(jié)點(diǎn)指針指向的空間就釋放了。
所以這種方法好像有點(diǎn)麻煩。
那我就可以考慮用另外一種——直接調(diào)用list的splice 接口轉(zhuǎn)移結(jié)點(diǎn)。
那splice 這個(gè)函數(shù)其實(shí)我們之前也有提到過

它可以把一個(gè)鏈表的一部分轉(zhuǎn)移到另一個(gè)鏈表（當(dāng)然也可以是同一個(gè)鏈表直接進(jìn)行轉(zhuǎn)移）
所以我們就可以直接調(diào)用splice將這個(gè)結(jié)點(diǎn)轉(zhuǎn)移到list的頭部。

那最后就剩下put：

那put的話呢?zé)o非就兩種操作
如果關(guān)鍵字 key 已經(jīng)存在，則變更其數(shù)據(jù)值 value ；如果不存在，則向緩存中插入該組 key-value 。
當(dāng)然插入的時(shí)候需要判斷：
如果插入操作導(dǎo)致關(guān)鍵字?jǐn)?shù)量超過 capacity ，則應(yīng)該 逐出 最久未使用的關(guān)鍵字，然后插入新值。
另外不論是插入還是更新，都應(yīng)該把插入或更新的值放到鏈表頭部。

那我們來寫一下代碼：

🆗，那到這里就完事了。

我們來提交一下：

沒有問題！

完整代碼：

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對(duì)應(yīng)的結(jié)點(diǎn)轉(zhuǎn)移到鏈表頭部_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對(duì)應(yīng)的結(jié)點(diǎn)轉(zhuǎn)移到鏈表頭部_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 默認(rèn)鏈表尾部的是最久未被使用的list<pair<int, int>> _LRUList;size_t _capacity;
};

那我們這篇文章就到這里…