手写LRU缓存：哈希表+双向链表核心实现与面试考点

“请手写一个LRU缓存。”

这道题我这些年见过太多次了，面试官问、笔试考、论坛里讨论，几乎每个学数据结构的人迟早都会碰到它。LRU（Least Recently Used，最近最少使用）已经不只是面试题里的常客，它是计算机系统里真实存在的底层机制——操作系统页面置换、数据库缓存命中、Redis的内存淘汰、浏览器的回退页面，背后都有它的影子。这篇是这个系列的第二篇，我就把这个高频数据结构核心知识点彻底拆开：算法原理、执行步骤、代码实现、边界场景、踩坑记录，一次性讲透。

一句话概括LRU的思想：当空间不够时，优先淘汰最近最久没被访问过的数据。换句话说，如果一个数据在最近一段时间内被频繁访问，那么它在未来一段时间内被访问的概率也更高——这是时间局部性原理的直观应用。真正落地到代码上，需要回答两个问题：怎么做到O(1)的访问速度？怎么做到O(1)的淘汰删除？这篇博文就来逐一解开，适合正在准备面试的开发者，也适合刚学完链表和哈希表、想看它们怎么组合实战的学生。

1. 从朴素到高效：为什么最后是哈希表加双向链表

1.1 LRU到底在解决什么问题：先从手机后台说起

想象一下你正在用手机刷应用。微信聊完切到抖音，抖音看完又切回微信，再点开支付宝付个款。手机系统后台保留着这些应用的状态，但内存是有限的，不可能把所有用过的应用都留在后台。这时候系统会怎么做？它会把最长时间没被重新打开的那个应用关掉，保留最近用过的那些。这个策略，就是LRU。

把这个场景抽象成数据结构模型：有一块容量固定的存储空间，不断有key进来，每个key对应一份数据。当容量满了，再有新数据要进来，就必须把某份旧数据踢出去——踢谁？踢最久没被访问的那个。同时，每次get、每次更新，都应该把该数据的"最近使用时间"刷新。这就是LRU的全部逻辑：读、写、淘汰，三个操作。

如果只让你用理论实现，很多人第一反应是用数组加时间戳：每个数据记录一个lastAccessTime，每次访问O(1)更新，淘汰时遍历找最小的时间戳O(n)。这个方法能跑，但淘汰是O(n)，数据量一大就扛不住。更致命的问题是，如果数据命中的概率很高，每一次get都要维护时间戳，后续淘汰还要全表扫描，性能很难看。

所以LRU的核心难点不是"思想"，而是：读要快、写要快、淘汰还要快。三个都快，才是这题真正的考点。

1.2 为什么选双向链表：单向链表缺了什么

先拆解需求。要O(1)地找到一个key，自然会想到哈希表——这是哈希表最擅长的场景。哈希表里存key和对应的节点引用，get时能立刻定位。

但淘汰的时候，哈希表帮不上忙。哈希表是无序的，它不知道谁是最久没被访问的。所以必须有一个"有序结构"来记录访问的时间顺序。这个有序结构里，头部是最新访问的，尾部是最久未访问的，淘汰时直接删尾部——这就是链表。

链表选单向还是双向？这是关键抉择。

单向链表能O(1)地插入头部，但删除任意一个节点时，得知道它的前驱节点是谁。问题来了：通过哈希表拿到的是节点本身，单向链表的节点只有next指针，没有prev指针，你没法O(1)找到它的前驱，只能从头遍历。这一遍历，删除就变成O(n)了。

双向链表完美解决这个问题——每个节点不仅有next，还有prev。删除任意节点时，直接执行node.prev.next = node.next和node.next.prev = node.prev，不需要遍历，O(1)完成。这就是为什么所有LRU的标准实现都是哈希表加双向链表：哈希表负责O(1)查找，双向链表负责O(1)删除和O(1)移动。

用一张对比表看清各方案的复杂度：

