LRU Cache：面试必考设计题

LRU Cache：面试必考设计题

1. 直观类比：手机后台应用列表

打开手机的多任务界面——你最近打开的 App 排在前面，很久没用的沉到后面。当后台 App 太多（容量满了），系统杀掉排在最末尾的那个。

这就是 LRU（Least Recently Used）淘汰策略：最近用过的留下，最久没用的滚蛋。

// 类比代码：想象一个只能装 4 个 App 的后台// 顺序：最近使用 -> 最久未使用std::vector<std::string>recentApps={"微信","浏览器","相机","设置"};// 容量=4，新开"小红书" → 淘汰"设置"

2. 数据结构选择：为什么两个一起上？

只用一个数据结构搞不定，逐个分析：

哈希表给 O(1) 查找，双向链表给 O(1) 插入/删除。组合起来就是 LRU Cache 的标准答案。

3. 核心操作

get(key)： 不存在 → return -1 存在 → 把节点移到链表头部，返回 value put(key, value)： 已存在 → 更新 value，移到头部 不存在 → 插入头部 检查容量，超了则删尾部

4. C++ 实现一：std::list + unordered_map

利用 STL 的list和splice，面试快速写。

#include<list>#include<unordered_map>#include<cassert>classLRUCache{public:LRUCache(intcapacity):cap_(capacity){}intget(intkey){autoit=map_.find(key);if(it==map_.end())return-1;// splice 把选中节点移到链表开头，O(1)list_.splice(list_.begin(),list_,it->second);returnit->second->second;}voidput(intkey,intvalue){autoit=map_.find(key);if(it!=map_.end()){it->second->second=value;list_.splice(list_.begin(),list_,it->second);return;}if(list_.size()==cap_){// 淘汰尾部（最久未使用）intold_key=list_.back().first;map_.erase(old_key);list_.pop_back();}list_.emplace_front(key,value);map_[key]=list_.begin();}private:intcap_;std::list<std::pair<int,int>>list_;std::unordered_map<int,std::list<std::pair<int,int>>::iterator>map_;};

5. C++ 实现二：手写双向链表（面试更推荐）

面试官想看你对链表指针的掌控。自己实现DLinkedNode，左右指针自己维护。

#include<unordered_map>structDLinkedNode{intkey,value;DLinkedNode*prev,*next;DLinkedNode():key(0),value(0),prev(nullptr),next(nullptr){}DLinkedNode(intk,intv):key(k),value(v),prev(nullptr),next(nullptr){}};classLRUCache{public:LRUCache(intcapacity):cap_(capacity),size_(0){// 头尾哑节点，避免边界判断head_=newDLinkedNode();tail_=newDLinkedNode();head_->next=tail_;tail_->prev=head_;}intget(intkey){autoit=cache_.find(key);if(it==cache_.end())return-1;moveToHead(it->second);returnit->second->value;}voidput(intkey,intvalue){autoit=cache_.find(key);if(it!=cache_.end()){it->second->value=value;moveToHead(it->second);return;}auto*node=newDLinkedNode(key,value);cache_[key]=node;addToHead(node);++size_;if(size_>cap_){auto*removed=removeTail();cache_.erase(removed->key);deleteremoved;--size_;}}private:voidaddToHead(DLinkedNode*node){node->prev=head_;node->next=head_->next;head_->next->prev=node;head_->next=node;}voidremoveNode(DLinkedNode*node){node->prev->next=node->next;node->next->prev=node->prev;}voidmoveToHead(DLinkedNode*node){removeNode(node);addToHead(node);}DLinkedNode*removeTail(){auto*node=tail_->prev;removeNode(node);returnnode;}intcap_,size_;DLinkedNode*head_,*tail_;std::unordered_map<int,DLinkedNode*>cache_;};

手写优势：面试官可以直接问你指针操作细节，而 STL 版少了很多考察点。

6. 扩展：LFU 与 LRU 对比

LFU（Least Frequently Used）—— 淘汰访问次数最少的。对缓存命中率的理论设计更优，但实现昂贵。

// LFU 核心思路：每个频率一个双向链表// unordered_map<int, int> keyToFreq;// unordered_map<int, list<int>> freqToList; // 频率 → 该频率的 key 列表// unordered_map<int, list<int>::iterator> keyToIter;// 淘汰时从最低频的链表尾部取

7. 复杂度表

哈希冲突理论上让最坏退化为 O(n)，但面试中直接说 O(1) 即可。

8. 面试题

题 1：手写 LRU Cache（LeetCode 146）

直接抄上面的实现二，手撕 5 分钟写完。注意细节：

• 哑节点省判空
• 记得删旧 key 的哈希记录
• get和put都要做"移到头部"操作

完整自测代码：

#include<iostream>intmain(){LRUCachecache(2);cache.put(1,1);cache.put(2,2);std::cout<<cache.get(1)<<"\n";// 1cache.put(3,3);// 淘汰 key=2std::cout<<cache.get(2)<<"\n";// -1cache.put(4,4);// 淘汰 key=1std::cout<<cache.get(1)<<"\n";// -1std::cout<<cache.get(3)<<"\n";// 3std::cout<<cache.get(4)<<"\n";// 4return0;}

题 2：LFU Cache 设计思路（LeetCode 460）

说出三个核心容器即可：

// 伪代码框架structLFUCache{intmin_freq;unordered_map<int,int>key_to_val;unordered_map<int,int>key_to_freq;unordered_map<int,list<int>>freq_to_keys;// 每个频率一条双向链unordered_map<int,list<int>::iterator>key_to_pos;intget(intkey){if(!key_to_val.count(key))return-1;// 频率+1，从旧频率列表移到新频率列表// 更新 min_freq}voidput(intkey,intvalue){// 存在：更新值，频率+1// 不存在：插入 key，频率=1// 超容量则从 min_freq 链表尾部淘汰}};

题 3：LRU 在 Redis 中的应用

Redis 不是精确 LRU，而是近似 LRU：

# redis.conf maxmemory-policy allkeys-lru

• Redis 从所有 key 中采样maxmemory-samples个（默认 5）
• 淘汰其中最久未用的那个
• 为什么近似：精确 LRU 需要维护双向链表，Redis 单线程扛不住链表全部操作的内存和 CPU 开销

// 近似 LRU 伪逻辑// 1. 随机取 N 个 key// 2. 比较它们的 idle time（最后一次访问距今）// 3. 淘汰 idle time 最大的

题 4：多级缓存架构

面试追加题——考系统设计意识：

L1：CPU Cache (KB 级, 纳秒) L2：本地内存 Cache（如 Guava Cache, GB 级, 微秒） L3：分布式 Cache（如 Redis, 内存有限, 毫秒级） L4：DB（磁盘, 慢）

每一层都有自己的 LRU（或近似 LRU）。项目中常组合使用：本地 Cache 兜高频 + Redis 兜中等频率 + DB 兜底。DNS 系统也常用多级 LRU 缓存域名解析结果。

总结：LRU Cache 考的是"拿两个最基础的数据结构拼成一个复合结构"的能力。面试时先讲类比让面试官懂你的思路，再动手写——手写双向链表版比 STL 版多拿 5 分。