力扣hot100：146. LRU 缓存

力扣hot100：146. LRU 缓存

听说华为实习笔试考了这题

如何使得插入操作时$O(1)$呢？我们需要维护一个时间的长短，以便于取出离现在最长的时间，这个时间比较容易实现，我们维护一个time表示当前时间，从0开始，然后在使用的一些关键字里面，当一个关键字使用的时间越小，那么它越久未被使用，我们只需要维护一个关键字使用的最小值就行，并且还需要有更新操作。

1. 如果我们使用优先队列，那么插入一次需要$O(logn)$，不满足要求
2. 如果我们排序，那么排序一次需要$O(nlogn)$，不满足要求
3. 我们使用双向链表维护时间递增序列呢？使用哈希表快速查找结点
   • 答案是可行的！因为time是递增的，我们更新中间结点的时间，则必然会将这个结点移动到链表末尾，因此是$O(1)$的。这样做我们甚至可以连时间都不用保存了

由于结点和值都是通过key来查询的，而查询只需要判断key，因此我们可以只使用一个哈希表，来同时维护这两个信息。

class LRUCache {
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        dummy = new List;
        end = dummy;
    }
    
    int get(int key) {
        if(mp.count(key) == 1){
            put_to_end(key);
            return mp[key].first;
        }
        return -1;
    }
    
    void put(int key, int value) {
        if(mp.count(key) == 1){
            mp[key].first = value;
            put_to_end(key);
            return;
        }
        //判断是否超出容量
        if(size == capacity){
            List * temp = dummy->next;
            dummy->next = temp->next;
            if(temp->next) temp->next->pre = dummy;
            mp.erase(temp->key);
            if(temp == end) end = temp->pre;
            delete temp;
        }else ++size;
        //插入全新元素
        List * lst = new List;
        lst->key = key;
        mp[key] = {value,lst};
        //放到末尾
        lst->pre = end;
        end->next = lst;
        end = lst;
        return;
    }
private:
    struct List{
        List * pre = nullptr;
        List * next = nullptr;
        int key;//该key用于删除头结点
    };
    void put_to_end(int key){
        List * access = mp[key].second;
        if(access == end) return;
        access->pre->next = access->next;
        if(access->next) access->next->pre = access->pre;
        access->next = nullptr;
        access->pre = end;
        end->next = access;
        end = access;
        return;
    }
private:
    unordered_map<int,pair<int,List *>> mp;
    int capacity;
    int size = 0;
    List * dummy;
    List * end;
};

需要注意的点：

1. 容量为1，需要删除的结点可能就在队列末尾，因此需要和end比较
2. 最新被使用的结点可能就在队列末尾，因此需要和end比较
3. 更新新结点时，注意end需要指向它
4. 除了使用伪首部之外，还可以使用伪尾部！这样对尾部的判断也减少了许多。

写完之后可以再思考一个，LRU：

• LRU是一个最近最少使用的缓存机制，实现时，本质上，我们将最近使用的放到了双向链表的尾部，而最久没有使用的就再链表头，一旦我们需要这个值的时候，我们只需要使用哈希表快速查找到值在双向链表中的位置，再把它放到链表尾部即可。
• 实际上我们这相当于维护了一个单调序列，并且能够快速修改它的值并更新位置，我们每次只取头部使用，这似乎比优先队列还快。但实际上他们的使用场景不一样，思考一下可以发现双向链表维护的单调序列，每次更新内部结点的值后它必然被更新到最大值，会被放在最后面，而不会更新后还在中间，如果更新后的值并不一定是最值，则这种方法就不适用了。

既然这是一个面试常考的题，那么写完后可以记住：LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。