实现 LRU 缓存(并发安全)
面试考点
LRU 缓存是面试中出现频率最高的数据结构题之一。面试官考察你是否理解 LRU 的淘汰策略、哈希表 + 双向链表实现 O(1) 访问和淘汰、以及如何用读写锁或互斥锁实现线程安全的并发访问。
核心概念
LRU(Least Recently Used)缓存的策略是:当缓存满时,淘汰最近最少使用的条目。数据结构选择:unordered_map 提供 O(1) 的键查找,std::list 的 splice 操作提供 O(1) 的顺序调整。链表头部是最近使用的,尾部是最久未使用的。每次访问或插入都把条目移到头部,淘汰时删除尾部。
基本示例
#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) 原理,以及讨论并发策略的权衡。