题目：在C++中实现一个线程安全的LRU缓存

2026-01-16 作者 stdcpp

在许多高性能应用中，LRU（Least Recently Used，最近最少使用）缓存是一种常见的数据结构，用于在内存受限的环境下保持热点数据。本文将演示如何在C++17/20环境下实现一个线程安全的LRU缓存，并讨论其关键实现细节和性能优化点。

1. LRU缓存的基本概念

LRU缓存保持一组键值对，并在达到容量上限时淘汰最近最少使用的条目。典型实现需要：

常数时间的访问：通过哈希表实现 O(1) 的查找与更新。
快速维护访问顺序：通过双向链表维护条目的使用顺序，最近使用的元素移到链表头，最久未使用的元素在尾部。
容量控制：当容量已满时，移除链表尾部元素。

2. 线程安全的设计思路

在多线程环境下，LRU缓存必须保证：

读写互斥：多个线程同时读可以并发，但读写、写写必须互斥。
避免死锁：锁的粒度与顺序需谨慎。
性能最优：读操作多的场景下，锁开销不宜过高。

方案：使用 std::shared_mutex（C++17）来实现读写锁。读操作获取共享锁；写操作获取独占锁。

3. 关键类与结构

#include <unordered_map>
#include <list>
#include <shared_mutex>
#include <optional>

template<typename Key, typename Value>
class LRUCache {
public:
    LRUCache(size_t capacity) : capacity_(capacity) {}

    // 获取键对应的值（若存在）
    std::optional <Value> get(const Key& key) {
        std::shared_lock lock(mutex_);
        auto it = map_.find(key);
        if (it == map_.end()) return std::nullopt;

        // 需要提升到独占锁以移动到前端
        lock.unlock();
        std::unique_lock ulock(mutex_);
        touch(it);
        return it->second.second;
    }

    // 插入或更新键值
    void put(const Key& key, const Value& value) {
        std::unique_lock lock(mutex_);
        auto it = map_.find(key);
        if (it != map_.end()) {
            it->second.second = value;
            touch(it);
            return;
        }

        if (list_.size() >= capacity_) {
            evict();
        }
        list_.push_front(key);
        map_[key] = {list_.begin(), value};
    }

    // 删除指定键
    void remove(const Key& key) {
        std::unique_lock lock(mutex_);
        auto it = map_.find(key);
        if (it != map_.end()) {
            list_.erase(it->second.first);
            map_.erase(it);
        }
    }

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

private:
    // 移动元素到链表头
    void touch(typename std::unordered_map<Key, std::pair<typename std::list<Key>::iterator, Value>>::iterator it) {
        list_.erase(it->second.first);
        list_.push_front(it->first);
        it->second.first = list_.begin();
    }

    // 淘汰尾部元素
    void evict() {
        const Key& key = list_.back();
        map_.erase(key);
        list_.pop_back();
    }

    size_t capacity_;
    std::list <Key> list_;
    std::unordered_map<Key, std::pair<typename std::list<Key>::iterator, Value>> map_;
    mutable std::shared_mutex mutex_;
};

4. 代码解读

双向链表 (std::list) 用于维护访问顺序。链表头是最近使用的，链表尾是最久未使用的。
哈希表 (std::unordered_map) 存储键到链表迭代器与对应值的映射，提供 O(1) 的查找。
共享锁 (std::shared_mutex) 允许多线程并发读取。读操作先尝试共享锁，若需要移动链表则临时升级为独占锁。
evict() 负责在容量已满时移除最久未使用的条目。

5. 性能评测与优化

维度	默认实现	可能优化
读操作锁竞争	共享锁降低冲突	使用 `try_lock_shared()` + `unlock()` 细粒度控制
写操作	独占锁	对于高并发写，可使用分段锁（striped lock）
内存占用	`list` + `unordered_map`	采用 `std::vector`+链表索引的自定义哈希表
Cache Miss	O(1)	预取策略：根据热点分析提前加载

6. 示例使用

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

    cache.put(1, "One");
    cache.put(2, "Two");
    cache.put(3, "Three");

    // 访问 1，更新顺序
    auto v = cache.get(1);
    if (v) std::cout << *v << '\n';

    // 插入新元素，导致 2 被淘汰
    cache.put(4, "Four");

    std::cout << "Size: " << cache.size() << '\n';
    if (!cache.get(2)) std::cout << "Key 2 evicted\n";
}

7. 结语

通过组合 unordered_map、list 与 shared_mutex，我们得到了一个既能满足 O(1) 访问速度，又能在多线程环境下保持线程安全的 LRU 缓存实现。若需进一步提升性能，可考虑使用分段锁或更轻量级的数据结构。祝你在项目中顺利使用此实现，提升系统缓存命中率与响应速度！

发表评论取消回复