字节面试高频原题哈希表双向链表经典综合题同时对应计算机组成原理的LRU页面置换策略。146. LRU缓存题目描述请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。实现 LRUCache 类1. LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU缓存2. int get(int key) 如果关键字 key存在于缓存中则返回关键字的值否则返回 -13. void put(int key, int value) 如果key已经存在则变更其值如果不存在则插入。当缓存达到上限时它应该在写入新数据之前删除最久未使用的数据。要求 get 和 put 操作的时间复杂度必须是 O(1)。示例思路分析LRU全称最近最少使用缓存。简单说缓存空间满了的时候优先删掉很久没访问过的数据。为了做到查找和移动节点都是O(1)我们用HashMap加上双向链表一起实现。为什么要用这两个呢原因如下❌使用数组删除中间元素时后面的元素要整体向前移动时间复杂度O(n)。❌使用单向链表只知道下一个节点不知道前驱节点如果要删除中间节点必须从头遍历时间复杂度O(n)。❌ 只用哈希表查找O(1)但是无法记录访问顺序找不到最久未使用元素。❌ 只用双向链表可以维护访问顺序但是根据key查找节点需要遍历时间复杂度O(n)。✅ 哈希表 双向链表组合方案1. 双向链表维护访问顺序链表头部存放最近使用节点链表尾部存放最久未使用节点缓存满了的时候直接删除尾哨兵指向的节点设置虚拟头、虚拟尾哨兵节点不用更新每个节点都去判断是否在链表表头或者链表表尾。2. HashMap保存key到链表节点的对应关系实现O(1)快速找到链表节点。3. 每次 get 访问、 put 更新都要把对应节点移动到链表头部缓存满的时候删除尾部节点同时哈希表也要同步删除该key。重点Node节点内部需要保存key。淘汰尾部节点的时候只能拿到节点对象需要节点内部的key去删除HashMap中的记录。Java完整实现使用算法笔记1. 封装思想 Node 使用静态内部类只属于LRUCache内部零件外部不能随意修改节点指针实现信息隐藏、高内聚低耦合。2. 哨兵节点虚拟头、虚拟尾避免大量判空逻辑简化双向链表增删代码。3. 易错点淘汰节点时链表删除节点之后HashMap必须同步删除对应的key否则会产生脏数据。4. 对应关联知识点LRU缓存对应计组的LRU页面置换算法缓存内存capacity代表内存最多存放页面数量满了淘汰很久没有访问的页面。5. 时间复杂度get、put操作全部O(1)哈希表查找O(1)双向链表增删移动节点O(1)。总结LRU缓存是面试超级高频的数据结构设计题核心就是哈希表负责查找双向链表维护时序。需要牢牢记住几个坑Node里面为什么存keyput更新旧key也要moveToHead淘汰时链表和map两边都要删除。感谢您的关注本人会持续更新的力扣解法