LRU 缓存

LRU（Least Recently Used，最近最少使用）缓存的规则是：每次访问或更新一个 key，就将它标记为"最近使用"；容量满时淘汰最久没有访问的 key。

要同时满足高效查找与高效调整访问顺序，经典组合是：

std::unordered_map<Key, ListIterator>：由 key 直接定位链表节点，平均 O(1) 查找；
std::list<std::pair<Key, Value>>：双向链表维护访问顺序，头部是最近使用（MRU），尾部是最久未使用（LRU）；已知节点时移动与删除都是 O(1)。

unordered_map 的最坏复杂度会因严重哈希冲突退化到 O(n)，所以这里的 O(1) 指平均复杂度。

实现

下面以 int 为 key/value。泛型版本只需将 int 替换为模板参数并提供合适的哈希函数。

cpp

#include <list>
#include <stdexcept>
#include <unordered_map>
#include <utility>

class LRUCache {
public:
    explicit LRUCache(std::size_t capacity) : capacity_(capacity) {
        if (capacity == 0) {
            throw std::invalid_argument("capacity must be positive");
        }
    }

    bool get(int key, int& value) {
        auto map_it = index_.find(key);
        if (map_it == index_.end()) {
            return false;
        }

        items_.splice(items_.begin(), items_, map_it->second);
        value = map_it->second->second;
        return true;
    }

    void put(int key, int value) {
        auto map_it = index_.find(key);
        if (map_it != index_.end()) {
            map_it->second->second = value;
            items_.splice(items_.begin(), items_, map_it->second);
            return;
        }

        if (items_.size() == capacity_) {
            const int lru_key = items_.back().first;
            index_.erase(lru_key);
            items_.pop_back();
        }

        items_.emplace_front(key, value);
        index_[key] = items_.begin();
    }

private:
    using Item = std::pair<int, int>;
    using Iterator = std::list<Item>::iterator;

    std::size_t capacity_;
    std::list<Item> items_;
    std::unordered_map<int, Iterator> index_;
};

使用示例：

cpp

LRUCache cache(2);
cache.put(1, 100);
cache.put(2, 200);

int value;
cache.get(1, value); // value = 100
cache.put(3, 300);   // 淘汰 2

复杂度与易错点

操作	平均复杂度	原因
`get`	O(1)	哈希查找 + `list::splice`
更新已有 key	O(1)	哈希查找 + 移到表头
插入新 key	O(1)	头插；满容量时尾删
空间	O(capacity)	哈希表和链表各保存一份索引/节点信息

不能只用 vector 保存顺序：中间移动元素通常是 O(n)；
不能只用 unordered_map：它不保存"最近使用顺序"；
上述实现不是线程安全的。多线程同时调用 get/put 时，要在外部或类内部加 mutex；
高性能缓存还可能需要 TTL、分片锁、淘汰统计、容量按字节计算等能力。

LRU 缓存 ​

实现 ​

复杂度与易错点 ​

关联笔记 ​

LRU 缓存

实现

复杂度与易错点

关联笔记