实战：LRU缓存（哈希表+双向链表）

LRU缓存，全称是Least Recently Used Cache。说白了，就是当缓存满了的时候，优先淘汰掉最久没被访问过的那个数据。这个机制在操作系统、数据库、Redis里随处可见。我当年第一次手写LRU时，面试官就坐在对面，盯着我画链表图——那场面，记忆犹新。

核心思路：为什么是哈希表+双向链表？

你想想看，LRU缓存需要支持两个操作：

• get(key)：快速拿到值，同时把该key标记为“最近使用”。
• put(key, value)：插入新数据，如果满了就淘汰最久没用的那个。

哈希表能做到O(1)查找，但没法维护“使用顺序”。双向链表能维护顺序，但查找是O(n)。所以两者结合——哈希表负责快速定位节点，双向链表负责记录访问顺序。嗯，这就是经典解法。

数据结构设计

我习惯用两个结构体：一个存节点，一个存缓存本身。节点里要有key和value，因为淘汰时需要通过key去哈希表里删记录。

struct DLinkedNode {
    int key, 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) {}
};

class LRUCache {
private:
    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode* head;  // 虚拟头节点
    DLinkedNode* tail;  // 虚拟尾节点
    int size;
    int capacity;
    // ...
};

这里用了虚拟头尾节点，避免处理空指针边界。我在项目中第一次写LRU时没加虚拟节点，结果每次移动都要判断是不是头尾，代码又臭又长。后来改成虚拟节点，清爽多了。

核心操作实现

1. 移动节点到头部

这个操作分两步：先把节点从当前位置摘出来，再插入到头部。注意要处理好前后指针的衔接。

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

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

2. get操作

如果key存在，取出值并移动到头部。不存在就返回-1。

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

3. put操作

如果key已存在，更新值并移动到头部。如果不存在，创建新节点插入头部，然后检查容量。超了就把尾部节点删掉。

void put(int key, int value) {
    if (cache.find(key) != cache.end()) {
        DLinkedNode* node = cache[key];
        node->value = value;
        moveToHead(node);
    } else {
        DLinkedNode* node = new DLinkedNode(key, value);
        cache[key] = node;
        addToHead(node);
        ++size;
        if (size > capacity) {
            DLinkedNode* removed = tail->prev;
            removeNode(removed);
            cache.erase(removed->key);
            delete removed;
            --size;
        }
    }
}

完整代码

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

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

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

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

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

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

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

LRU缓存核心流程图

复杂度分析

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

n是缓存容量。哈希表占O(n)，双向链表也占O(n)。整体空间就是O(n)。

避坑指南

• 内存泄漏：C++里new了节点一定要delete。我见过有人只erase哈希表，忘了释放节点内存，跑着跑着内存就爆了。
• 指针悬空：删除节点后，确保没有其他指针还指向它。虚拟头尾节点不要被误删。
• 并发安全：这个实现不是线程安全的。如果在多线程环境下用，记得加锁。我项目里就吃过这个亏，两个线程同时put，链表指针乱成一团。

---

公众号:蓝海资料掘金营，微信deep3321