这是一道面试中常考的算法题 考察频度非常高 所以必须要了解

但是我们也不要那么功利 既然这个题考察频率如此之高 那它的背后肯定有更多有价值的东西等着我们去探索 所以先简单介绍一下LRU到底是什么

简单介绍

LRU缓存(Least Recently Used Cache) 是一种常用的缓存淘汰策略 其核心思想是优先移除长时间未被访问的数据项 以确保缓存中始终存储最新和最频繁使用的数据

LRU缓存基于“最近最少使用”的原则，当一个数据项被访问时，如果该数据已经在缓存中，则将其移动到缓存的最前面，表示最近被访问过；如果缓存已满，则移除最久未被访问的数据项，为新的数据项腾出空间‌

工作原理

LRU缓存通过维护一个有序的访问队列来实现其功能。具体来说，可以使用双向链表来维护这个访问队列，链表中的节点按照数据的访问顺序排列。最近被访问的数据项位于链表的前部，而最久未被访问的数据项位于链表的尾部。当某个数据被访问时，如果该数据已经存在于缓存中，就将其移动到链表的头部；如果缓存已满，则移除链表尾部的数据项‌

具体的应用场景

‌ Web服务器页面缓存‌：在Web服务器中，LRU缓存常用于存储页面内容或资源文件，如HTML、CSS、JavaScript等。当用户请求访问某个页面时，Web服务器会首先检查缓存中是否存在该页面的缓存副本，如果存在，则直接返回缓存的页面内容‌

‌ 数据库查询优化‌：在数据库查询中，LRU缓存可以优化查询效率，减少对磁盘的访问次数

‌网络服务器性能提升‌：通过使用LRU缓存，可以提升网络服务器的响应速度和性能‌

实现LRU缓存的算法还是vue中keep-alive组件的核心算法 和我们即将学习的vue框架也有着很大的关系 所以前端er也要重视起来!!!

上题!!!

到底要怎么去实现满足LRU缓存约束的数据结构呢?

这并不简单 但是我们可以将问题转化一下 可以用移动一摞书的例子来感受一下这个机制

是不是很巧妙呢? 又根据我们刚刚提到的LRU缓存工作原理 可以用双向链表来模拟这一摞书 又因为我们需要根据key来找到对应的节点进行操作 很容易想到使用哈希表来实现快速定位

这里提到的哨兵很重要 根据图片所示 我们把哨兵的后继节点 记为首节点 哨兵的前驱节点记为尾部节点 就形成了一个完整的复合条件数据结构

分析到此结束 接下来就是实现了 我们需要有双向链表的添加,删除,和查找方法 查找很简单 就不说明了 下面是删除节点和增加节点到链表头的操作说明

接下来是代码的逐步分析

1.构造节点(书)

2.设置容量,哨兵节点,hashMap

3.删除和增添节点到链表头

4.获取key对应的节点 同时把该节点移动到链表头部

5.构造函数 初始化capacity 创建虚拟头结点dummy 初始化链表指针

6.实现get函数

找到返回对应值 未找到返回-1

7.实现put函数

先看当前链表中有没有这个节点(有没有这本书) 如果有 就将对应值更新 没有就创建新节点放在链表头(把新书放在最上面) 如果超过节点数量超过capacity 去掉末尾节点的(key,value)(拿掉最底下的书)

到这里就实现完成啦^_^!

完整代码贴在这里

class Node {
public:
    int key;
    int value;
    Node* prev;
    Node* next;
    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;

    // 删除一个节点（抽出一本书）
    void remove(Node* x) {
        x->prev->next = x->next;
        x->next->prev = x->prev;
    }

    // 在链表头添加一个节点（把一本书放在最上面）
    void push_front(Node* x) {
        x->prev = dummy;
        x->next = dummy->next;
        x->prev->next = x;
        x->next->prev = x;
    }
    

    // 获取 key 对应的节点，同时把该节点移到链表头部
    Node* get_node(int key) {
        auto it = key_to_node.find(key);
        if (it == key_to_node.end()) { // 没有这本书
            return nullptr;
        }
        Node* node = it->second; // 有这本书
        remove(node); // 把这本书抽出来
        push_front(node); // 放在最上面
        return node;
    }

public:
    LRUCache(int capacity) : capacity(capacity), dummy(new Node()) {
        dummy->prev = dummy;
        dummy->next = dummy;
    }

    int get(int key) {
        Node* node = get_node(key);
        return node ? node->value : -1;
    }

    void put(int key, int value) {
        Node* node = get_node(key);
        if (node) { // 有这本书
            node->value = value; // 更新 value
            return;
        }
        key_to_node[key] = node = new Node(key, value); // 新书
        push_front(node); // 放在最上面
        if (key_to_node.size() > capacity) { // 书太多了
            Node* back_node = dummy->prev;
            key_to_node.erase(back_node->key);
            remove(back_node); // 去掉最后一本书
            delete back_node; // 释放内存
        }
    }
};

这一题搞下来真不简单呀 但是再困难的问题我们都要克服 我们要为更好的未来奋斗

留一句励志的诗句吧 望你我共勉

千淘万漉虽辛苦,吹尽狂沙始到金