設(shè)計(jì)實(shí)現(xiàn)LRU緩存機(jī)制

一、要求

LRU：最近最少使用算法

支持：get 和 put 操作
- get(key): 獲取數(shù)據(jù) get, 如果密鑰 (key) 存在于緩存中，則返回對(duì)應(yīng)的值
- put(key, value): 如果密鑰不存在，則寫入其數(shù)據(jù)值。當(dāng)緩存容量達(dá)到上限時(shí)淳蔼，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最近最少未使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間裁眯。
get 和 put 時(shí)間復(fù)雜度 $O(1)$
題目：https://leetcode-cn.com/problems/lru-cache/

二鹉梨、實(shí)現(xiàn)

1. 說明

其實(shí)標(biāo)準(zhǔn)的 hash 數(shù)據(jù)結(jié)構(gòu)可以實(shí)現(xiàn)get 操作 $O(1)$ , 但是針對(duì)put 操作的中，`到達(dá)內(nèi)存容量上限是穿稳，刪除最近最少使用的數(shù)據(jù)值的, 簡單hash 無法做到 $O(1)$ 存皂，因?yàn)闊o法判斷那些數(shù)據(jù)是最近最少使用的。我們采取一個(gè)雙向鏈表去維護(hù)LRU的數(shù)據(jù)值逢艘。

雙向鏈表

如圖所示艰垂，我們建立一個(gè)雙向的鏈表去維持LRU 這么一個(gè)概念，通過頭節(jié)點(diǎn)和尾節(jié)點(diǎn)去維護(hù)這個(gè)雙向鏈表埋虹。我們每次操作一個(gè)節(jié)點(diǎn)（get, put)的時(shí)候猜憎，都把這個(gè)節(jié)點(diǎn)移到頭節(jié)點(diǎn)后面。這樣經(jīng)過一系列的操作后搔课，鏈表除了尾節(jié)點(diǎn)的最后一個(gè)就是最近最少使用的數(shù)據(jù)值胰柑。因?yàn)榉彩潜徊僮鬟^的節(jié)點(diǎn)都是插入到頭節(jié)點(diǎn)后面，未被操作的節(jié)點(diǎn)慢慢就挪到了尾部爬泥。

2. 實(shí)現(xiàn)hash

這里面我們采取的C++ STL中的unordered_map作為hash結(jié)構(gòu)的實(shí)現(xiàn)柬讨。

3. 實(shí)現(xiàn)雙向鏈表

鏈表的節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)

template<typename K, typename V>
struct BiNode {
    K key;
    V value;
    BiNode(int k, int v = 0):key(k), value(v){};
    shared_ptr<BiNode> pre;
    shared_ptr<BiNode> next;
};

template<typename K, typename V>
bool operator==(const BiNode<K, V>& node1, const BiNode<K, V>& node2){
    return node1.key == node2.key;
}

namespace std {

    template<typename K, typename V>
    struct hash<BiNode<K, V>> {
        size_t operator()(const BiNode<K, V>& node) const noexcept {
            return std::hash<size_t>()(node.key);
        }
    };
}

應(yīng)為我們會(huì)在unorderd_map中存儲(chǔ)鏈表，所以要重載等于（==）和hash袍啡，使節(jié)點(diǎn)可以計(jì)算哈希值和判斷散列沖突踩官。

實(shí)現(xiàn)維護(hù)LRU的雙向鏈表

template<typename K, typename V>
class LRUList {
public:
    using NodeType = BiNode<K, V>;
    using PNodeType = shared_ptr<NodeType>;

    LinkedList(){
        head_ = make_shared<NodeType>();
        tail_ = make_shared<NodeType>();
        head_->next = tail_;
        tail_->pre = head_;
    }

    PNodeType add(K key, V value){
        PNodeType node = make_shared<NodeType>(key, value);
        PNodeType next = head_->next;
        node->next = next;
        next->pre = node;
        head_->next = node;
        node->pre = head_;
    }

    PNodeType pop(){
        PNodeType target = tail_->pre;
        if(target == head_)
            return NullNode;
        PNodeType pre = target->pre;
        pre->next = tail_;
        tail_->pre = pre;
        return target;
    }

    PNodeType move_to_head(PNodeType node){
        PNodeType pre  = node->pre;
        PNodeType next = node->next;
        pre->next = next;
        next->pre = pre;

        next = head_->next;
        
        node->next = next;
        next->pre = node;
        node->pre = head_;
        head_->next = node;
    }

public:
    static const PNodeType NullNode = make_shared<NodeType>();
private:
    PNodeType head_;
    PNodeType tail_;
};

可以看到我們所有操作都是通過頭節(jié)點(diǎn)和尾節(jié)點(diǎn)實(shí)現(xiàn)的，所以我們這個(gè)鏈表的操作的復(fù)雜度都是 $O(1)$ 的境输。

三蔗牡、LRU 緩存機(jī)制

最終我們組合unordered_map(哈希）和 LRUList (雙向鏈表）實(shí)現(xiàn) LRU 緩存機(jī)制。

get(key): 獲取的時(shí)候我們通過unordered_map直接獲得對(duì)應(yīng)的值嗅剖， $O(1)$
put(key, value): 插入數(shù)據(jù)時(shí)候如果鍵值存在辩越，直接插入。如果不存在信粮，內(nèi)存足夠時(shí)黔攒，直接將節(jié)點(diǎn)插入unordered_map和LRUList中即可；不足時(shí)，現(xiàn)在LRUList中獲取最近最實(shí)用的值督惰，把其在哈希表和雙向鏈表中刪除不傅，再插入新的節(jié)點(diǎn)。復(fù)雜度 $O(1)$


template<typename K, typename V>
class LRUCache {
public:
    using PNodeType = shared_ptr<BiNode<K, V>>;
public:

    LRUCache(int cap):cap_(cap){};
    PNodeType get(int key){
        if(dict_.count(key)){
            PNodeType node = dict_[key];
            list_.move_to_head(node);
            return node;    
        }
        
        return LRUList<K, V>::NullNode;
    }

    void set(int key, int val){
        PNodeType cur = nullptr;
        
        if(dict_.count(key)){
            cur = dict_[key];
            cur->value = val;
        }else{
            if(dict_.size() == cap_){
                auto del_node = list_.pop();
                dict_.erase(del_node->key);
            }
            cur = list_.add(key, val);
            dict_[key] = cur;
        }
        list_.move_to_head(cur);
    }

private:
    size_t cap_ = 0;
    LRUList<K, V> list_ = {};
    unordered_map<K, BiNode<K, V>> dict_ = {};
};