一篇文章让你不怕LRU算法

LRU 是什么LRU最近最少使用淘汰策略。当缓存满了需要淘汰数据时优先删除“最长时间没被访问过”的那一项。典型场景页面缓存数据库热点数据缓存Redis 本地缓存策略CDN 边缘节点缓存为什么不能只用数组或链表很多人第一反应是用数组存一下访问时调整位置。问题在于查找某个 keyO(n)删除某个 keyO(n)插入头部O(n)面试官一般会要求 get 和 put 都是 O(1)。所以需要组合结构哈希表unordered_mapO(1) 找到节点双向链表O(1) 删除节点、移动节点到头部、删除尾节点核心设计思路维护一个双向链表链表头表示“最近使用”链表尾表示“最久未使用”。操作规则get(key)key 不存在返回 -1key 存在把该节点移动到链表头再返回 valueput(key, value)key 已存在更新 value并移动到链表头key 不存在容量未满直接插入头部容量已满删除尾节点再插入新节点到头部C 版本#include iostream #include unordered_map using namespace std; class LRUCache { private: struct Node { int key, value; Node* prev; Node* next; Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {} }; int cap; unordered_mapint, Node* mp; Node* head; // 虚拟头 Node* tail; // 虚拟尾 void removeNode(Node* node) { node-prev-next node-next; node-next-prev node-prev; } void addToHead(Node* node) { node-next head-next; node-prev head; head-next-prev node; head-next node; } void moveToHead(Node* node) { removeNode(node); addToHead(node); } Node* removeTail() { Node* node tail-prev; removeNode(node); return node; } public: LRUCache(int capacity) : cap(capacity) { head new Node(0, 0); tail new Node(0, 0); head-next tail; tail-prev head; } int get(int key) { if (!mp.count(key)) return -1; Node* node mp[key]; moveToHead(node); return node-value; } void put(int key, int value) { if (mp.count(key)) { Node* node mp[key]; node-value value; moveToHead(node); } else { Node* node new Node(key, value); mp[key] node; addToHead(node); if ((int)mp.size() cap) { Node* removed removeTail(); mp.erase(removed-key); delete removed; } } } ~LRUCache() { Node* cur head; while (cur) { Node* nxt cur-next; delete cur; cur nxt; } } };复杂度分析get哈希查找 链表移动O(1)put哈希查找/插入 链表操作O(1)空间复杂度哈希表 链表O(capacity)面试里容易被问到的细节为什么必须是双向链表单向链表删除任意节点需要前驱不是 O(1)。为什么要用虚拟头尾节点统一边界处理避免链表空/单节点时写很多 if。put 已存在 key 时为什么也要移动到头因为“被更新”本身就是一次访问应该算最近使用。如果要线程安全怎么做可以加互斥锁或者做分段锁高并发下会涉及锁粒度和一致性策略。一个实际工程提醒LRU 在真实项目里不一定总是最优。如果存在“扫描型访问”例如一次性顺序读大量数据LRU 可能把热点挤掉。这时会考虑 LFU、ARC 等策略或者给业务做分层缓存。总结LRU 的重点不是“记住模板”而是能否讲清楚这三件事为什么是哈希表 双向链表为什么能保证 O(1)淘汰逻辑和边界情况怎么处理面试中把这三点讲明白基本就稳了。