这个复杂度推导过程，本身就是面试官想听到的思维路径。很多人背结论说"LRU用哈希加链表"，但说不出为什么不能用单向链表，原因就在这里——不是背出来的，是算出来的。

2. 图解LRU：核心数据结构与节点移动全过程

2.1 Node节点设计：每个元素需要记住什么

动手写代码前，先把数据结构的形态在脑子里画清楚。

每条数据的载体是一个双向链表节点Node，它需要保存四个信息：

• key：哈希表的键，也是淘汰时从哈希表移除的依据
• value：真正的数据值
• prev：指向前一个节点
• next：指向后一个节点

整个LRU结构里有两个关键部件：一个HashMap<Integer, Node>，负责从key直接定位节点；一条双向链表，负责维护访问顺序。

这里有个工程上面的细节：链表的头尾不能是null。最省心的做法是设置两个"哨兵节点"——伪头节点head和伪尾节点tail。它们不存任何真实数据，只是作为边界存在。真正的数据节点都在head和tail之间。

结构长这样：

head <-> nodeA <-> nodeB <-> nodeC <-> tail

head的下一个节点是最新访问的，tail的上一个节点是最久未访问的。为什么要用哨兵节点？想象一下如果没有它们，当链表为空时，插入第一个节点要判断head == null，删除最后一个节点时也要处理tail == null，代码里到处是空指针判断。有了哨兵节点，链表的插入和删除逻辑永远是一致的，不需要分支判断，代码简洁且不易出错。

2.2 get操作全过程：命中、移动、返回

执行get(k)时，三个步骤：

1. 用哈希表查k，如果不存在直接返回-1
2. 如果存在，拿到对应的Node节点
3. 把这个节点移动到链表头部，然后返回它的value

为什么get也要移动节点？因为"访问"本身刷新了数据的最近使用时间。刚才还在尾部（最久未访问），现在被读了，它就变成了最近被使用的数据，必须提到最前面。

举例说明。初始状态：

map: {A:nodeA, B:nodeB, C:nodeC} list: head <-> A <-> B <-> C <-> tail

执行get("B")后，B被访问，移动到头部：

list: head <-> B <-> A <-> C <-> tail

步骤拆开看就是两步：先把B从链表中摘下来，让A直接接上C；再把B插到head的后面。摘和插都是O(1)的指针操作。

2.3 put操作三个分支：新增、覆盖、淘汰

执行put(k, v)时，情况分三种：

情况一：k已存在。直接更新该节点的value，并把它移动到链表头部。注意，这里不需要新建节点，也不需要走淘汰逻辑。

情况二：k不存在，且链表未满。新建一个node(k, v)，把它插入链表头部，同时在map里注册k到node的映射。

情况三：k不存在，但链表已满。先删除链表尾部的节点——它是最久未访问的数据。拿到尾部节点的key，从map里把它移除，释放空间，再执行情况二的操作。

这里插一句容易踩坑的地方：淘汰的节点必须从map中移除。很多人写代码时只操作了链表，忘记同步map，结果map里残留着被淘汰节点的引用，导致这个key还能被get到，逻辑就乱了。链表和哈希表是一体两面的，任何一侧的修改都必须同步到另一侧。

用图说明淘汰：

capacity = 3 list: head <-> A <-> B <-> C <-> tail 执行put("D") 第1步：插入D到头部，list变成 head <-> D <-> A <-> B <-> C <-> tail 第2步：发现size=4 > capacity=3，删除尾部C list变成 head <-> D <-> A <-> B <-> tail map中同步移除C

完美体现了LRU的淘汰规则：最久没被访问的C先出局，哪怕它曾经被访问过无数次，只要最近一段时间没碰它，就会被淘汰。

3. 手写实现：完整Java代码与逐段拆解

3.1 直接能跑的完整代码

把上面的分析落到代码上。用Java实现一版，结构清晰、注释完整，可以直接复制运行测试。

