LRU緩存機制

目錄

LRU（Least Recently Used）最近少用

what

why

where

how

int get(int key)

void put(int key,int value)

資料結構的選用

具體實作（附詳細注釋）

LRU（Least Recently Used）最近少用

• what

它是一種緩存淘汰機制，顧名思義，将最近使用次數最少的緩存淘汰

• why

根據程式的局部性原理，最近經常使用的緩存留在記憶體中，而将最近不常用的緩存換出記憶體，是比較接近理想的一種緩存置換算法

• where

在凡是帶有緩存的場景中，LRU都可以作為最基本的緩存置換政策，例如：作業系統記憶體的頁面置換、Redis緩存淘汰機制等等

• how

如何設計一個簡單的LRU緩存算法？

舉個栗子，記憶體容量大小為2，按照key-value形式存儲，結構的頭部為最近最常使用的結點，尾部為最近最少使用的結點

LRU有兩個操作：get和put，每次get和put操作都将查詢的值變為最近最常使用的結點，當put容量已滿時，删除最近最少使用的結點

int get(int key)

1. 輸入一個key值
2. 如果key值不存在，則傳回-1
3. 如果key值存在，則将key-value鍵值對放到結構頭部

void put(int key,int value)

1. 首先檢視是否存在相同key值的結點
2. 如果存在，把它删除；
3. 如果不存在，先檢視容量是否已滿
4. 如果容量已經滿了，從尾部删除最近最少使用的結點，為新插入結點騰出位置
5. 如果容量未滿，在最前面放入一個key-value的鍵值對

資料結構的選用

對于get操作的第2.3步

需要通過key值查找是否存在，則應該使得查找的時間複雜度為O(1)，鍊式結構肯定不可以，因為需要周遊查找，考慮使用數組、hash

如果查找到key值對應的結點存在，需要将key-value鍵值對放到結構頭部，則應該使得頭部插入的時間複雜度為O(1)，考慮使用連結清單

對于put操作的第1步

同get操作

對于put操作的第2步

則應該使得在任意位置删除的時間複雜度為O(1)，數組結構肯定不可以，因為删除後需要向前移動補齊，考慮使用鍊式結構

對于put操作的第4步

則需要在尾部删除的時間複雜度為O(1)，數組連結清單皆可

對于put操作的第5步

同get操作

綜合考慮，因為需要在任意位置删除的時間複雜度為O(1)，數組結構肯定是不能選用的，那麼如果使用鍊式結構，該如何在O(1)時間找到這個要删除的位置呢？

思路是這樣的，

我們需要以時間複雜度O(1）得知Cache中key值對應的結點是否存在，可以使用一個hash映射

我們需要在頭插尾删時間複雜度為O(1)，那麼使用雙向連結清單是最好的選擇，想要在雙向連結清單中以時間複雜度O(1)删除某個結點，則首先要找到這個結點對應的疊代器

那麼這個hash映射，key值就是結點的key值，而value值，我們存放key值對應結點的疊代器，通過疊代器調用erase就可以實作以O(1)時間複雜度删除指定位置結點

它的結構圖是下面醬嬸兒的

使用這種方式我們可以實作以下操作的時間複雜度都是O(1)：

在Cache的頭插入、任意位置删除

查找key值對應的結點是否在Cache中

具體實作（附詳細注釋）

class LRUCache {
public:
    list<pair<int,int>> cache;
    unordered_map<int,list<pair<int,int>>::iterator> hash;
    int cap;
    LRUCache(int capacity) :cap(capacity){
    }
    int get(int key) {
        //先看映射中有沒有 沒有 傳回-1
        if(hash.find(key) == hash.end())
            return -1;
        //如果有，取得結點
        pair<int,int> node = *hash[key];
        //通過結點的疊代器，删除
        cache.erase(hash[key]);
        //将結點重新插入到頭部，變為最近最常使用
        cache.push_front(node);
        //更新hash中疊代器的位置
        hash[key] = cache.begin();
        //傳回value值
        return node.second;
    }
    void put(int key, int value) {
        //先看映射中有沒有
        if(hash.find(key) != hash.end()){
            //有 通過疊代器删除
            cache.erase(hash[key]);
        }else{
            //沒有 判斷這次插入是否越界
            if(cap == cache.size()){
                //越界了 
                //注意順序：通過Cache取得key值，删除hash中的該結點
                //在Cache尾巴删除最近最少使用的結點
                hash.erase(cache.back().first);
                cache.pop_back();
            }
        }
        //頭插入
        cache.push_front(make_pair(key,value));
        //更新map的疊代器
        hash[key] = cache.begin();
            
    }
};