146. LRU 缓存 - 力扣（LeetCode）

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

get函数访问时，缓存中存在数据，则更新数据为最近已使用的；

put函数向缓存中添加数据：

  • 若缓存中存在此数据，则更新为最新值，并将数据更新为最近已使用的；
  • 若缓存中不存在此数据，则新建数据，将数据更新为最近已使用的，并判断是否超出缓存最大容量，若超出，需要选择最近最少使用的页面予以淘汰

使用hash表和双向链表模拟LRU 缓存机制：

  • 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。需要考虑的操作：

    • put时缓存中不存在此数据，需要新建数据添加至链表头，故实现头插法；
    • 将数据更新为最近已使用的，即将数据移至链表头
    • 选择最近最少使用的页面予以淘汰，即删除链表尾的数据
    • 移动数据时，是将该数据从链表中先删除，然后添加到链表头，故考虑删除结点操作

  • 哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。

    • 当选择最近最少使用的页面予以淘汰，即删除链表尾的数据时，map中的值也要通过数据的key删除，故链表的数据中也包含了key
class LinkNode{//双向链表结点
public:
    int key,value;
    LinkNode* prev;
    LinkNode* next;
    LinkNode():key(0),value(0),prev(nullptr),next(nullptr){}
    LinkNode(int _key,int _value):key(_key),value(_value),prev(nullptr),next(nullptr){};
};
class LRUCache {
public:
    unordered_map<int,LinkNode*> cache;//cache通过缓存数据的键映射到其在双向链表中的位置
    // 靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
    LinkNode* head;//伪头部节点
    LinkNode* tail;//伪尾部节点
    int size;//当前存放数据的数量
    int capacity;//容量

    LRUCache(int _capacity):capacity(_capacity),size(0) {
        head=new LinkNode();
        tail=new LinkNode();
        head->next=tail;
        tail->prev=head;
    }
    
    int get(int key) {
        if(cache.find(key)!=cache.end()){//缓存中有数据
            LinkNode * curNode=cache[key];
            moveToHead(curNode);
            return curNode->value;
        }else{
            return -1;
        }
    }
    
    void put(int key, int value) {
        if(cache.find(key)!=cache.end()){//缓存中有数据
            LinkNode * curNode=cache[key];
            curNode->value=value;//更新数据
            moveToHead(curNode);
        }else{//缓存中没有数据
            LinkNode* newNode=new LinkNode(key,value);
            cache[key]=newNode;
            addToHead(newNode);
            ++size;
            if(size>capacity){ // 如果超出容量
                LinkNode* removedNode=removeTail();
                cache.erase(removedNode->key);//根据链表结点的key删除cache中的数据
                delete removedNode;
                --size;
            }

        }
    }
    void addToHead(LinkNode* node) {
        node->prev=head;
        node->next=head->next;
        head->next->prev=node;
        head->next=node;

    }
    void removeNode(LinkNode* node) {
        node->next->prev=node->prev;
        node->prev->next=node->next;
    }
    void moveToHead(LinkNode* node) {
        removeNode(node);
        addToHead(node);
    }
    LinkNode* removeTail() {
        LinkNode* lastNode=tail->prev;
        removeNode(lastNode);
        return lastNode;

    }

};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */