实现 LRU 缓存(并发安全) ​

面试考点 ​

LRU 缓存是面试中出现频率最高的数据结构题之一。面试官考察你是否理解 LRU 的淘汰策略、哈希表 + 双向链表实现 O(1) 访问和淘汰、以及如何用读写锁或互斥锁实现线程安全的并发访问。

核心概念 ​

LRU(Least Recently Used)缓存的策略是:当缓存满时,淘汰最近最少使用的条目。数据结构选择:unordered_map 提供 O(1) 的键查找,std::list 的 splice 操作提供 O(1) 的顺序调整。链表头部是最近使用的,尾部是最久未使用的。每次访问或插入都把条目移到头部,淘汰时删除尾部。

基本示例 ​

cpp
#include <iostream>
#include <unordered_map>
#include <list>
#include <optional>
#include <mutex>
#include <shared_mutex>
#include <thread>
#include <vector>
#include <cassert>
#include <string>

// ============================
// 非线程安全版 LRU 缓存
// ============================

template<typename Key, typename Value>
class LRUCache {
public:
    // 缓存条目:键值对
    using Entry = std::pair<Key, Value>;
    // 链表迭代器
    using ListIterator = typename std::list<Entry>::iterator;

    explicit LRUCache(size_t capacity) : capacity_(capacity) {}

    // 查找:O(1)
    std::optional<Value> get(const Key& key) {
        auto it = map_.find(key);
        if (it == map_.end()) {
            return std::nullopt;  // 缓存未命中
        }

        // 命中:把条目移到链表头部(最近使用)
        // splice 是 O(1) 操作,不会使迭代器失效
        list_.splice(list_.begin(), list_, it->second);

        return it->second->second;
    }

    // 插入/更新:O(1)
    void put(const Key& key, const Value& value) {
        auto it = map_.find(key);

        if (it != map_.end()) {
            // 键已存在:更新值并移到头部
            it->second->second = value;
            list_.splice(list_.begin(), list_, it->second);
            return;
        }

        // 缓存已满:淘汰尾部(最久未使用)
        if (list_.size() >= capacity_) {
            auto& back = list_.back();
            map_.erase(back.first);  // 从哈希表删除
            list_.pop_back();        // 从链表删除
        }

        // 插入新条目到头部
        list_.emplace_front(key, value);
        map_[key] = list_.begin();
    }

    // 删除
    bool erase(const Key& key) {
        auto it = map_.find(key);
        if (it == map_.end()) return false;

        list_.erase(it->second);
        map_.erase(it);
        return true;
    }

    size_t size() const { return map_.size(); }
    size_t capacity() const { return capacity_; }
    bool empty() const { return map_.empty(); }

    // 检查键是否存在(不改变访问顺序)
    bool contains(const Key& key) const {
        return map_.find(key) != map_.end();
    }

    // 打印缓存内容(调试用)
    void dump() const {
        std::cout << "LRU [";
        for (auto it = list_.begin(); it != list_.end(); ++it) {
            if (it != list_.begin()) std::cout << ", ";
            std::cout << it->first << ":" << it->second;
        }
        std::cout << "] (最左=最近使用)" << std::endl;
    }

private:
    size_t capacity_;
    std::list<Entry> list_;                         // 有序链表
    std::unordered_map<Key, ListIterator> map_;     // 键 → 链表迭代器
};

// ============================
// 线程安全版 LRU 缓存
// ============================

template<typename Key, typename Value>
class ConcurrentLRUCache {
public:
    using Entry = std::pair<Key, Value>;
    using ListIterator = typename std::list<Entry>::iterator;

    explicit ConcurrentLRUCache(size_t capacity) : capacity_(capacity) {}

    // 查找(需要写锁,因为 splice 修改链表)
    std::optional<Value> get(const Key& key) {
        std::unique_lock<std::shared_mutex> lock(mutex_);

        auto it = map_.find(key);
        if (it == map_.end()) {
            return std::nullopt;
        }

        // 移到头部(修改链表结构,需要写锁)
        list_.splice(list_.begin(), list_, it->second);
        return it->second->second;
    }

    // 只读查找(不改变顺序,用读锁)
    std::optional<Value> peek(const Key& key) const {
        std::shared_lock<std::shared_mutex> lock(mutex_);

        auto it = map_.find(key);
        if (it == map_.end()) {
            return std::nullopt;
        }
        return it->second->second;
    }

    // 插入/更新
    void put(const Key& key, const Value& value) {
        std::unique_lock<std::shared_mutex> lock(mutex_);

        auto it = map_.find(key);
        if (it != map_.end()) {
            it->second->second = value;
            list_.splice(list_.begin(), list_, it->second);
            return;
        }

        if (list_.size() >= capacity_) {
            auto& back = list_.back();
            map_.erase(back.first);
            list_.pop_back();
        }

        list_.emplace_front(key, value);
        map_[key] = list_.begin();
    }

    // 删除
    bool erase(const Key& key) {
        std::unique_lock<std::shared_mutex> lock(mutex_);

        auto it = map_.find(key);
        if (it == map_.end()) return false;

        list_.erase(it->second);
        map_.erase(it);
        return true;
    }

    size_t size() const {
        std::shared_lock<std::shared_mutex> lock(mutex_);
        return map_.size();
    }

    bool contains(const Key& key) const {
        std::shared_lock<std::shared_mutex> lock(mutex_);
        return map_.find(key) != map_.end();
    }

private:
    size_t capacity_;
    std::list<Entry> list_;
    std::unordered_map<Key, ListIterator> map_;
    mutable std::shared_mutex mutex_;  // 读写锁
};

// ============================
// 分段锁 LRU 缓存(高并发版)
// ============================

// 把缓存分成多个段,每段独立加锁,减少锁竞争
template<typename Key, typename Value, size_t NumSegments = 16>
class ShardedLRUCache {
public:
    explicit ShardedLRUCache(size_t total_capacity) {
        // 每段的容量
        size_t per_shard = (total_capacity + NumSegments - 1) / NumSegments;
        for (size_t i = 0; i < NumSegments; i++) {
            shards_[i] = std::make_unique<ConcurrentLRUCache<Key, Value>>(per_shard);
        }
    }

    std::optional<Value> get(const Key& key) {
        return shard(key).get(key);
    }

    void put(const Key& key, const Value& value) {
        shard(key).put(key, value);
    }

    bool erase(const Key& key) {
        return shard(key).erase(key);
    }

private:
    // 根据键的哈希值选择段
    ConcurrentLRUCache<Key, Value>& shard(const Key& key) {
        size_t h = std::hash<Key>{}(key);
        return *shards_[h % NumSegments];
    }

    std::unique_ptr<ConcurrentLRUCache<Key, Value>> shards_[NumSegments];
};

// ============================
// 测试
// ============================

void test_basic() {
    std::cout << "--- 基本 LRU ---" << std::endl;

    LRUCache<int, std::string> cache(3);

    cache.put(1, "一");
    cache.put(2, "二");
    cache.put(3, "三");
    cache.dump();  // [3:三, 2:二, 1:一]

    // 访问 1,把它移到头部
    auto v = cache.get(1);
    std::cout << "get(1): " << v.value_or("miss") << std::endl;
    cache.dump();  // [1:一, 3:三, 2:二]

    // 插入 4,淘汰最久未使用的 2
    cache.put(4, "四");
    cache.dump();  // [4:四, 1:一, 3:三]

    // 2 已被淘汰
    auto miss = cache.get(2);
    std::cout << "get(2): " << miss.value_or("miss") << std::endl;
}

void test_concurrent() {
    std::cout << "\n--- 并发 LRU ---" << std::endl;

    ConcurrentLRUCache<int, int> cache(1000);

    // 多线程并发读写
    std::vector<std::thread> threads;
    for (int t = 0; t < 4; t++) {
        threads.emplace_back([&cache, t]() {
            for (int i = 0; i < 1000; i++) {
                int key = t * 1000 + i;
                cache.put(key, key * 10);
            }
            for (int i = 0; i < 1000; i++) {
                int key = t * 1000 + i;
                cache.get(key);
            }
        });
    }

    for (auto& t : threads) t.join();
    std::cout << "并发测试完成,缓存大小: " << cache.size() << std::endl;
}

void test_sharded() {
    std::cout << "\n--- 分段锁 LRU ---" << std::endl;

    ShardedLRUCache<int, int> cache(10000);

    std::vector<std::thread> threads;
    for (int t = 0; t < 8; t++) {
        threads.emplace_back([&cache, t]() {
            for (int i = 0; i < 5000; i++) {
                int key = t * 5000 + i;
                cache.put(key, key);
                cache.get(key);
            }
        });
    }

    for (auto& t : threads) t.join();
    std::cout << "分段锁测试完成" << std::endl;
}

int main() {
    test_basic();
    test_concurrent();
    test_sharded();
    return 0;
}

LRU 缓存的数据结构选择 ​

操作哈希表双向链表组合效果
查找O(1)O(n)O(1)
插入O(1)O(1)O(1)
删除O(1)O(1)(已知位置)O(1)
调整顺序-O(1)(splice)O(1)
淘汰最旧-O(1)(pop_back)O(1)

并发策略对比 ​

策略实现优点缺点
全局互斥锁std::mutex实现简单所有操作串行化
读写锁std::shared_mutex读操作可并行get 仍需写锁(移动元素)
分段锁N 个独立缓存锁粒度小,并发度高每段容量独立,淘汰不全局
无锁atomic + CAS最高并发度极难实现

常见问题 ​

为什么 get 操作也需要写锁?

get 不仅读取值,还要把访问的条目移到链表头部(更新访问顺序)。splice 操作修改了链表的结构,不能和其他读写操作并发。如果只是查看值不更新顺序(peek),可以用读锁。

std::list::splice 为什么是 O(1)?

splice 只修改链表节点的前后指针,不涉及内存分配/释放和数据拷贝。把一个节点从链表中间移到头部只需要修改 6 个指针(原位置的前后节点、新位置的前后节点、以及节点自身的前后指针)。

分段锁的缺点是什么?

每个分段是独立的 LRU 缓存,淘汰策略只在段内生效。如果某些段的访问频率远高于其他段,可能出现热门段频繁淘汰而冷门段浪费容量的情况。一种改进是用全局的访问频率统计来指导淘汰。

适用场景 ​

  • 数据库查询缓存
  • Web 服务的 session 缓存
  • DNS 解析缓存
  • 文件系统的页缓存

注意事项 ​

  • LRU 缓存的容量需要根据内存和访问模式调整
  • 缓存击穿(热点 key 过期瞬间大量请求)需要加互斥锁或预热
  • 缓存雪崩(大量 key 同时过期)需要随机化过期时间
  • 分段锁的段数通常设为 CPU 核心数的 2-4 倍
  • 值类型如果较大,考虑存储 shared_ptr 减少拷贝

总结 ​

LRU 缓存用 unordered_map + std::list 实现 O(1) 的查找、插入和淘汰。哈希表存储键到链表迭代器的映射,链表维护访问顺序。并发安全版用 shared_mutex 读写锁保护,高并发场景用分段锁减少竞争。面试中要能手写非线程安全版(get/put 的完整逻辑),解释 splice 的 O(1) 原理,以及讨论并发策略的权衡。