LRU 缓存原理与实现（让你彻底搞懂什么是最近最少使用）

引言在计算机里缓存Cache的容量通常是有限的。当缓存满了再有新数据进来时就需要淘汰一些旧数据。那到底该淘汰谁呢这就是一个很现实的问题也是很多面试官喜欢问的问题。LRU的全称是Least Recently Used翻译过来就是最近最少使用。它的核心思想非常简单如果一个数据最近被访问过那么它将来被访问的概率也更高反过来很久都没被访问过的数据大概率以后也不怎么用可以优先淘汰。简单点说LRU 就像我们收拾书桌一样最久没碰的东西最应该先被清理掉。1. 生活中的例子假设你的书桌只能放 3 本书缓存容量是 3你先拿了《数据结构》来看。然后拿了《操作系统》。接着拿了《计算机网络》。这时候书桌满了。如果你接下来想看《算法》就必须先拿走一本。按照 LRU 的策略你会优先拿走最早看的那本《数据结构》因为它是“最近最少使用”的。注意这里的关键词是“最近”而不是“读过一次就不再需要”。比如你刚才还在翻《操作系统》那么即使《操作系统》比《数据结构》买得更早它依然会被视为“最近用过”暂时不会被淘汰。这也是 LRU 和其他简单淘汰策略比如先进先出最大的区别。2. LRU 需要支持的操作一个 LRU 缓存通常要高效支持两个核心操作get(key)查询这个 key 对应的值。如果 key 存在返回它的值并且把这个 key 标记为“最近使用过”。如果 key 不存在返回 -1。put(key, value)插入或更新一个键值对。如果 key 已经存在就更新它的值并标记为最近使用。如果 key 不存在就插入。如果插入后缓存满了就要把最久没使用的那个数据淘汰掉。3. 怎么实现才高效如果只用普通数组或链表查找和移动的效率会比较低。比如用数组找某个 key 要遍历最坏是 O(n)。用单链表虽然删除方便但要找到某个节点还是得从头扫描。最经典的高效实现是哈希表 双向链表。哈希表用来根据 key 快速找到对应的节点时间复杂度 O(1)。双向链表用来维护数据的使用顺序。链表头部表示最近使用的。链表尾部表示最久没使用的。操作逻辑如下每次 get 或 put 一个已存在的 key就把它移到链表头部。需要淘汰时直接删除链表尾部的节点。这样就能保证所有操作都是 O(1) 的。这也是 LRU 成为面试高频题的原因之一它把数据结构的组合运用考得很到位。4. 结构示意图哈希表负责“快速找到”双向链表负责“维护顺序”哈希表通过 key 快速定位到链表中的节点。双向链表Head ↔ [最近使用] ↔ [次近使用] ↔ ... ↔ [最久没使用] ↔ Tail。5. 核心操作总结操作具体动作get 存在返回值 把节点移到头部get 不存在返回 -1put 已存在更新值 移到头部put 不存在新建节点放到头部。如果满了先删尾部再插入6. 完整 C 代码实现哈希表 双向链表前面已经把原理讲清楚了下面直接给出完整可运行的 C 代码并配上详细注释。代码里用到了虚拟头尾节点这个设计能让新增和删除操作少写很多判断建议初学者仔细体会。6.1 完整代码实现#include iostream #include unordered_map using namespace std; // 双向链表节点 struct DLinkedNode { int key; int value; DLinkedNode* prev; DLinkedNode* next; DLinkedNode() : key(0), value(0), prev(nullptr), next(nullptr) {} DLinkedNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {} }; class LRUCache { private: unordered_mapint, DLinkedNode* cache; // 哈希表key - 链表节点指针 DLinkedNode* head; // 虚拟头节点 DLinkedNode* tail; // 虚拟尾节点 int capacity; // 缓存容量 int size; // 当前缓存大小 // 将节点添加到双向链表头部 void addToHead(DLinkedNode* node) { node-prev head; node-next head-next; head-next-prev node; head-next node; } // 删除链表中的某个节点 void removeNode(DLinkedNode* node) { node-prev-next node-next; node-next-prev node-prev; } // 将节点移动到头部先删再加 void moveToHead(DLinkedNode* node) { removeNode(node); addToHead(node); } // 删除尾部节点最久未使用并返回该节点方便清理 DLinkedNode* removeTail() { DLinkedNode* node tail-prev; removeNode(node); return node; } public: LRUCache(int capacity) { this-capacity capacity; this-size 0; // 使用虚拟头尾节点简化边界操作 head new DLinkedNode(); tail new DLinkedNode(); head-next tail; tail-prev head; } int get(int key) { if (cache.find(key) cache.end()) { return -1; // key 不存在 } // key 存在移动到头部表示最近使用 DLinkedNode* node cache[key]; moveToHead(node); return node-value; } void put(int key, int value) { if (cache.find(key) ! cache.end()) { // key 已存在更新值并移到头部 DLinkedNode* node cache[key]; node-value value; moveToHead(node); } else { // key 不存在创建新节点 DLinkedNode* node new DLinkedNode(key, value); cache[key] node; addToHead(node); size; // 如果超出容量淘汰尾部节点 if (size capacity) { DLinkedNode* removed removeTail(); cache.erase(removed-key); delete removed; size--; } } } // 析构函数释放内存 ~LRUCache() { DLinkedNode* cur head; while (cur) { DLinkedNode* next cur-next; delete cur; cur next; } } };6.2 测试代码int main() { LRUCache cache(2); // 容量为 2 cache.put(1, 1); // 缓存是 {11} cache.put(2, 2); // 缓存是 {11, 22} cout cache.get(1) endl; // 返回 1缓存变成 {22, 11} cache.put(3, 3); // 淘汰 key 2缓存是 {11, 33} cout cache.get(2) endl; // 返回 -1未找到 cache.put(4, 4); // 淘汰 key 1缓存是 {33, 44} cout cache.get(1) endl; // 返回 -1未找到 cout cache.get(3) endl; // 返回 3 cout cache.get(4) endl; // 返回 4 return 0; }预期输出1 -1 -1 3 46.3 代码要点说明虚拟头尾节点避免在增删头部或尾部节点时做大量判空代码更简洁也不容易写出空指针 bug。moveToHead每次访问或更新节点时调用它保证头部始终是最新使用的。removeTail容量满时调用淘汰最久未使用的节点。删除后别忘了同时清理哈希表中的映射并释放内存。初学者可以重点看这里为什么链表节点的字段里要同时保存key和value原因是在淘汰尾部节点时我们需要根据这个节点的 key 去哈希表里执行erase。如果节点里不存 key只存 value淘汰时就无法准确删除哈希表里的对应项。7. 为什么面试常考 LRU考查你对哈希表和链表的理解与组合使用。考查你对“时间复杂度”的敏感度能不能做到 O(1)。和操作系统、数据库缓存等实际场景联系紧密。另外LRU 还有一种更简洁但同样常考的实现方式就是直接使用 C 的list和unordered_map组合。不过手写双向链表能够更清楚地展示对指针和节点操作的理解建议面试前两种方式都准备一下。8. 总结LRU 的本质就是用双向链表维护“谁先谁后被使用”。用哈希表保证查找是 O(1)。淘汰时总是丢弃最久没被访问的数据。一句话记住哈希表负责快速查找链表负责维护顺序满了就淘汰链表尾部。理解了这个思想后面再看代码实现就会轻松很多。建议你先把 6.2 节的手动运行过程在纸上模拟一遍再自己动手写一遍完整代码这样对 LRU 的理解会非常扎实。