字节面试高频原题，哈希表+双向链表经典综合题，同时对应计算机组成原理的LRU页面置换策略。

146. LRU缓存

题目描述：

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。

实现 LRUCache 类：

1. LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU缓存

2. int get(int key) 如果关键字 key存在于缓存中，则返回关键字的值，否则返回 -1

3. 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里面为什么存key；put更新旧key也要moveToHead；淘汰时链表和map两边都要删除。

感谢您的关注，本人会持续更新的力扣解法