import java.util.HashMap; import java.util.Map; public class LRUCache { // 双向链表节点定义 private static class Node { int key; int value; Node prev; Node next; Node(int key, int value) { this.key = key; this.value = value; } } private final int capacity; private final Map<Integer, Node> map = new HashMap<>(); private final Node head = new Node(0, 0); // 伪头节点 private final Node tail = new Node(0, 0); // 伪尾节点 private int size; public LRUCache(int capacity) { this.capacity = capacity; head.next = tail; tail.prev = head; } public int get(int key) { Node node = map.get(key); if (node == null) { return -1; } moveToHead(node); return node.value; } public void put(int key, int value) { Node node = map.get(key); if (node != null) { // 已存在：更新值并移动到头部 node.value = value; moveToHead(node); return; } // 不存在：新建节点 Node newNode = new Node(key, value); map.put(key, newNode); addToHead(newNode); size++; if (size > capacity) { // 淘汰尾部最久未使用的节点 Node removed = removeTail(); map.remove(removed.key); size--; } } // 将节点插入到链表头部（伪头节点之后） private void addToHead(Node node) { node.next = head.next; node.prev = head; head.next.prev = node; head.next = node; } // 将节点从链表中摘除 private void removeNode(Node node) { node.prev.next = node.next; node.next.prev = node.prev; } // 将节点移动到头部 = 先摘除再插入 private void moveToHead(Node node) { removeNode(node); addToHead(node); } // 删除并返回尾部节点（伪尾节点之前那个） private Node removeTail() { Node node = tail.prev; removeNode(node); return node; } }

这段代码就是LRU的经典实现，LeetCode第146题的官方解法，也是各种书籍、教程里出现频率最高的版本。运行一下：

LRUCache cache = new LRUCache(2); cache.put(1, 1); cache.put(2, 2); System.out.println(cache.get(1)); // 返回 1 cache.put(3, 3); // 淘汰 key=2 System.out.println(cache.get(2)); // 返回 -1 System.out.println(cache.get(3)); // 返回 3

3.2 最容易写错的addToHead：四行指针的顺序问题

如果你自己手写过这段代码，大概率在addToHead这个函数上卡过壳。就四行代码，但顺序错了，整个链表就乱了。

node.next = head.next; // 新节点的next指向原第一个真实节点 node.prev = head; // 新节点的prev指向伪头节点 head.next.prev = node; // 原第一个真实节点的prev指向新节点 head.next = node; // 伪头节点的next指向新节点

关键点是：必须先让新节点和原第一个真实节点建立联系，再去修改head.next。如果反过来，先执行head.next = node，那么原第一个真实节点就"失联"了——head的next已经变成node，你再也拿不到原第一个节点，后面两行就没法进行了。

可以这样记：先处理新节点自己的两个指针（next和prev都得指对），再处理它相邻两个节点指向它的指针（先让后一个节点指过来，再让前一个节点指过去）。这个顺序是链表插入的通用法则，不只是LRU里要用，任何双向链表插入操作都遵循同样的规律。

3.3 removeNode和moveToHead：为什么不需要判空

removeNode执行的是标准的双向链表摘除：

node.prev.next = node.next; node.next.prev = node.prev;

两行代码，没有判空。为什么不判空？因为哨兵节点的存在，链表里任何一个真实数据节点的prev和next都一定不为null——链表的边界是伪头和伪尾，它们永远不会被当作真实节点删除，也不会被移出链表。

moveToHead就是removeNode加addToHead的组合：先从老位置摘下来，再插到头部。这两步必须连续执行，中间不能有其他操作插入。所以我把它们封装成一个方法，从调用方来看语义很清晰——"这个节点刚刚被访问了，把它挪到最新的位置"。

4. 面试官不会直接告诉你的三个隐藏考点

4.1 考点一：为什么get和put都是O(1)

这道题之所以经典，是因为它把三种数据结构的优势组合了起来：哈希表O(1)查找、双向链表O(1)插入删除、哨兵节点避免空指针分支。三者缺一不可。

面试时回答这个问题的标准表述：

• get：哈希表查key O(1)，移动节点到头部由两个O(1)指针操作组成，整体O(1)
• put：哈希表查key O(1)，新增或更新节点O(1)，容量满时删除尾部节点O(1)，同步map操作O(1)，整体O(1)
• 空间复杂度：O(capacity)，哈希表存capacity个映射，链表存capacity个节点

注意别说什么"均摊O(1)"——这个场景里所有操作都是严格的O(1)，不需要分摊。

4.2 考点二：map里存Node还是Node里存map

有同学会问：为什么哈希表是Map<Integer, Node>，而不是把Node作为key直接存？

你可以试想一下，如果定义Map<Node, Integer>或者干脆把Node当key，会有什么问题。Node是一个自定义类，如果你没有重写equals和hashCode方法，那么哈希表比较节点时比较的是内存地址。每次新建一个Node，它的内存地址都不一样，即使key值相同，查找时也匹配不上，哈希表形同虚设。所以这里的设计原则是：哈希表的key一定要是业务意义上的key，value才是存储的载体节点。

还有一个隐藏细节：淘汰时为什么能通过removed.key从map中移除？因为Node节点里保存了key字段。如果Node里不存key，只存value，淘汰的时候你拿到了Node，却不知道它在map里对应的key是什么，就没法同步清理map——那整个缓存就垮了。所以Node里的key字段不是冗余，它是链表和map之间的桥梁。

4.3 考点三：手写实现没考虑并发，但你要知道答案

上面这份代码不是线程安全的。两个线程同时调用put，可能导致链表被破坏、size计数不准确、map和链表数据不一致。面试时经常会追问："如果并发访问怎么办？"

最直接的答案是给get和put加上synchronized关键字。这属于粗粒度锁，实现简单，但并发性能很差，所有操作串行化。实际生产环境如果追求性能，会用读写锁——读操作不互斥，写操作互斥，因为get只读不改（且get有修改链表的操作，这个要看你对"读"的定义了），或者直接使用JDK的ConcurrentHashMap配合额外的同步控制。

另一个思路是使用LinkedHashMap的线程安全包装，这个下一节详细说。更进一步的方案，在Java生态里可以直接用Caffeine、Guava Cache这些本地缓存库，它们内部实现了LRU/LFU等多种淘汰策略，还支持过期时间、刷新机制，比手写强得多。但面试时，把这些方案说出来就够了，不需要真去实现一个并发LRU。

5. LinkedHashMap三行代码实现，以及生产环境的真实选择

5.1 三行代码背后发生了什么

JDK里的LinkedHashMap本身就是一个"哈希表+双向链表"的组合，它默认按插入顺序维护链表。但它提供了一个构造参数accessOrder，当设为true时，链表顺序会变成按访问顺序维护——每次get到一个key，这个key对应的节点就会被移动到链表尾部。

利用这个特性，LRU缓存可以这么写：

class LRUCache extends LinkedHashMap<Integer, Integer> { private final int capacity; public LRUCache(int capacity) { super(capacity, 0.75f, true); this.capacity = capacity; } @Override protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) { return size() > capacity; } }

