LRU Cache 是 LeetCode Hot 100 里面一道非常经典的设计题。
这道题和前面的数组、链表、二叉树题不太一样，它不再只是让我们“遍历”或者“计算”，而是要求我们设计一个数据结构，并且同时满足下面两个条件：
-
get(key)：如果 key 存在，返回对应的值；否则返回-1 -
put(key, value)：插入或更新一个 key-value -
当缓存容量满了之后，需要淘汰最近最少使用的元素
-
并且这两个操作都要尽量高效
也就是说，这道题考察的核心不只是“会不会写代码”，而是你是否真正理解：
-
什么叫做“最近最少使用”
-
如何维护数据的访问顺序
-
如何在插入、删除、更新时保持缓存状态正确
LinkedHashMap + 手动维护访问顺序
这种写法没有自己手写双向链表，而是借助 Java 容器来实现缓存逻辑，代码量更少，思路也更清晰。
本文就结合这段代码，系统地讲一下这道题的解法。
一、题目描述
请你设计并实现一个满足 LRU（Least Recently Used，最近最少使用）缓存机制 的数据结构。
实现 LRUCache 类：
-
LRUCache(int capacity)以正整数作为容量初始化缓存 -
int get(int key)如果关键字存在于缓存中，则返回关键字的值，否则返回-1 -
void put(int key, int value)如果关键字已经存在，则变更其数据值；如果不存在，则插入该组关键字值。若插入操作导致关键字数量超过capacity，则应该逐出最久未使用的关键字
题目要求 get 和 put 尽量做到高效。
二、示例理解
假设缓存容量 capacity = 2。
操作过程如下：
put(1, 1) -> 缓存: {1=1}
put(2, 2) -> 缓存: {1=1, 2=2}
get(1) -> 返回 1，缓存顺序更新为 {2=2, 1=1}
put(3, 3) -> 容量已满，淘汰 2，缓存变为 {1=1, 3=3}
get(2) -> 返回 -1
put(4, 4) -> 淘汰 1，缓存变为 {3=3, 4=4}
get(1) -> 返回 -1
get(3) -> 返回 3
get(4) -> 返回 4
这里最关键的一点是：
谁“最久没有被访问”，谁就应该被优先删除。
所以这道题的重点不是单纯保存数据，而是要同时维护一个“使用顺序”。
三、核心思路
1. 为什么普通 HashMap 不够？
普通的 HashMap 确实可以做到：
-
根据 key 快速查询 value
-
根据 key 快速插入和删除
但是它有一个明显问题：
它不会记录元素的访问顺序。
而 LRU 的关键就在于：
你不仅要知道某个 key 在不在，还要知道它最近有没有被使用过。
所以仅仅有哈希表还不够，我们还需要一个结构来维护“先后顺序”。
2. 为什么这里用 LinkedHashMap？
LinkedHashMap 本质上是：
哈希表 + 链表
它既保留了哈希表的快速查找能力，又维护了元素的插入顺序。
在你这份代码里：
private final Map<Integer, Integer> cache = new LinkedHashMap<>();
这里的 cache 会按插入顺序保存数据。
于是我们可以这样理解：
-
链表头部的元素：最久没有使用
-
链表尾部的元素：最近刚刚使用
那么每次：
-
get(key)成功后，把这个元素删掉再重新插入到末尾 -
put(key, value)如果 key 已存在，也先删掉再重新插入到末尾 -
如果容量满了，就删除链表头部的元素
这样就实现了“最近使用的放后面，最久未使用的放前面”的效果。
四、代码分析
你的代码如下：
class LRUCache {
private final int capacity;
private final Map<Integer, Integer> cache = new LinkedHashMap<>(); // 内置 LRU
public LRUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
Integer value = cache.remove(key);
if (value != null) {
cache.put(key, value);
return value;
}
return -1;
}
public void put(int key, int value) {
if (cache.remove(key) != null) {
cache.put(key, value);
return;
}
if (cache.size() == capacity) {
Integer eldestKey = cache.keySet().iterator().next();
cache.remove(eldestKey);
}
cache.put(key, value);
}
}
下面逐段分析。
1. 成员变量
private final int capacity;
private final Map<Integer, Integer> cache = new LinkedHashMap<>();
这里定义了两个成员：
-
capacity：缓存最大容量 -
cache：真正保存缓存数据的容器
LinkedHashMap 能够维护元素顺序，所以很适合这道题。
2. 构造方法
public LRUCache(int capacity) {
this.capacity = capacity;
}
构造函数只做一件事：记录缓存容量。
3. get(int key)
public int get(int key) {
Integer value = cache.remove(key);
if (value != null) {
cache.put(key, value);
return value;
}
return -1;
}
这段代码看起来很短，但非常关键。
它做了两件事：
情况一：key 存在
-
先通过
remove(key)拿到对应的值 -
再执行
put(key, value)
这样做的本质是：
把这个元素从原来的位置删除，再重新插入到尾部。
这就意味着：
这个 key 刚刚被访问过，所以它应该变成“最近使用”的元素。
情况二：key 不存在
-
remove(key)返回null -
直接返回
-1
这表示缓存未命中。
4. put(int key, int value)
public void put(int key, int value) {
if (cache.remove(key) != null) {
cache.put(key, value);
return;
}
if (cache.size() == capacity) {
Integer eldestKey = cache.keySet().iterator().next();
cache.remove(eldestKey);
}
cache.put(key, value);
}
这部分需要分三种情况来看。
情况一：key 已存在
if (cache.remove(key) != null) {
cache.put(key, value);
return;
}
如果 key 已经存在：
-
先删掉旧位置上的 key
-
再把新的
(key, value)插入到末尾
这样既完成了值更新，也完成了“最近使用”的顺序更新。
情况二：key 不存在，并且缓存已满
if (cache.size() == capacity) {
Integer eldestKey = cache.keySet().iterator().next();
cache.remove(eldestKey);
}
这里的 cache.keySet().iterator().next() 取到的是：
当前插入顺序中的第一个 key
由于我们一直在手动维护“最近访问的元素放末尾”，那么第一个元素自然就是：
最近最少使用的元素
把它删掉，就完成了淘汰操作。
情况三：key 不存在，并且缓存未满
cache.put(key, value);
直接插入即可。
新插入的元素本身就属于最近使用，因此放在末尾正合适。
五、执行过程模拟
还是以容量 2 为例：
初始: {}
put(1,1)
=> {1=1}
put(2,2)
=> {1=1, 2=2}
get(1)
- 删除 1，再插入 1
=> {2=2, 1=1}
put(3,3)
- 容量已满
- 删除最前面的 2
- 插入 3
=> {1=1, 3=3}
get(1)
- 删除 1，再插入 1
=> {3=3, 1=1}
put(4,4)
- 删除最前面的 3
- 插入 4
=> {1=1, 4=4}
从这个过程可以看出来：
-
被访问过的 key 会被移动到末尾
-
最前面的 key 永远是最久未使用的
-
容量满时，删除第一个 key 就是正确的 LRU 行为
六、为什么这种写法成立？
这份代码的核心思想其实可以总结成一句话：
用
LinkedHashMap维护顺序，用“删除再插入”来模拟最近访问。
因为 LinkedHashMap 默认维护的是插入顺序，而不是访问顺序。
所以你这里并没有直接依赖它的“自动 LRU”机制，而是选择手动控制：
-
访问某个元素后，把它重新插到最后
-
更新某个元素后，也把它重新插到最后
-
删除第一个元素，就是删除最久未使用元素
这种做法逻辑非常直观，特别适合在刷题时快速实现。
七、复杂度分析
时间复杂度
-
get(key)：平均O(1) -
put(key, value)：平均O(1)
原因是 LinkedHashMap 底层依然基于哈希表，增删查操作平均都是常数时间。
空间复杂度
-
O(capacity)
最多只会存储 capacity 个键值对。
八、和标准“双向链表 + 哈希表”写法对比
这道题最标准的解法通常是：
哈希表 + 双向链表
这种写法的优点是：
-
完全手写 LRU 机制
-
更符合面试中对底层实现的考察
-
可以精确控制节点移动和删除
但缺点也很明显：
-
代码更长
-
细节更多
-
更容易出错
而你这份 LinkedHashMap 写法的优点是：
-
实现短小
-
逻辑清晰
-
非常适合刷题和理解 LRU 的核心思想
所以如果目标是：
-
快速通过题目
-
理解 LRU 的缓存淘汰逻辑
-
写出可读性较高的 Java 解法
那么这份代码已经非常不错。
九、一个补充点
严格来说，Java 的 LinkedHashMap 其实还支持通过构造参数开启 access-order（按访问顺序排序），再配合重写 removeEldestEntry，可以写出更“官方”的 LRU 实现。
但从刷题和理解角度来说，你现在这份代码更容易看懂，因为它把“最近使用”的维护过程完整地写出来了。
也就是说：
-
自动维护访问顺序的写法更简洁
-
手动删除再插入的写法更适合学习原理
十、完整代码
class LRUCache {
private final int capacity;
private final Map<Integer, Integer> cache = new LinkedHashMap<>(); // 内置顺序维护
public LRUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
Integer value = cache.remove(key);
if (value != null) {
cache.put(key, value);
return value;
}
return -1;
}
public void put(int key, int value) {
if (cache.remove(key) != null) {
cache.put(key, value);
return;
}
if (cache.size() == capacity) {
Integer eldestKey = cache.keySet().iterator().next();
cache.remove(eldestKey);
}
cache.put(key, value);
}
}
十一、总结
LRU Cache 这道题的难点，不在于某一个 API 怎么调用，而在于你是否理解：
缓存不仅要存数据，还要记录数据的使用顺序。
你这份代码的思路非常清楚：
-
用
LinkedHashMap保存 key-value -
用“删除再插入”的方式，把最近访问的元素移动到末尾
-
容量满时，删除最前面的元素
于是就完成了 LRU 的整个过程。
如果把这道题再提炼一下，本质上就是一句话：
谁最近被用过，就让谁靠后；谁最久没被用过，就优先淘汰谁。
这也是 LRU 缓存机制最核心的思想。
