)
一、 题目简单描述
设计并实现一个满足LRU (最近最少使用) 缓存约束的数据结构。
它需要支持以下两个核心操作，且两个操作的平均时间复杂度都必须为 O (1)：
get(int key)：获取数据put(int key, int value)：写入 / 更新数据
二、 LRU 原理详解
什么是 LRU？
LRU=(Least Rencently Used) -> （最近最少使用），是一种常见的内存淘汰算法
核心思想：如果数据最近被访问过，那么说明这个 数据在将来被访问的概率也很高
删除思想：当缓存满了的时候，删除最久没有被访问的数据
数据结构选型：
要实现get和put的时间复杂度为O(1)
1.哈希表：（关键字和数据）、访问速度O(1)。
（其实可以使用unordered_map作为哈希表，因为节点数据每次被访问都会将被访问数据的节点移动到链表的头节点，而且每个键值key唯一对应一个节点，所以该程序中的哈希表是无序的，而且unordered_map的底层逻辑本身就是哈希表）
2.双向链表：插入和删除移动结点，都是O(1)，本篇将会手动实现
结构设计：
双向链表中：
1.头节点代表最新被访问的数据
2.尾节点代表最久没有访问的节点，缓存满的时候从尾节点删除
哈希表中：
哈希键值对应链表中的节点，快速定位元素位置。
核心操作逻辑：
get(key)：获取该键值对应的数据
如果不存在：返回-1
如果键值存在：将该节点移动到链表的头部（标记为最近使用过），返回键对应的数据
put(key，value):
如果关键字key存在，将关键字对应的值替换为value，并将该节点移动到链表头部
如果关键字不存在，则新建节点，直接将这个节点插入链表头部，哈希表中添加key键值，如果超出容量，则将尾部的节点，并删除哈希表中对应的键值key，删除后在进行插入
三、 算法思路简单模拟
初始化：容量 = 3，空缓存：此时链表：[ ]
put (1,1) → 链表：[1]
put (2,2) → 链表：[2, 1]
put (3,3) → 链表：[3, 2, 1]
get (1) → 命中，移到头部 → 链表：[1, 3, 2]
put (4,4) → 缓存满，删除尾部 2 → 链表：[4, 1, 3]
四、 完整源代码
双向链表手动实现，哈希表将用unordered_map实现。
#include<iostream> #include<unordered_map> #include<assert.h> using namespace std; //using ElemType = int;//给数据类型重命名 struct DLinkedNode { int key; int value; DLinkedNode* prev; DLinkedNode* next; //无参构造用于创建虚拟头尾节点 DLinkedNode() :key(0), value(0), prev(nullptr), next(nullptr) {} DLinkedNode(int _key, int _value) :key(_key), value(_value), prev(nullptr), next(nullptr) {} }; class LRUCache { private: std::unordered_map<int, DLinkedNode*> cache;//哈希表 key->节点指针 DLinkedNode* head;//头节点 DLinkedNode* tail;//尾节点 int capacity;//最大容量 int size;//当前元素个数 //在链表的头节点（虚拟节点）之后插入新节点 void addToHead(DLinkedNode* node) { assert(node != nullptr); node->next = head->next; node->prev = head; node->prev->next = node;//head->next=node; node->next->prev = node;///旧的头节点的prev=node } //从链表中移除任意节点(不释放内存) void removeDLinkedNode(DLinkedNode* node) { assert(node != nullptr); node->prev->next = node->next; node->next->prev = node->prev; } //移动节点到链表的头部 void moveToHead(DLinkedNode* node) { assert(node != nullptr); removeDLinkedNode(node); addToHead(node); } //删除尾节点并返回该节点指针 DLinkedNode* deleteTail() { DLinkedNode* pret = tail->prev;//tail是虚拟节点，需要删除的是tail的前驱节点 removeDLinkedNode(pret);//并不会释放内存，在数据超限的时候，删除哈希中key之后再通过该函数的返回值释放内存 return pret; } public: LRUCache(int _capacity) :capacity(_capacity), size(0) { head = new DLinkedNode(); tail = new DLinkedNode(); head->next = tail; tail->prev = head; } ~LRUCache() { DLinkedNode* cur = head->next; while (cur != tail) { DLinkedNode* temp = cur->next; delete cur; cur = temp; } //删除头尾虚拟节点 delete head; delete tail; } int get(int key) { auto ret = cache.find(key); if (ret == cache.end()) { return -1; } DLinkedNode* node = ret->second; moveToHead(node); return node->value; } void put(int key, int value) { //1.如果key存在，替换value的值 auto ret = cache.find(key); if (ret != cache.end()) { ret->second->value = value; moveToHead(ret->second); return; } //2.如果不存在 //2.1先将元素插入进来，插入结束后判断是否空间超限制 DLinkedNode* newnode = new DLinkedNode(key, value); cache[key] = newnode;//将新节点存放到哈希表中去 addToHead(newnode); size++;//节点个数增加//缓存中的数据个数增加 //2.2如果超限制，则删除，如果没有，不做任何处理 if (size > capacity) { DLinkedNode* temp = deleteTail(); cache.erase(temp->key);//按照key删除键值对 delete temp;//此时真正释放尾节点的内存 size--; } return; } };五、 代码逐行解析
1.节点类设计：
struct DLinkedNode { int key; int value; DLinkedNode* prev; DLinkedNode* next; //无参构造用于创建虚拟头尾节点 DLinkedNode() :key(0), value(0), prev(nullptr), next(nullptr) {} DLinkedNode(int _key, int _value) :key(_key), value(_value), prev(nullptr), next(nullptr) {} };上面已经分析过我们需要用到双向链表来实现。
所以链表节点需要包含节点的前驱和后继。
以及需要存储的数据。
还有一个key值。
为什么还需要一个key呢？
在淘汰最久未使用的数据的时候，我们不仅要删除链表中的节点，还必须在哈希表中同步删除对应的键值对，否则会导致内存泄漏或数据不一致。
哈希表删除元素必须依赖
key（例如cache.erase(key)）因为此时，我们手里只有链表尾部节点的指针。如果节点内部不存储
key，我们就无法知道这个节点对应的key是什么，从而无法在哈希表中执行删除操作。
2.虚拟头尾节点：
核心作用是消除边界条件，极大地简化代码逻辑
如果没有虚拟节点，当你在链表中插入或删除元素时，必须时刻警惕操作的是否是真正的头节点或尾节点：
插入时：如果链表为空，或者要在头部插入，你需要特殊处理头指针的指向。
删除时：如果删除的是头节点或尾节点，你需要更新外部的头尾指针，并且还要判断删除后链表是否变空。
有了虚拟节点后，真正的数据节点永远被夹在
head和tail之间。无论链表是否为空，head->next和tail->prev始终存在（最差也是互相指向）。因此，所有的插入和删除操作都可以统一处理。
在单链表中有带头节点的链表和不带头节点的链表之分，其头节点的作用和这里相同。
3.核心工具函数：
（1）addToHead(DLinekNode*node);
//在链表的头节点（虚拟节点）之后插入新访问的节点 void addToHead(DLinkedNode* node) { assert(node != nullptr); node->next = head->next; node->prev = head; node->prev->next = node;//head->next=node; node->next->prev = node;///旧的头节点的prev=node }其实这个代码就是双向链表中的带头节点的头插的代码：
1.新节点node的后继指向虚拟头节点的后继
2.新节点的前驱指向的就是虚拟头节点
3.此时的head节点的next域存储的节点的地址和node->next中存储的相同，
但是此时的head->next应该是node
需要更新head->next：让head->next指向新的后继node;
4.并且此时的node->next节点的prev域存储的节点的地址任然是head，但是其新前驱是node
需要更新node->next->prev让其指向新的后继前驱node;
（2）removeDLinekNode(DLinekNode*node);
//从链表中移除任意节点(不释放内存) void removeDLinkedNode(DLinkedNode* node) { assert(node != nullptr); node->prev->next = node->next; node->next->prev = node->prev; }这个移除链表中的任意节点的逻辑：
让被删除节点node的前驱的后继指针域指向被删除节点node的后继
并让被删除节点node的后继的前驱指针域指向被删除节点node的前驱
可以注意到我们在移除节点的时候并未delete，原因有两个：
1.如果这个节点是被访问的数据节点，这个时候，我们需要及那个这个节点放到链表的头部，如果delete之后，再插入的时候就需要重新再申请节点，删除再申请两个操作抵消，相当于不释放，直接将这个节点移动过去即可
2.如果是要删除的尾节点，直接在这一步中直接delete掉，在链表中删除了节点，其节点中存储的key的值就被销毁了，没有了key的值，就无法快速的同步在哈希表中删除该节点对应的键值对，必须去逐个遍历，这就不符合题目删除时间复杂度O(1)的要求了。
（3）moveToHead(DLinkedNode*node);
//移动节点到链表的头部 void moveToHead(DLinkedNode* node) { assert(node != nullptr); removeDLinkedNode(node); addToHead(node); }这个代码的作用就是将被访问节点移动到链表的头部去，标记为已访问的新数据节点
将被访问节点移动到链表的头部去，需要两个步骤：
1.将该节点从链表中移除，但是不释放内存
2.拿着这个节点的地址直接将其添加到链表的头部去，表示该节点是新访问的数据
（4）deleteTail(DLinkedNode*node);
//删除尾节点并返回该节点指针 DLinkedNode* deleteTail() { DLinkedNode* pret = tail->prev;//tail是虚拟节点，需要删除的是tail的前驱节点 removeDLinkedNode(pret);//并不会释放内存，在数据超限的时候，删除哈希中key之后再通过该函数的返回值释放内存 return pret; }这个函数的作用是将最久未被访问的数据节点从缓存中删除（也就是从链表中删除）
这里需要强调以下：我们删除的尾节点是虚拟尾节点的前驱节点
先找到需要删除的尾节点：tail->prev
然后调用删除链表中任意节点的函数，将tail->prev作为参数传进去，这里也只是移除尾节点，其真正删除并不在这里，最后还需要将tail->prev作为返回值返回，后续要使用该节点中的key值同步删除哈希表中的该节点对应的键值对。
4.get 方法解析：
int get(int key) { auto ret = cache.find(key); if (ret == cache.end()) { return -1; } DLinkedNode* node = ret->second; moveToHead(node); return node->value; }get函数的作用：
1.如果键值key不存在，则返回-1
2.如果键值key存在，则将key对应的数据替换为value
所以：
首先，判断哈希表中是否存在key键值，通过unordered_map::find函数
如果函数返回值ret==unordered_map::end()则说明该键值不存在，直接返回-1
相反，则说明存在，则ret->second就能得到键值key中存储的节点的地址，并返回该节点中的数值，不要忘记将新访问的节点挪到链表的头部。
5.put 方法解析：
void put(int key, int value) { auto ret = cache.find(key); if (ret != cache.end()) { ret->second->value = value; moveToHead(ret->second); return; } DLinkedNode* newnode = new DLinkedNode(key, value); cache[key] = newnode;//将新节点存放到哈希表中去 addToHead(newnode); size++;//节点个数增加 if (size > capacity) { DLinkedNode* temp = deleteTail(); cache.erase(temp->key);//按照key删除键值对 delete temp;//此时真正释放尾节点的内存 size--; } return; }1.如果key存在，替换value的值
2.如果不存在
2.1先将元素插入进来，插入结束后判断是否空间超限制插入节点，在链表头部插入直接调用addToHead(newnode)，除此之外还要将该节点映射到哈希表中去，通过cache[key]=newnode插入。
2.2判断是否超出限制，如果超限制，则移除尾部节点，如果没有，不做任何处理
移除尾部最久未被访问的节点，直接调用已经封装好的deleteTail()，并定义一个临时节点temp接受该函数的返回值，是被移除的节点的地址，并通过该节点得到移除节点的key值，通过这个key值同步删除哈希表中对应的键值对，等到这一步执行结束以后，就可以真正删除尾节点delete temp;
删除之后链表中的节点的个数要-1
六、 复杂度分析
时间复杂度：分析get和put操作为何是 O(1)。
1.get操作的时间复杂度分析：O(1)
哈希查找：
auto ret = cache.find(key);。unordered_map的底层是哈希表，查找一个键的平均时间复杂度是 O(1)。链表移动：如果找到了对应的节点，需要调用
moveToHead(node)将其移到链表头部。这个操作包含两步：先调用removeDLinkedNode（修改前后节点的指针，O(1)），再调用addToHead（修改虚拟头节点及原首节点的指针，O(1)）。结论：O(1) + O(1) =O(1)。
2.put操作的时间复杂度分析：O(1)
put操作分为两种情况，但无论哪种情况，整体耗时都是 O(1)情况 1：Key 已存在
哈希查找：
cache.find(key)耗时 O(1)。更新值与移动节点：修改
value耗时 O(1)，moveToHead耗时 O(1)。总耗时：O(1)。
情况 2：Key 不存在（需要插入新节点）
插入哈希表：
cache[key] = newnode;。哈希表的插入平均时间复杂度为 O(1)。链表头部插入：
addToHead(newnode);。修改指针耗时 O(1)。容量检查与淘汰（最坏情况）：当
size > capacity时，触发淘汰机制。
deleteTail()：删除尾部节点，仅需修改指针，耗时 O(1)。
cache.erase(temp->key)：由于节点内部冗余存储了key，哈希表删除操作无需遍历， 直接定位删除，耗时 O(1)。总耗时：O(1) + O(1) + O(1) = O(1)。
(注：严格来说，哈希表的 O(1) 是“平均时间复杂度”。在极端情况下，如果哈希冲突极其严重，退化为链表，单次操作可能达到 O(N)。但在工程实际和算法面试中，我们默认哈希表操作为 O(1)。)
空间复杂度：
空间复杂度主要取决于缓存中实际存储的元素数量。假设当前缓存中的有效元素个数为N（即N <= capacity）。
1. 哈希表的空间占用：O(N)
哈希表中存储了 N 个键值对（
std::pair<const int, DLinkedNode*>）。每个键值对包含一个
int类型的 key（4 字节）和一个指针类型的 value（64位系统下为 8 字节）。考虑到哈希表底层的负载因子（Load Factor）和哈希桶（Bucket）数组的开销，哈希表实际占用的内存略大于 N，但宏观上依然是O(N)。
2. 双向链表的空间占用：O(N)
普通节点：链表中间存储了 N 个真实的业务节点（
DLinkedNode）。每个节点包含key(4B)、value(4B)、prev指针 (8B)、next指针 (8B)，共计 24 字节（未考虑内存对齐）。这部分占用O(N)。虚拟头尾节点：
head和tail是两个固定的哨兵节点，不存储真实业务数据，仅占用常数级别的内存O(1)。
3. 结论
哈希表占用 O(N) + 链表节点占用 O(N) + 虚拟节点占用 O(1) =O(N)。
七、 面试高频考点
1. 为什么选择双向链表而不是单向链表或数组？
这是为了满足
get和put操作均为 O(1) 的时间复杂度要求。排除数组：数组在中间插入或删除元素时，需要移动后续所有元素，时间复杂度为 O(N)。
排除单向链表：虽然插入和删除节点本身是 O(1)，但单向链表无法直接获取前驱节点。当需要将某个节点移动到头部，或删除尾部节点时，必须从头遍历寻找前驱，导致时间复杂度退化为 O(N)。
双向链表的优势：双向链表的节点同时拥有前驱（
prev）和后继（next）指针。在已知节点的情况下，可以在 O(1) 时间内完成任意节点的摘除、移动和尾部淘汰操作。
2. 为什么双向链表的节点中需要冗余存储key？
为了在缓存淘汰时，能够以 O(1) 的时间复杂度同步删除哈希表中的对应记录。
淘汰机制的联动：当缓存达到容量上限触发淘汰时，系统会直接删除双向链表尾部的节点。
哈希表的删除依赖：删除哈希表中的元素必须依赖
key（如cache.erase(key)）。如果链表节点只存value，在拿到被淘汰的节点时，将无从得知其对应的key是什么。避免性能退化：如果不存
key，就只能遍历整个哈希表去比对节点指针地址，这会导致淘汰操作的时间复杂度变为 O(N)，打破了 LRU 缓存 O(1) 的设计初衷。
3. 虚拟头节点（Dummy Head）和虚拟尾节点的作用是什么？
消除边界条件判断，极大地简化代码逻辑并提升健壮性。
统一操作逻辑：如果没有虚拟节点，在链表头部插入或在尾部删除时，必须额外判断链表是否为空、头尾指针是否为
nullptr。引入虚拟节点后，真正的业务节点永远被夹在head和tail之间。避免空指针异常：所有的节点（包括真正的头尾节点）都有前驱和后继。无论是
addToHead还是removeTail，都可以用同一套代码统一处理，无需进行任何特殊的边界条件判断，减少了代码出错的概率。
八、 测试用例
测试代码：
int main() { cout << "------------------------ 开始测试 --------------------------" << endl; int n = 2; // 设置缓存容量为 n LRUCache lru(n); cout << "缓存容量：" << n << " ------------------------------------- " << endl; // 测试1：插入两个元素，未满，无淘汰 cout << "\n1. 插入 (1,1)、(2,2)----------------------------" << endl; lru.put(1, 1); lru.put(2, 2); // 访问 key=1，该节点变为最近使用 cout << "get(1) = " << lru.get(1) << endl; // 预期输出：1 // 测试2：插入第三个元素，超出容量，淘汰最久未使用的 key=2 cout << "\n2. 插入 (3,3)，触发淘汰-------------------------" << endl; lru.put(3, 3); cout << "get(2) = " << lru.get(2) << endl; // 预期输出：-1（已被淘汰） // 测试3：访问 key=3，再插入新元素，淘汰 key=1 cout << "\n3. 访问(3) 后插入(4,4)---------------------------" << endl; cout << "get(3) = " << lru.get(3) << endl; // 预期输出：3 lru.put(4, 4); cout << "get(1) = " << lru.get(1) << endl; // 预期输出：-1（已被淘汰） cout << "get(3) = " << lru.get(3) << endl; // 预期输出：3 cout << "get(4) = " << lru.get(4) << endl; // 预期输出：4 // 测试4：重复 key 写入，更新值并移动到头部 cout << "\n4. 重复写入 key=4，更新值为 44" << endl; lru.put(4, 44); cout << "get(4) = " << lru.get(4) << endl; // 预期输出：44 // 测试5：查询不存在的 key cout << "\n5. 查询不存在的 key=99" << endl; cout << "get(99) = " << lru.get(99) << endl; // 预期输出：-1 cout << "\n--------------------- 测试完毕----------------------------" << endl; return 0; }测试结果：
九、结语
本文完整实现了基于哈希表 + 双向链表的经典 LRU 缓存，从数据结构选型、核心方法封装到内存管理、边界校验逐一落地。LRU 作为面试高频考点，不仅要能写出代码，更要理解背后的设计思想：利用双向链表维护访问时序，借助哈希表实现 O (1) 级别的查找效率，二者互补达成最优性能。
实际开发中，Redis、浏览器缓存等场景都大量运用了 LRU 淘汰策略。吃透这份基础实现，再去学习进阶的 LFU、分段 LRU 等优化方案，也会轻松很多。如果文中有疏漏或者你有更好的优化思路，欢迎在评论区交流探讨。
