力扣——146.LRU缓存详解

前言前文已详细讲解LRU缓存底层原理、淘汰规则与设计思想零基础入门可跳转上篇文章LRU缓存机制题目整体设计与思路LRU 缓存机制可以通过哈希表辅以双向链表实现我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。双向链表按照被使用的顺序存储了这些键值对靠近头部的键值对是最近使用的而靠近尾部的键值对是最久未使用的。哈希表即为普通的哈希映射HashMap通过缓存数据的键映射到其在双向链表中的位置。这样以来我们首先使用哈希表进行定位找出缓存项在双向链表中的位置随后将其移动到双向链表的头部即可在 O(1) 的时间内完成 get 或者 put 操作。具体的方法如下对于 get 操作首先判断 key 是否存在如果 key 不存在则返回 −1如果 key 存在则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置并将其移动到双向链表的头部最后返回该节点的值。对于 put 操作首先判断 key 是否存在如果 key 不存在使用 key 和 value 创建一个新的节点在双向链表的头部添加该节点并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量如果超出容量则删除双向链表的尾部节点并删除哈希表中对应的项如果 key 存在则与 get 操作类似先通过哈希表定位再将对应的节点的值更新为 value并将该节点移到双向链表的头部。上述各项操作中访问哈希表的时间复杂度为 O(1)在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为 O(1)。而将一个节点移到双向链表的头部可以分成「删除该节点」和「在双向链表的头部添加节点」两步操作都可以在 O(1) 时间内完成。在双向链表的实现中使用一个伪头部dummy head和伪尾部dummy tail标记界限这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。双向链表结构体设计与分析// 自定义双向链表节点structDLinkedNode{intkey,value;// 存储键、值DLinkedNode*prev;// 前驱指针指向前一个节点DLinkedNode*next;// 后继指针指向后一个节点// 无参构造初始化空节点所有成员置空DLinkedNode():key(0),value(0),prev(nullptr),next(nullptr){}// 有参构造直接传入key、value快速创建数据节点DLinkedNode(int_key,int_value):key(_key),value(_value),prev(nullptr),next(nullptr){}};节点必须存储key后续淘汰尾部节点时需要拿到 key 去哈希表中删除对应映射只存value会导致映射无法清除构造函数统一将指针初始化为空避免野指针报错LRU缓存类私有成员变量设计与分析classLRUCache{private:unordered_mapint,DLinkedNode*cache;// 核心哈希映射key - 链表节点DLinkedNode*head;// 虚拟头哨兵节点DLinkedNode*tail;// 虚拟尾哨兵节点intsize;// 当前缓存实际存放元素数量intcapacity;// 缓存最大容纳容量cache 实现快速查找绕过链表遍历满足O(1)查找head/tail 纯虚拟节点不存储业务数据仅用来统一链表操作size/capacity 实时统计数量判断是否触发缓存淘汰机制构造函数初始化逻辑public:// 初始化LRU缓存传入最大容量LRUCache(int_capacity):capacity(_capacity),size(0){// 创建伪头部、伪尾部两个哨兵节点headnewDLinkedNode();tailnewDLinkedNode();// 空链表初始化头节点与尾节点互相绑定head-nexttail;tail-prevhead;}执行逻辑初始化最大容量 capacity 初始元素个数 size 置0开辟内存创建虚拟头尾节点初始状态链表结构 head ---- tail 无任何业务数据哨兵节点初始化完成后后续所有增删逻辑无需判断链表是否为空四大核心辅助函数所有 get 、 put 业务逻辑全部依赖这四个函数吃透指针操作即可掌握全部逻辑1. addToHead 节点插入链表头部// 将指定节点插入到链表最前端最近使用位置voidaddToHead(DLinkedNode*node){node-prevhead;// 新节点前驱指向虚拟头节点node-nexthead-next;// 新节点后继指向原本头部第一个真实节点head-next-prevnode;// 原头部节点的前驱指向当前新节点head-nextnode;// 虚拟头节点后继改为指向新节点}新写入数据、刷新访问数据统一放到链表头部。2.removeNode 摘除链表中的任意节点// 把某个节点从链表中单独摘除不删除内存voidremoveNode(DLinkedNode*node){// 前节点直接连接后节点跳过当前nodenode-prev-nextnode-next;// 后节点直接连接前节点跳过当前nodenode-next-prevnode-prev;}只断开节点前后指针关系不释放内存为移动节点做铺垫。3.moveToHead 将节点移动到头部// 将已存在的节点移动至头部刷新为最近使用voidmoveToHead(DLinkedNode*node){removeNode(node);// 第一步先从原位置摘除节点addToHead(node);// 第二步重新插入到链表头部}先摘后插是LRU更新访问顺序的标准写法。4.removeTail删除尾部最久未使用节点// 删除链表末尾节点最久未使用数据并返回该节点DLinkedNode*removeTail(){// 虚拟尾节点的前驱就是最后一个真实业务节点DLinkedNode*nodetail-prev;removeNode(node);returnnode;}专门用于缓存容量溢出时执行淘汰策略。get 查询方法实现逻辑// 根据key查询缓存数据intget(intkey){// 哈希表中不存在该key直接返回-1if(!cache.count(key)){return-1;}// key存在通过哈希表O(1)定位节点DLinkedNode*nodecache[key];// 访问即代表最近使用移动到链表头部moveToHead(node);// 返回节点存储的值returnnode-value;}逻辑流程哈希快速判重不存在直接返回 -1存在则定位节点访问必刷新位置符合LRU最近使用规则返回对应数值put存入/更新方法实现逻辑voidput(intkey,intvalue){// 分支1当前key不存在执行新增缓存逻辑if(!cache.count(key)){// 1. 创建全新数据节点DLinkedNode*nodenewDLinkedNode(key,value);// 2. 存入哈希表建立映射cache[key]node;// 3. 新数据默认为最近使用插入头部addToHead(node);// 4. 缓存元素数量1size;// 5. 判断是否超出最大容量超出则淘汰最久未使用数据if(sizecapacity){// 摘除尾部淘汰节点DLinkedNode*removedremoveTail();// 同步删除哈希表中对应key映射cache.erase(removed-key);// 手动释放内存杜绝内存泄漏deleteremoved;// 元素数量-1--size;}}// 分支2当前key已存在执行更新逻辑else{// 1. 哈希表定位旧节点DLinkedNode*nodecache[key];// 2. 覆盖更新存储的值node-valuevalue;// 3. 更新访问位置移至头部moveToHead(node);}}两大分支逻辑新增数据创建节点 → 绑定哈希映射 → 头部插入 → 数量自增超容量自动删除尾部节点同步清哈希、释放内存更新旧数据直接修改value值 → 刷新访问位置即可不改变缓存数量整体代码structDLinkedNode{intkey,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){}};classLRUCache{private:unordered_mapint,DLinkedNode*cache;DLinkedNode*head;DLinkedNode*tail;intsize;intcapacity;public:LRUCache(int_capacity):capacity(_capacity),size(0){headnewDLinkedNode();tailnewDLinkedNode();head-nexttail;tail-prevhead;}intget(intkey){if(!cache.count(key)){return-1;}DLinkedNode*nodecache[key];moveToHead(node);returnnode-value;}voidput(intkey,intvalue){if(!cache.count(key)){DLinkedNode*nodenewDLinkedNode(key,value);cache[key]node;addToHead(node);size;if(sizecapacity){DLinkedNode*removedremoveTail();cache.erase(removed-key);deleteremoved;--size;}}else{DLinkedNode*nodecache[key];node-valuevalue;moveToHead(node);}}voidaddToHead(DLinkedNode*node){node-prevhead;node-nexthead-next;head-next-prevnode;head-nextnode;}voidremoveNode(DLinkedNode*node){node-prev-nextnode-next;node-next-prevnode-prev;}voidmoveToHead(DLinkedNode*node){removeNode(node);addToHead(node);}DLinkedNode*removeTail(){DLinkedNode*nodetail-prev;removeNode(node);returnnode;}};