LRU算法

LRU算法

前言：

我们常用缓存提升数据查询速度，由于缓存的容量有限，当达到上限的时候，就需要删除部分数据挪出空间，这样新的数据才可以添加进来，缓存数据不能随机删除，一般情况下需要根据某种特定的算法删除缓存数据，常用的淘汰算法右LRU，LFU，FIFO

核心思想：如果数据最近被访问过，那么是热门数据，下次很大概率会再次被使用。如果内存满了，有限淘汰最近很少使用的数据

LRU: Least Recently Used, 最近最少使用，主要应用场景是缓存，缓存规则如下。

①.最近被使用或访问的数据放置在最前面;
②.没当缓存命中(即缓存数据被访问)则将数据移到头部;
③.当缓存数量达到最大值时，将最近最少访问的数据剔除;

• 访问一个数据，哪个数据就会被添加到头节点。

class Node { // 双向链表的节点
public:
    int key;    // key值是为了便于哈希表的定位
    int value;  // 缓存的数据
    Node* prev; // 前驱指针
    Node* next; // 后驱指针
    // 构造函数
    // 给一个默认参数key为0，v为0
    Node(int k = 0, int v = 0) : key(k), value(v) {}
};

class LRUCache {
private:
    int capacity; // 缓存的容量
    Node* dummy;  // 哨兵节点，双向链表的头节点
    unordered_map<int, Node*> key_to_node;
    // 哈希表，存储key和node的信息
public:
    // 构造函数
    LRUCache(int capacity) : capacity(capacity), dummy(new Node()) {
        dummy->prev = dummy;
        dummy->next = dummy;
    }

    // 删除一个节点（抽出一本书）
    // 双向链表的删除节点
    void remove(Node* x) {
        x->prev->next = x->next; // 前面的后继要改
        x->next->prev = x->prev; // 后面的前驱要改
    }

    // 在链表头添加一个节点（把一本书放在最上面）
    // 双向链表的头插
    void push_front(Node* x) {
        x->next = dummy->next; // 1
        dummy->next = x;       // 4
        x->prev = dummy;       // 2
        x->next->prev = x;     // 3
        // 4一定要在1的后面，其他的顺序随意，绑线原则
    }

    Node* get_node(int key) {
        auto it = key_to_node.find(key);
        if (it == key_to_node.end()) // 没有这本书
            return nullptr;
        auto node = it->second; // 有这本书
        remove(node);           // 把这本书抽出来
        push_front(node);       // 放在最上面
        return node;            //返回这本书
    }

    int get(int key) {
        auto node = get_node(key);
        //如果node不为空，就返回node的value
        //如果为空，就是-1
        return node ? node->value : -1;
    }

    void put(int key, int value) {
        auto node = get_node(key);//获取node
        //node不为空，就是有这本书
        if (node) {              // 有这本书
            node->value = value; // 更新 value
            return;
        }
        node = new Node(key, value); // 新书
        key_to_node[key] = node;
        push_front(node);                               // 放在最上面

        //超过容量
        if (key_to_node.size() > capacity) {            // 书太多了
            auto back_node = dummy->prev;//头节点的前驱放的是最后一个节点
            key_to_node.erase(back_node->key);
            remove(back_node); // 去掉最后一本书
            delete back_node;  // 释放内存
        }
    }
};