一、 题目简单描述设计并实现一个满足LRU (最近最少使用) 缓存约束的数据结构。它需要支持以下两个核心操作且两个操作的平均时间复杂度都必须为 O (1)get(int key)获取数据put(int key, int value)写入 / 更新数据二、 LRU 原理详解什么是 LRULRU(Least Rencently Used) - 最近最少使用是一种常见的内存淘汰算法核心思想如果数据最近被访问过那么说明这个 数据在将来被访问的概率也很高删除思想当缓存满了的时候删除最久没有被访问的数据数据结构选型要实现get和put的时间复杂度为O(1)1.哈希表关键字和数据、访问速度O(1)。其实可以使用unordered_map作为哈希表因为节点数据每次被访问都会将被访问数据的节点移动到链表的头节点而且每个键值key唯一对应一个节点所以该程序中的哈希表是无序的而且unordered_map的底层逻辑本身就是哈希表2.双向链表插入和删除移动结点都是O(1)本篇将会手动实现结构设计双向链表中1.头节点代表最新被访问的数据2.尾节点代表最久没有访问的节点缓存满的时候从尾节点删除哈希表中哈希键值对应链表中的节点快速定位元素位置。核心操作逻辑get(key)获取该键值对应的数据如果不存在返回-1如果键值存在将该节点移动到链表的头部标记为最近使用过返回键对应的数据put(keyvalue):如果关键字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实现。#includeiostream #includeunordered_map #includeassert.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_mapint, 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-nextnode; node-next-prev node;///旧的头节点的prevnode } //从链表中移除任意节点(不释放内存) 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.核心工具函数1addToHead(DLinekNode*node);//在链表的头节点虚拟节点之后插入新访问的节点 void addToHead(DLinkedNode* node) { assert(node ! nullptr); node-next head-next; node-prev head; node-prev-next node;//head-nextnode; node-next-prev node;///旧的头节点的prevnode }其实这个代码就是双向链表中的带头节点的头插的代码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;2removeDLinekNode(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)的要求了。3moveToHead(DLinkedNode*node);//移动节点到链表的头部 void moveToHead(DLinkedNode* node) { assert(node ! nullptr); removeDLinkedNode(node); addToHead(node); }这个代码的作用就是将被访问节点移动到链表的头部去标记为已访问的新数据节点将被访问节点移动到链表的头部去需要两个步骤1.将该节点从链表中移除但是不释放内存2.拿着这个节点的地址直接将其添加到链表的头部去表示该节点是新访问的数据4deleteTail(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不存在则返回-12.如果键值key存在则将key对应的数据替换为value所以首先判断哈希表中是否存在key键值通过unordered_map::find函数如果函数返回值retunordered_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)情况 1Key 已存在哈希查找cache.find(key)耗时 O(1)。更新值与移动节点修改value耗时 O(1)moveToHead耗时 O(1)。总耗时O(1)。情况 2Key 不存在需要插入新节点插入哈希表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::pairconst int, DLinkedNode*。每个键值对包含一个int类型的 key4 字节和一个指针类型的 value64位系统下为 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); // 访问 key1该节点变为最近使用 cout get(1) lru.get(1) endl; // 预期输出1 // 测试2插入第三个元素超出容量淘汰最久未使用的 key2 cout \n2. 插入 (3,3)触发淘汰------------------------- endl; lru.put(3, 3); cout get(2) lru.get(2) endl; // 预期输出-1已被淘汰 // 测试3访问 key3再插入新元素淘汰 key1 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. 重复写入 key4更新值为 44 endl; lru.put(4, 44); cout get(4) lru.get(4) endl; // 预期输出44 // 测试5查询不存在的 key cout \n5. 查询不存在的 key99 endl; cout get(99) lru.get(99) endl; // 预期输出-1 cout \n--------------------- 测试完毕---------------------------- endl; return 0; }测试结果九、结语本文完整实现了基于哈希表 双向链表的经典 LRU 缓存从数据结构选型、核心方法封装到内存管理、边界校验逐一落地。LRU 作为面试高频考点不仅要能写出代码更要理解背后的设计思想利用双向链表维护访问时序借助哈希表实现 O (1) 级别的查找效率二者互补达成最优性能。实际开发中Redis、浏览器缓存等场景都大量运用了 LRU 淘汰策略。吃透这份基础实现再去学习进阶的 LFU、分段 LRU 等优化方案也会轻松很多。如果文中有疏漏或者你有更好的优化思路欢迎在评论区交流探讨。
面试常考题目：LRU缓存机制超详细解析(附可运行源码)
一、 题目简单描述设计并实现一个满足LRU (最近最少使用) 缓存约束的数据结构。它需要支持以下两个核心操作且两个操作的平均时间复杂度都必须为 O (1)get(int key)获取数据put(int key, int value)写入 / 更新数据二、 LRU 原理详解什么是 LRULRU(Least Rencently Used) - 最近最少使用是一种常见的内存淘汰算法核心思想如果数据最近被访问过那么说明这个 数据在将来被访问的概率也很高删除思想当缓存满了的时候删除最久没有被访问的数据数据结构选型要实现get和put的时间复杂度为O(1)1.哈希表关键字和数据、访问速度O(1)。其实可以使用unordered_map作为哈希表因为节点数据每次被访问都会将被访问数据的节点移动到链表的头节点而且每个键值key唯一对应一个节点所以该程序中的哈希表是无序的而且unordered_map的底层逻辑本身就是哈希表2.双向链表插入和删除移动结点都是O(1)本篇将会手动实现结构设计双向链表中1.头节点代表最新被访问的数据2.尾节点代表最久没有访问的节点缓存满的时候从尾节点删除哈希表中哈希键值对应链表中的节点快速定位元素位置。核心操作逻辑get(key)获取该键值对应的数据如果不存在返回-1如果键值存在将该节点移动到链表的头部标记为最近使用过返回键对应的数据put(keyvalue):如果关键字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实现。#includeiostream #includeunordered_map #includeassert.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_mapint, 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-nextnode; node-next-prev node;///旧的头节点的prevnode } //从链表中移除任意节点(不释放内存) 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.核心工具函数1addToHead(DLinekNode*node);//在链表的头节点虚拟节点之后插入新访问的节点 void addToHead(DLinkedNode* node) { assert(node ! nullptr); node-next head-next; node-prev head; node-prev-next node;//head-nextnode; node-next-prev node;///旧的头节点的prevnode }其实这个代码就是双向链表中的带头节点的头插的代码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;2removeDLinekNode(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)的要求了。3moveToHead(DLinkedNode*node);//移动节点到链表的头部 void moveToHead(DLinkedNode* node) { assert(node ! nullptr); removeDLinkedNode(node); addToHead(node); }这个代码的作用就是将被访问节点移动到链表的头部去标记为已访问的新数据节点将被访问节点移动到链表的头部去需要两个步骤1.将该节点从链表中移除但是不释放内存2.拿着这个节点的地址直接将其添加到链表的头部去表示该节点是新访问的数据4deleteTail(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不存在则返回-12.如果键值key存在则将key对应的数据替换为value所以首先判断哈希表中是否存在key键值通过unordered_map::find函数如果函数返回值retunordered_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)情况 1Key 已存在哈希查找cache.find(key)耗时 O(1)。更新值与移动节点修改value耗时 O(1)moveToHead耗时 O(1)。总耗时O(1)。情况 2Key 不存在需要插入新节点插入哈希表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::pairconst int, DLinkedNode*。每个键值对包含一个int类型的 key4 字节和一个指针类型的 value64位系统下为 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); // 访问 key1该节点变为最近使用 cout get(1) lru.get(1) endl; // 预期输出1 // 测试2插入第三个元素超出容量淘汰最久未使用的 key2 cout \n2. 插入 (3,3)触发淘汰------------------------- endl; lru.put(3, 3); cout get(2) lru.get(2) endl; // 预期输出-1已被淘汰 // 测试3访问 key3再插入新元素淘汰 key1 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. 重复写入 key4更新值为 44 endl; lru.put(4, 44); cout get(4) lru.get(4) endl; // 预期输出44 // 测试5查询不存在的 key cout \n5. 查询不存在的 key99 endl; cout get(99) lru.get(99) endl; // 预期输出-1 cout \n--------------------- 测试完毕---------------------------- endl; return 0; }测试结果九、结语本文完整实现了基于哈希表 双向链表的经典 LRU 缓存从数据结构选型、核心方法封装到内存管理、边界校验逐一落地。LRU 作为面试高频考点不仅要能写出代码更要理解背后的设计思想利用双向链表维护访问时序借助哈希表实现 O (1) 级别的查找效率二者互补达成最优性能。实际开发中Redis、浏览器缓存等场景都大量运用了 LRU 淘汰策略。吃透这份基础实现再去学习进阶的 LFU、分段 LRU 等优化方案也会轻松很多。如果文中有疏漏或者你有更好的优化思路欢迎在评论区交流探讨。
