LeetCode 146 LRU缓存机制(哈希表 + 自定义双向链表 )

LeetCode 146 LRU缓存机制(哈希表 自定义双向链表 )题目链接https://leetcode.cn/problems/lru-cache/难度中等标签哈希表、双向链表、设计、LRU缓存 题目描述设计并实现满足LRU最近最少使用缓存约束的数据结构LRUCacheLRUCache(int capacity)给定容量初始化缓存int get(int key)key存在返回value不存在返回-1void put(int key, int value)key存在更新value并标记为最近使用key不存在插入键值对若超出容量淘汰最久未使用的数据。要求get、put平均时间复杂度O(1) 前置说明面试重点实现LRU存在两种方案语言内置封装容器JavaLinkedHashMapPythonOrderedDict代码极简⚠️面试不推荐直接使用面试官通常要求手写双向链表。手写哈希表 双向链表标准解法本文重点讲解该方案。方案0LinkedHashMap 偷懒实现笔试快速写面试慎用classLRUCacheextendsLinkedHashMapInteger,Integer{privateintcapacity;publicLRUCache(intcapacity){// accessOrdertrue开启访问顺序模式LRU核心super(capacity,0.75F,true);this.capacitycapacity;}publicintget(intkey){returnsuper.getOrDefault(key,-1);}publicvoidput(intkey,intvalue){super.put(key,value);}// 超过容量时自动删除最久未访问节点OverrideprotectedbooleanremoveEldestEntry(Map.EntryInteger,Integereldest){returnsize()capacity;}}关键点accessOrdertrue开启访问顺序每次访问节点自动移至链表尾部。方法一哈希表 手写双向链表【标准面试解法】核心思路双向链表维护数据访问时序链表头部存放最近使用节点链表尾部存放最久未使用节点使用伪头head、伪尾tail哨兵节点避免大量空指针边界判断。HashMap 哈希表key - 链表节点O(1)时间定位节点。为什么两种结构必须搭配使用HashMap查找快但无法维护时序双向链表可以有序增删但无法快速查找key。操作逻辑梳理1. get(key)key不存在返回-1key存在通过哈希表定位节点将节点移动到链表头部返回value。2. put(key, value)key不存在新建节点 → 加入哈希表 → 添加到链表头部若总大小 容量删除链表尾节点同步删除哈希表对应key。key存在更新节点value → 将节点移动到链表头部。辅助函数说明addToHead(node)将节点插入伪头之后链表真正头部removeNode(node)从链表中移除指定节点moveToHead(node)removeNodeaddToHeadremoveTail()移除伪尾的前驱节点最久未使用节点返回该节点用于清理哈希表Java完整代码实现publicclassLRUCache{// 双向链表节点classDLinkedNode{intkey;intvalue;DLinkedNodeprev;DLinkedNodenext;publicDLinkedNode(){}publicDLinkedNode(int_key,int_value){key_key;value_value;}}// 哈希表key映射链表节点privateMapInteger,DLinkedNodecachenewHashMap();privateintsize;// 当前元素数量privateintcapacity;// 缓存容量上限privateDLinkedNodehead,tail;// 哨兵伪头、伪尾publicLRUCache(intcapacity){this.size0;this.capacitycapacity;// 初始化哨兵节点headnewDLinkedNode();tailnewDLinkedNode();head.nexttail;tail.prevhead;}publicintget(intkey){DLinkedNodenodecache.get(key);if(nodenull){return-1;}// 访问后移至链表头部moveToHead(node);returnnode.value;}publicvoidput(intkey,intvalue){DLinkedNodenodecache.get(key);if(nodenull){// key不存在新建节点DLinkedNodenewNodenewDLinkedNode(key,value);cache.put(key,newNode);addToHead(newNode);size;// 超出容量淘汰尾部节点if(sizecapacity){DLinkedNodetailNoderemoveTail();cache.remove(tailNode.key);size--;}}else{// key存在更新值并移到头部node.valuevalue;moveToHead(node);}}// 将节点添加到链表头部head之后privatevoidaddToHead(DLinkedNodenode){node.prevhead;node.nexthead.next;head.next.prevnode;head.nextnode;}// 删除链表中指定节点privatevoidremoveNode(DLinkedNodenode){node.prev.nextnode.next;node.next.prevnode.prev;}// 将节点移动到头部privatevoidmoveToHead(DLinkedNodenode){removeNode(node);addToHead(node);}// 删除尾部节点返回被删除节点privateDLinkedNoderemoveTail(){DLinkedNoderestail.prev;removeNode(res);returnres;}}⚠️ 高频坑点面试提问重点节点为什么要同时保存key和value删除尾部节点时只能拿到链表节点需要节点内的key去同步删除HashMap中的记录。哨兵伪头、伪尾作用不需要区分节点是否是头/尾节点统一增删逻辑消除大量null判断。moveToHead不能直接插入必须先删再加如果节点本身就在链表中直接插入会造成链表环。双向链表必须维护双向指针prev、next单向链表无法O(1)删除任意节点。 复杂度分析时间复杂度get、put均为 O(1)HashMap查找O(1)双向链表增删节点O(1)。空间复杂度O(capacity)哈希表与双向链表最多存储capacity个有效节点。