三行核心逻辑，但背后有不少细节。super(capacity, 0.75f, true)三个参数分别是初始容量、负载因子、accessOrder。置true之后，每次get或put操作都会触发内部的afterNodeAccess回调，把刚访问的节点挪到链表尾部。removeEldestEntry是插入完成后的钩子方法，返回true时就删除链表头部的节点——注意，在LinkedHashMap的实现里，链表头部是最久未访问的，尾部是最近访问的，正好和手写版本相反。

这个方法能不能用？能，生产环境里如果不想引入第三方库，LinkedHashMap版LRU是完全可行的。但它的淘汰粒度只支持"容量超过上限就删一个"，如果你需要按时间过期、按key维度设置不同的淘汰策略，它就不够灵活了。

5.2 为什么面试题不让你直接写LinkedHashMap

面试官让你手写LRU，不是不知道有LinkedHashMap，恰恰相反，他是在考察你对底层机制的理解。直接甩一个removeEldestEntry重写上去，说明你只知道"能用"而不知道"为什么这样能用"。

手写版本考察的是：

• 对哈希表和链表两个数据结构的理解深度
• 对指针操作边界条件的掌控能力
• 对复杂度的推导能力

这三项才是数据结构和算法面试真正想筛选的能力。LinkedHashMap版本背熟了三分钟就能默写，但它不会让你理解为什么"哈希加双向链表"是O(1)的。我的建议是：两版都要会，先能手写底层版，再用LinkedHashMap做对照验证，这样既理解原理又有生产落地方案。

