1. 什么是 LRU 算法

LRU（Least Recently Used，最近最少使用）是一种常用的缓存淘汰策略。它的核心思想是：当缓存空间不足时，优先淘汰那些最长时间没有被访问的数据。因为在实际应用中，最近被访问过的数据往往在短时间内更有可能再次被访问，所以保留这些"热点数据"能有效提升缓存命中率。

LRU 算法广泛应用于操作系统页面置换、数据库缓冲池、Redis 内存淘汰、浏览器缓存等场景，是面试和工程实践中都非常重要的基础算法。

2. LRU 的基本原理

LRU 算法维护一个按访问时间排序的数据结构，每次访问某个数据时，就把该数据移动到"最近使用"的位置；当缓存满时，从"最久未使用"的位置淘汰数据。整个过程可以概括为两个操作：

• 访问（get）：如果数据存在，返回其值，并将该数据移动到最近使用的位置。
• 插入（put）：如果数据已存在，更新其值并移动到最近使用的位置；如果数据不存在，则插入新数据。若缓存已满，先淘汰最久未使用的数据，再插入新数据。

为了高效实现这两个操作，LRU 通常采用"哈希表 + 双向链表"的组合结构：哈希表负责 O(1) 时间定位节点，双向链表负责 O(1) 时间完成节点的插入和删除。

3. 数据结构设计

双向链表中的每个节点保存键值对，链表头部表示最近使用的数据，链表尾部表示最久未使用的数据。哈希表的键是数据的 key，值是指向链表节点的指针。这样设计的好处是：

• 通过哈希表可以在 O(1) 时间内找到任意 key 对应的链表节点。
• 通过双向链表可以在 O(1) 时间内把某个节点移动到头部，或删除尾部节点。

之所以使用双向链表而不是单向链表，是因为删除某个节点时需要知道它的前驱节点，双向链表可以直接拿到前驱指针，从而在 O(1) 时间内完成删除操作。

4. C++ 代码实现

下面给出一个基于哈希表和双向链表的 LRU 缓存实现，支持 get 和 put 两个操作，时间复杂度均为 O(1)。

#include <unordered_map>

using namespace std;

struct Node {
    int key;
    int value;
    Node* prev;
    Node* next;
    Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    int capacity;
    unordered_map<int, Node*> cache;
    Node* head;  // 虚拟头节点，head->next 是最近使用的节点
    Node* tail;  // 虚拟尾节点，tail->prev 是最久未使用的节点

    void removeNode(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

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

    void moveToHead(Node* node) {
        removeNode(node);
        addToHead(node);
    }

    Node* removeTail() {
        Node* node = tail->prev;
        removeNode(node);
        return node;
    }

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

    int get(int key) {
        if (cache.find(key) == cache.end()) {
            return -1;
        }
        Node* node = cache[key];
        moveToHead(node);
        return node->value;
    }

    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            Node* node = cache[key];
            node->value = value;
            moveToHead(node);
            return;
        }
        if (cache.size() >= capacity) {
            Node* removed = removeTail();
            cache.erase(removed->key);
            delete removed;
        }
        Node* newNode = new Node(key, value);
        cache[key] = newNode;
        addToHead(newNode);
    }
};

代码中使用了两个虚拟节点 head 和 tail，避免了对链表为空等边界情况的特殊判断，使插入和删除操作更加简洁统一。

5. 复杂度分析

操作	时间复杂度	空间复杂度
get	O(1)	O(n)
put	O(1)	O(n)

其中 n 是缓存容量。哈希表保证了查找的 O(1) 复杂度，双向链表保证了节点移动和删除的 O(1) 复杂度，整体空间开销为 O(n)。

6. 实际应用场景

LRU 算法在真实系统中应用非常广泛，常见场景包括：

• 操作系统：页面置换算法，当物理内存不足时淘汰最久未使用的页面。
• Redis：内存淘汰策略之一，当内存达到上限时按 LRU 近似算法淘汰键。
• 数据库：MySQL 的 InnoDB 缓冲池使用改进的 LRU 算法管理数据页。
• 浏览器：HTTP 缓存和本地图片缓存中用于淘汰旧资源。

7. 总结

LRU 算法通过"最近使用"这一局部性原理，在有限的缓存空间内尽可能保留热点数据，是工程中最经典的缓存淘汰策略之一。掌握"哈希表 + 双向链表"的实现方式，不仅有助于理解缓存系统的设计思路，也是面试中高频考察的算法题。实际生产环境中，还可以根据业务特点对 LRU 进行改进，例如 Redis 的近似 LRU 和 MySQL 的分段 LRU，以在性能和精度之间取得平衡。