知識點：

LRU是Least Recently Used的縮寫，意思是最近最少使用，它是一種Cache替換算法
Cache的容量有限，因此當Cache的容量用完后，而又有新的內容需要添加進來時， 就需要挑選
并舍棄原有的部分內容，從而騰出空間來放新內容。LRU Cache 的替換原則就是將最近最少使用
的內容替換掉。其實，LRU譯成最久未使用會更形象， 因為該算法每次替換掉的就是一段時間內
最久沒有使用過的內容
?

LRU本質就是一個頁面置換算法，關鍵就是如何實現get()和put()函數O（1）時間復雜度

具體內容請打開leedcode上面這題：

146. LRU 緩存 - 力扣（LeetCode）

如何實現O(1)，關鍵在于鏈表和哈希的使用，我來結合代碼講解：

//首先，定義一個capacity、list和unordered_map成員變量，注意的是_hashmp存放的第二個參數為list迭代器,list存放的是pair類型，first為key，second為value
//其次：實現put函數，如果存在，我們只需要更新器內容，并放在鏈表的頭部（注：尾部是不使用的），但當我們put的是不存在的，需要判斷容量是否滿足，是否需要刪除list尾部，然后再插入到鏈表的頭部，更新——_hashmp注意放的是iterator
//最后，實現get函數，不存在返回-1，否則，找到該value，然后將其提前保存放入list頭部，再將其原位置刪除，同時更新hash中迭代器位置
class LRUCache {
public:LRUCache(int capacity) {_capacity = capacity;}//O(1):int get(int key) {//通過key得到value，否則返回-1//去哈希中查找auto hashit = _hashmap.find(key);if(hashit == _hashmap.end()){//未找到return -1;}else{//找到auto listit = hashit->second;//更新該節點的使用情況pair<int,int> kv = *listit;_list.erase(listit);_list.push_front(kv);//更新哈希_hashmap[key] = _list.begin();return kv.second;}}//O(1):void put(int key, int value) {//存在更新，不存在插入//判斷是否存在auto hashit = _hashmap.find(key);//注意：hashit是迭代器if(hashit == _hashmap.end()){//不存在，插入，注意capacityif(_list.size() == _capacity){//刪除最近未使用的_hashmap.erase(_list.back().first);_list.pop_back();}//插入到鏈表頭部+更新哈希_list.push_front(make_pair(key,value));_hashmap[key] = _list.begin();}else{//存在，更新數據并且放在鏈表頭部，我們尾部是最近未使用數據//獲取list中迭代器位置auto listit = hashit->second;//更新KVpair<int,int> kv = *listit;kv.second = value;//將鏈表中該節點位置放入頭部_list.erase(listit);_list.push_front(kv);//更新哈希_hashmap[key] = _list.begin();}}
private:int _capacity;//容量list<pair<int,int>> _list;unordered_map<int,list<pair<int,int>>::iterator> _hashmap;
};

LRU面試不算經常考察的內容，但是也需要我們會實現到O(1)的復雜度

補充：

現在還存在面試常考的另一種算法LFU算法

該算法是通過一個count記錄來處理最少使用的情況，下面聯系leedcode例題來講解：

460. LFU 緩存 - 力扣（LeetCode）

實現過程：

class LFUCache {
public:LFUCache(int capacity) {_capacity = capacity;}int get(int key) {auto hashit = _hashmp.find(key);if (hashit == _hashmp.end()) return -1;// 獲取當前節點并更新頻率auto listit = hashit->second;auto kcv = *listit;_list.erase(listit);  // 先移除舊節點// 更新頻率并重新插入到正確位置kcv.second.first++;auto new_it = insertIntoSortedList(kcv);_hashmp[key] = new_it;return kcv.second.second;}void put(int key, int value) {auto hashit = _hashmp.find(key);if (hashit == _hashmp.end()) {// 緩存已滿，淘汰頻率最低且最久未使用的節點if (_list.size() >= _capacity) {_hashmp.erase(_list.back().first);_list.pop_back();}// 插入新節點（頻率=1）auto kcv = make_pair(key, make_pair(1, value));auto new_it = insertIntoSortedList(kcv);_hashmp[key] = new_it;} else {// 更新現有節點（邏輯同get）auto listit = hashit->second;auto kcv = *listit;_list.erase(listit);kcv.second.first++;kcv.second.second = value;  // 更新valueauto new_it = insertIntoSortedList(kcv);_hashmp[key] = new_it;}}private:// 輔助函數：將節點按頻率和訪問順序插入到鏈表list<pair<int, pair<int, int>>>::iterator insertIntoSortedList(const pair<int, pair<int, int>>& kcv) {// 遍歷鏈表，找到第一個頻率 <= 當前節點頻率的位置for (auto it = _list.begin(); it != _list.end(); ++it) {if (it->second.first <= kcv.second.first) {return _list.insert(it, kcv);  // 插入到該位置前}}// 如果所有節點頻率都更低，插入到末尾return _list.insert(_list.end(), kcv);}int _capacity;list<pair<int, pair<int, int>>> _list;  // (key, (count, value))unordered_map<int, list<pair<int, pair<int, int>>>::iterator> _hashmp;
};

通過list和unordered_map來實現，但是需要兩個pair（重點），另外就是就是insert和erase操作使用，希望對大家有幫助！！！