LeetCode中LRU 緩存機制的示例分析

題目描述

運用你所掌握的數(shù)據(jù)結(jié)構(gòu)，設計和實現(xiàn)一個  LRU (最近最少使用) 緩存機制。它應該支持以下操作： 獲取數(shù)據(jù) get 和 寫入數(shù)據(jù) put 。

獲取數(shù)據(jù) get(key) - 如果密鑰 (key) 存在于緩存中，則獲取密鑰的值（總是正數(shù)），否則返回 -1。
寫入數(shù)據(jù) put(key, value) - 如果密鑰不存在，則寫入其數(shù)據(jù)值。當緩存容量達到上限時，它應該在寫入新數(shù)據(jù)之前刪除最近最少使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。

進階:

你是否可以在 O(1) 時間復雜度內(nèi)完成這兩種操作？

示例:

LRUCache cache = new LRUCache( 2 /* 緩存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 該操作會使得密鑰 2 作廢
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 該操作會使得密鑰 1 作廢
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

思路解析

這道題是讓我們實現(xiàn)一個 LRU 緩存器，LRU是 Least Recently Used 的簡寫，就是最近最少使用的意思。

這個緩存器主要有兩個成員函數(shù)，get 和 put。

其中 get 函數(shù)是通過輸入 key 來獲得 value，如果成功獲得后，這對 (key, value) 升至緩存器中最常用的位置（頂部），如果 key 不存在，則返回 -1 。

而 put 函數(shù)是插入一對新的 (key, value)，如果原緩存器中有該 key，則需要先刪除掉原有的，將新的插入到緩存器的頂部。如果不存在，則直接插入到頂部。

若加入新的值后緩存器超過了容量，則需要刪掉一個最不常用的值，也就是底部的值。

具體實現(xiàn)時我們需要三個私有變量，cap , l 和 m，其中 cap 是緩存器的容量大小，l 是保存緩存器內(nèi)容的列表，m 是 HashMap，保存關(guān)鍵值 key 和緩存器各項的迭代器之間映射，方便我們以 O(1) 的時間內(nèi)找到目標項。

然后我們再來看 get 和 put 如何實現(xiàn)。

其中，get 相對簡單些，我們在 m 中查找給定的key，若不存在直接返回 -1；如果存在則將此項移到頂部。

對于 put ，我們也是現(xiàn)在 m 中查找給定的 key，如果存在就刪掉原有項，并在頂部插入新來項，然后判斷是否溢出，若溢出則刪掉底部項(最不常用項)。  

參考代碼

class LRUCache{
public:
    LRUCache(int capacity) {
        cap = capacity;
    }

    int get(int key) {
        auto it = m.find(key);
        if (it == m.end()) return -1;
        l.splice(l.begin(), l, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = m.find(key);
        if (it != m.end()) l.erase(it->second);
        l.push_front(make_pair(key, value));
        m[key] = l.begin();
        if (m.size() > cap) {
            int k = l.rbegin()->first;
            l.pop_back();
            m.erase(k);
        }
    }

private:
    int cap;
    list<pair<int, int>> l;
    unordered_map<int, list<pair<int, int>>::iterator> m;
};

代碼截圖