第1章 LRU缓存原理与淘汰策略

LRU（Least Recently Used，最近最少使用）缓存是现代系统中最经典的缓存淘汰策略之一。它的核心思想很简单：当缓存空间满时，优先淘汰那些最长时间未被访问的数据。这一策略基于时间局部性原理——刚刚被访问的数据，在不久的将来很可能再次被访问；而那些长时间未被触及的数据，未来被访问的概率也较低。

1.1 最近最少使用淘汰策略详解

LRU 淘汰策略维护一个严格的“访问时间轴”。每当数据被访问（get 或 put 命中），该数据就会被提升到时间轴的最前端；当缓存达到容量上限时，尾部的数据被移除。这一机制保证：

• 热点数据驻留：高频访问的数据始终靠近头部，不会被误淘汰。
• 冷数据自然淘汰：长时间未被访问的数据逐渐移动到尾部，在缓存满时被清理。
• 无需预知访问模式：LRU 完全基于历史访问记录做决策，适用于大多数通用场景。

1.2 双向链表 + 哈希表：LRU 的经典实现组合

纯数组或单链表无法在 O(1) 时间内同时完成“查找”、“插入”和“删除”三种操作。LRU 缓存需要一种复合数据结构：双向链表（Doubly Linked List）+ 哈希表（HashMap）。二者分工明确：

为什么必须用双向链表？因为删除一个节点时，需要同时修改其前驱和后继节点的指针。单向链表无法 O(1) 获取前驱节点，必须遍历查找，导致删除操作退化为 O(n)。双向链表每个节点都持有 prev 和 next 两个指针，可在常数时间内完成节点摘除。

1.3 核心数据结构定义

以下 C++ 代码展示了 LRU 缓存的核心节点结构和类定义。注意哨兵节点的初始化方式：

// 双向链表节点定义
struct DLinkedNode {
    int key;
    int value;
    DLinkedNode* prev;
    DLinkedNode* next;
    DLinkedNode() : key(0), value(0), prev(nullptr), next(nullptr) {}
    DLinkedNode(int _key, int _value)
        : key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

// LRU 缓存类
class LRUCache {
private:
    unordered_map<int, DLinkedNode*> cache;  // key → 节点指针
    DLinkedNode* head;  // 伪头节点（不存数据）
    DLinkedNode* tail;  // 伪尾节点（不存数据）
    int size;           // 当前缓存数量
    int capacity;       // 缓存容量上限

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

    int get(int key);
    void put(int key, int value);

private:
    void removeNode(DLinkedNode* node);
    void moveToHead(DLinkedNode* node);
    DLinkedNode* removeTail();
};

哈希表 unordered_map<int, DLinkedNode*> 存储 key 到链表节点的映射。这样，通过 key 查找节点的时间为 O(1)，然后借助链表指针完成节点移动或删除。

1.4 get / put 操作流程与时间复杂度分析

两个核心操作完全依赖上述组合结构，每一步都能在常数时间内完成：

get(key) 操作

1. 在哈希表中查找 key：若不存在，返回 -1。
2. 若存在，通过哈希表拿到对应的链表节点指针。
3. 将该节点从链表中当前位置摘除（removeNode）。
4. 将该节点移动到链表头部（moveToHead），表示最近被使用。
5. 返回节点的 value 值。

put(key, value) 操作

1. 在哈希表中查找 key：若存在，更新节点 value，然后将其移动到头部。
2. 若不存在：
   • 创建新节点，插入链表头部，同时添加哈希表映射。
   • size++。若 size > capacity，则淘汰尾部节点：
     • 调用 removeTail() 摘除尾节点（伪尾节点的前驱）。
     • 从哈希表中删除该节点的 key。
     • delete 节点释放内存，size--。

下面的 SVG 结构图直观展示了 LRU 缓存中哈希表与双向链表的协作关系。左侧哈希表存储 key 到链表节点的映射，右侧双向链表维护数据的时间顺序，黄色说明框概括了淘汰策略：