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 不存在	返回 -1
put 已存在	更新值 + 移到头部
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_map<int, 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); // 缓存是 {1=1} cache.put(2, 2); // 缓存是 {1=1, 2=2} cout << cache.get(1) << endl; // 返回 1，缓存变成 {2=2, 1=1} cache.put(3, 3); // 淘汰 key 2，缓存是 {1=1, 3=3} cout << cache.get(2) << endl; // 返回 -1（未找到） cache.put(4, 4); // 淘汰 key 1，缓存是 {3=3, 4=4} cout << cache.get(1) << endl; // 返回 -1（未找到） cout << cache.get(3) << endl; // 返回 3 cout << cache.get(4) << endl; // 返回 4 return 0; }

预期输出：