3. 哈希表与双向链表实现LRU核心

LRU 缓存的高效性依赖于两种数据结构的配合：哈希表提供 O(1) 的键查找，双向链表维护访问顺序。本章节将详细拆解节点结构、链表头尾操作、哈希表快速查找以及将访问节点移动到链表头部的核心逻辑。

3.1 节点结构设计

每个缓存项在链表中对应一个节点，节点内部需要存储键、值以及前后指针。哈希表则存储键到节点的映射。

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) {}
};

3.2 双向链表头尾操作

LRU 算法将最近访问的节点置于链表头部，尾部节点即为最久未使用的候选淘汰项。需要维护两个哨兵节点：head 和 tail（伪头、伪尾），避免空指针判断。

• 初始化：头尾互指：head->next = tail; tail->prev = head;
• 头插法：将节点插入到 head 之后，即成为第一个有效节点。
• 尾删法：删除 tail 之前的节点（即真正最后一个有效节点），得到待淘汰的缓存项。
• 移除节点：通过节点指针直接将其从链表中断开：node->prev->next = node->next; node->next->prev = node->prev;

// 移除任意节点（内部方法）
void removeNode(DLinkedNode* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
}

// 将节点添加到头部
void addToHead(DLinkedNode* node) {
    node->prev = head;
    node->next = head->next;
    head->next->prev = node;
    head->next = node;
}

// 移除尾部节点并返回（用于淘汰）
DLinkedNode* removeTail() {
    DLinkedNode* node = tail->prev;
    removeNode(node);
    return node;
}

3.3 哈希表快速查找

使用 C++ STL 的 unordered_map 存储 key 到节点指针的映射，实现 O(1) 查找。哈希表本身不参与顺序维护，仅用于定位链表节点。

unordered_map<int, DLinkedNode*> cache;

当用户 get(key) 时，先查哈希表：

int get(int key) {
    if (cache.find(key) == cache.end()) {
        return -1; // 不存在
    }
    DLinkedNode* node = cache[key];
    // 将该节点移动到链表头部（表示最近使用）
    moveToHead(node);
    return node->value;
}

3.4 移动节点到头部

移动操作是 LRU 算法的核心步骤：每次访问一个节点（get 或 put 已存在的 key），都需要将其从原位置断开，再插入到链表头部。将前述两个基本操作组合即可：

void moveToHead(DLinkedNode* node) {
    removeNode(node);   // 从原位置移除
    addToHead(node);    // 插入头部
}

移动后，该节点成为最新使用的节点，不会因后续容量满而被立即淘汰。

3.5 整体结构数据流

下图展示了哈希表与双向链表如何协作完成一次 get 命中操作：

3.6 关键复杂度总结

3.7 完整 LRUCache 类骨架

class LRUCache {
private:
    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int capacity;
    int size;

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

    ~LRUCache() {
        // 清理所有节点（略）
    }

    int get(int key) { /* 见上文 */ }
    void put(int key, int value) { /* 第4章详细讲解 */ }

private:
    void addToHead(DLinkedNode* node) { /* ... */ }
    void removeNode(DLinkedNode* node) { /* ... */ }
    void moveToHead(DLinkedNode* node) { /* ... */ }
    DLinkedNode* removeTail() { /* ... */ }
};