5.3 生产环境里选LRU还是LFU，没人告诉你的事

手写一个LRU容易，但在真实系统里选用淘汰策略，要考虑的问题远不止缓存容量。

LRU有一个经典缺陷——缓存污染。如果一个冷门数据在短时间内被批量访问了一次，LRU会把它当成"热门数据"留在缓存里，挤掉真正的热点数据。针对这个场景，LFU（Least Frequently Used，最不经常使用）策略更合适，它按访问频率淘汰。但LFU也有问题，历史高频数据可能永远不被淘汰，即使最近已经不热门了。现代缓存库往往用LRU的变体或者LRU和LFU的组合策略来避开这个坑。

在Java世界里，生产级本地缓存的推荐方案是Caffeine。它内部实现了W-TinyLFU算法，结合了LRU和LFU的优势，性能非常出色。如果你只是需要一个简单的LRU，用LinkedHashMap足够了；但如果你的缓存命中率对业务影响很大，直接上Caffeine，不要浪费时间去优化自己写的LRU——优化空间有限，坑倒是一堆。

6. 实测验证：边界用例与一次真实的踩坑记录

6.1 测试用例清单：验证LRU的正确性

写完代码不能直接扔到一边，得用测试用例验证逻辑。我建议至少要覆盖这几类场景：

这里特别说一下容量为1的边界。容量1时，每次put新key，链表里只有一个元素，新节点插入头部后，size变成2超过容量，于是删除尾部节点——而尾部节点恰恰就是刚插入的那个新节点。所以put(2,2)之后，缓存里没有任何数据。这不是bug，这是"容量只有1"的正确行为。但如果你的代码在put时先淘汰再插入，顺序反了，就会出现"新插入的key反而被删掉了"的诡异现象。

6.2 一次真实踩坑：忘掉map.remove引发的数据错乱

最后分享一个我实际调试中踩过的坑。有一次封装LRU测试时，我在put里写淘汰逻辑，链表操作全部正确，size也减了，但忘了执行map.remove(removed.key)。结果是什么？被淘汰的key在map里还残留着引用，get这个key时：

• 第一步，map查到了节点，返回了value
• 第二步，这个节点早就从链表里摘下来了，但moveToHead时它依然是合法节点

所以get竟然能返回成功！表面上看起来"缓存没有淘汰干净"，实则是map和链表不同步了。排查过程很有意思：我先打印链表长度，发现链表确实是2个节点；再打印map的size，发现map里是3个映射——这一刻问题立刻暴露了。

这个场景很多人容易忽略，因为单看put的每行代码都"对"，只要遗漏了map的同步删除，整体行为就是错的。这件事加深了我的一个习惯：凡是涉及map和链表双结构联动的代码，写完第一版先做数据一致性自查——链表里每个节点，map里必须能找到；map里每个映射，链表里必须存在对应节点。这两条同时成立，代码才算写完。

这题我前前后后手写过几十遍，每次重写都会有新的收获：第一次能默写，第二次理解了addToHead的指针顺序，第三次想明白了为什么需要哨兵节点，第四次才开始关注并发和淘汰策略的边界。数据结构这种东西，看十遍不如手写一遍。你可以试着不用IDE自动提示，徒手把这段代码写出来，再跑一遍边界用例，感受绝对不一样。