企业官网建设流程全解析

如果你去一线大厂面过后端岗，十有八九会在算法轮撞上这道力扣 hot100 里的经典题：手写一个 LRU 缓存。我第一次刷到它的时候，跟着题解用双向链表加哈希表抄了一遍，AC 之后感觉良好。结果面试官一句“为什么不能用单向链表”“get 的时候为什么要动链表”，直接把我问傻了。

这道题难吗？单看思路其实不难，几十行代码就能写完。但它考察的远不止“会不会背模板”，而是你对缓存淘汰机制的底层理解、对数据结构的权衡能力，以及写代码时处理边界条件的细心程度。这篇文章我打算从真实场景讲起，把双向链表加哈希表这套组合的原理拆开揉碎，再带你把代码逐行过一遍，最后聊几个面试官高频追问的变体和并发方案。不管你是刚刷题的新手，还是准备冲刺 offer 的老手，这篇都能帮你把 LRU 这题彻底吃透。

1. 为什么每个系统都在用 LRU：这不是一道考试题，而是真实世界的需求

1.1 从 Redis 内存淘汰到操作系统页面置换：LRU 的实际场景

LRU（Least Recently Used，最近最少使用）并不是某个大牛凭空发明的算法，而是几乎所有带缓存能力的系统里都会用到的淘汰策略。它解决的问题非常具体：内存或存储空间有限，新数据要放进来时，到底应该把谁踢出去？

最朴素的直觉是“把最少用的踢掉”，但“最少用”怎么量化？LRU 给出的答案很简单——最近最久没被访问过的数据，就是最可能没用了的。这个假设在大多数业务场景下都成立：刚被读过的数据，短时间内大概率还会被读；很久没碰的数据，未来被访问的概率相对更低。

举几个你每天都会接触的例子：

• Redis作为内存数据库，内存是有限的，设置了maxmemory之后，数据写不进去了怎么办？Redis 提供了多种淘汰策略，其中allkeys-lru和volatile-lru就是按照 LRU 近似算法来淘汰键的。也就是说，你项目里 Redis 缓存的数据，底层很可能就是靠 LRU 来保证内存不会被撑爆。
• MySQL 的 Buffer Pool缓存了磁盘中经常访问的数据页，它内部用的其实是 LRU 的改良版本，把链表分成了 young 区和 old 区，避免一次全表扫描把热数据全部冲掉。
• 操作系统的页面置换算法里，LRU 也是最经典的思路之一，虽然现代 OS 因为硬件代价会采用 Clock 等近似算法，但核心思想一脉相承。
• 浏览器的缓存淘汰、CDN 的缓存节点、本地 DNS 缓存，只要是“容量有限 + 需要淘汰”的缓存场景，LRU 都是默认选项之一。

所以面试官考这道题，本质上不是在考你背了多少行代码，而是在看你能不能理解一个真实系统里每天都在发生的事情。

1.2 力扣 hot100 把它排在前列的原因：高频考点背后的系统设计思维

力扣 hot100 是很多人刷题的主线，而 LRU 缓存这道题几乎常年霸榜。原因有几点：

第一，它考数据结构组合能力。单看哈希表或者单看链表，都是最基础的数据结构。但把两者组合起来实现 O(1) 的 get 和 put，就需要你对两种结构的特性有真正的理解。这比单纯背一个树的遍历要有区分度得多。

第二，它和实际工作强相关。后端开发每天都会接触缓存，手写一个 LRU 是对“缓存淘汰”最直观的实践。面试官可以从这道题轻松引申出 Redis 的淘汰策略、本地缓存的设计、Guava Cache 的实现思路等一系列问题。

第三，它代码量适中、边界条件丰富。几十行代码里包含了“更新已有 key”“容量满淘汰”“刚好容量为 1”“get 也要改变访问顺序”等好几种容易翻车的细节。能在白板上一次写对的人，代码基本功通常不会差。

所以从刷题策略来讲，这道题值得你花时间彻底吃透。我的建议是：先把原理搞清楚，再动手写三遍以上，直到能 10 分钟内无 bug 写出完整代码为止。

2. 双向链表 + 哈希表：这个组合到底解决了什么问题

2.1 哈希表负责“找人”，双向链表负责“排序”

先想一个问题：如果我们只有哈希表，能不能实现 LRU？

哈希表能 O(1) 找到 key 对应的 value，但哈希表本身是无序的。当缓存满了，我们需要知道“谁是最久没被访问的”并把它删掉。哈希表答不上来这个问题，除非你遍历所有 key 去比较访问时间，那复杂度就变成 O(n) 了。

再想：如果只有链表呢？

链表能记录元素的访问顺序：最新的排头，最老的排尾。链表头部插入是 O(1)，尾部删除也是 O(1)——前提是你直接持有尾部节点的引用。问题在于，当我们要 get 某个 key 时，得从头遍历链表找到这个节点，再把它移动到头部，这是 O(n) 的。缓存本来就是用来加速的，O(n) 的命中查询不可接受。

哈希表和链表刚好互补：哈希表解决“快速定位到这个节点在哪儿”，链表解决“维护先后访问顺序”。两者合体，get 和 put 都能做到 O(1)。

打个比方。想象你办公桌上有一摞文件，最新用过的放在最上面，最久没用的在最底下，桌子只能放 10 份，满了就扔掉最底下的。现在你找一份文件，如果只知道文件名，你得从顶上往下翻——这就是纯链表。而哈希表相当于给你装了一个“文件索引系统”，你输入文件名，它直接告诉你“这份文件在从上面数第几本”。找到之后你把它抽出来放回最上面，这一步由于你直接拿到了它的位置，不需要从第一本重新翻起。

数据结构组合的核心逻辑就是这样：哈希表负责定位，链表负责排序。

2.2 为什么必须是双向链表：最后一个节点往前走的代价

这是面试官最爱追问的一个点。很多人代码写完了，被问“为什么是双向链表，单向不行吗”就懵了。

关键在于删除操作。LRU 缓存满了之后，我们要删除的是链表尾部的节点，也就是最久未访问的那个。删除一个节点，需要知道它的前驱节点，让前驱的 next 跳过它。

如果是单向链表，每个节点只有 next 指针。你手里有尾部节点的引用，但你没有它的前驱。要找到前驱，只能从头遍历到尾部附近——O(n)。这等于 put 操作在最坏情况下退化成了线性复杂度，整个 O(1) 的设计就崩了。

双向链表就完全没有这个问题：尾部节点的 prev 直接指向前驱，删掉尾部只需要tail.prev.prev.next = tail和tail.prev = tail.prev.prev两行操作（具体写法我们后面再细说），纯 O(1)。

有个很经典的类比：单向链表就像一条单行道，你站在最后一辆车旁边，想叫前面的车挪一下，但前车看不到你，你得跑到路口去挨个通知。双向链表是双向两车道，每辆车都知道前面是谁、后面是谁，站在最后一辆就能直接往前联系。

2.3 哨兵节点：让边界判断从此消失

写链表题最烦的是什么？处理“空链表”“节点在头部”“节点在尾部”这些边界情况。LRU 缓存里我们频繁要做头部插入、尾部删除、任意节点移动，如果用传统的 null 判断，代码里会充满if (node.prev != null)和if (node.next != null)，既丑又容易错。

解决办法是加两个哑节点：head和tail。它们不存储实际数据，只作为链表的边界标记。

初始状态是head.next = tail、tail.prev = head，真正有效的节点都夹在head和tail之间。

这样做的好处是：

• 链表永远不为空，至少还有两个哨兵节点在。
• 头部插入时，不需要判断 head.next 是否为 null，直接插在 head 和原来的第一个节点之间。
• 删除尾部时，tail.prev一定是最后一个有效节点，不需要判断链表是否为空。
• 任意节点移动时，remove 和 add 两个操作互相独立，不需要考虑“删除的是不是头节点”这种特例。

我在实际写代码时习惯用哨兵节点，因为它能把你从大量的分支判断里解放出来，让思路集中在业务逻辑上。力扣上很多人提交的代码也是这个风格，建议你直接采用，别自己造轮子去处理特殊情况。

3. 代码实现细节：不写一遍绝对发现不了的坑

3.1 定义节点结构和三个基础操作

先看完整的 Java 实现，我的写法比较经典，关键在于拆出了三个私有方法：addToHead、removeNode、moveToHead。这样后面 get 和 put 的主逻辑就非常干净了。

class LRUCache { // 双向链表节点 class Node { int key; int value; Node prev; Node next; public Node() {} public Node(int key, int value) { this.key = key; this.value = value; } } private Map<Integer, Node> cache = new HashMap<>(); private int capacity; // 哨兵节点，head.next 是最近使用的，tail.prev 是最久未使用的 private Node head = new Node(); private Node tail = new Node(); public LRUCache(int capacity) { this.capacity = capacity; head.next = tail; tail.prev = head; } public int get(int key) { Node node = cache.get(key); if (node == null) { return -1; } // 数据被访问了，它应该变成最近使用的 moveToHead(node); return node.value; } public void put(int key, int value) { Node node = cache.get(key); if (node != null) { // key 已存在，更新值并移动到头部 node.value = value; moveToHead(node); return; } // 缓存已满，先淘汰最久未使用的节点 if (cache.size() == capacity) { Node last = tail.prev; removeNode(last); cache.remove(last.key); } // 创建新节点，加入哈希表并插入链表头部 Node newNode = new Node(key, value); cache.put(key, newNode); addToHead(newNode); } // 将节点插入到 head 之后 private void addToHead(Node node) { node.prev = head; node.next = head.next; 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); } }

这段代码的核心是三个私有方法。很多人会纠结addToHead的四行赋值顺序有没有讲究。我的建议是：先处理新节点的 prev 和 next，再处理前后两个邻居的指针。上面这个顺序很好记，也基本不会出错。如果你喜欢先告诉 head“你后面是新节点”，也可以，但一定要小心别把 head.next 的旧引用覆盖掉导致链表断开。

3.2 get 和 put 的正确顺序：先删后插还是先插后删？

这一节说的不是代码语法，而是操作链表的时机。

先看 get。很多人会问：我只是读一下缓存，为什么要移动节点？因为 LRU 的语义是“最近最久未使用”，刚才被读过的 key，它的“最近使用时间”已经变了，必须把它提到链表头部，否则它可能很快被当作“最久未使用”给淘汰掉。这个细节是 LRU 和 FIFO（先进先出）最大的区别：访问也改变顺序。

再看 put，分三种情况：

1. key 不存在、缓存未满：创建节点，cache.put存映射，addToHead插入头部。两个操作顺序无所谓。
2. key 不存在、缓存已满：先把尾部节点从链表和哈希表里都删掉，再创建新节点。注意先淘汰再插入。
3. key 已存在：更新 value，然后把节点移动到头部。这里很多人会踩一个坑——只更新 value 忘了移动节点。如果忘了 moveToHead，这个 key 的访问顺序就没有更新，后续可能被错误淘汰。

我在帮朋友 review 代码时见过一个隐蔽的 bug：有人在 put 已存在的 key 时，直接删掉旧节点、创建新节点再插头。这样功能上没错，但多了一次 Node 对象的创建和垃圾回收，在高频调用下会造成不必要的内存波动。更规范的做法是复用节点，直接改 value。

还有一个细节值得注意：判断缓存是否满的时候，我写的是cache.size() == capacity。有人会在类里维护一个size变量，每次插入/删除手动更新。两种方式都可以，但用cache.size()更省心，因为哈希表的 size 和链表长度一定是同步的，不用额外维护，也不容易出现“size 没更新”的 bug。

3.3 容易翻车的边界：容量为 1、更新已有 key、满容量时删除

边界条件才是这道题真正的得分点。

容量为 1 的情况。此时 put 一个新的 key，链表里只有一个有效节点。再 put 另一个 key，先触发淘汰，把唯一的节点删掉，再插入新节点。由于哨兵节点的存在，删除和插入操作都能正常工作。如果不用哨兵节点，这个场景很容易出现head.next == null之类的空指针问题。

更新已有 key 时恰好也是容量满的状态。比如容量是 2，里面是[1, 2]，此时 put1的新值。由于 key 已存在，走到的是更新分支，不会触发淘汰，链表长度不变，只是把节点 1 移到了头部，变成[1, 2]。这里如果你在更新分支里误写了cache.size() == capacity的判断去淘汰节点，就会把节点 2 删掉，导致缓存里只剩一个元素，后面的访问就会出问题。

删除“最久未使用”的节点时，别忘了从哈希表里同步删除。链表里摘除节点只是断了指针关系，哈希表里那个key -> Node的映射还留着。如果只删链表不删哈希表，下次 get 这个 key 时cache.get还能查到 Node，但这个 Node 已经不在链表里了，moveToHead 会产生悬空引用，程序直接崩溃或行为异常。所以代码里cache.remove(last.key)这一行绝对不能漏。

我自己第一次写这道题时，最常犯的错误就是把链表操作和哈希表操作当成两件独立的事情，结果链表删了哈希表没删，或者哈希表插了链表没插。记住一个心法：每次涉及节点的增删，链表和哈希表必须同步完成。

4. 面试官爱问的进阶变体和等价实现：LinkedHashMap 与 LFU 延伸

4.1 用 LinkedHashMap 三行实现，但你必须能讲清原理

很多面试官会让你“用语言自带的库实现”，这时候 Java 选手可以搬出 LinkedHashMap。

LinkedHashMap 在 HashMap 的基础上，把每个 Entry 串成了一个双向链表，而且支持两种迭代顺序：插入顺序（默认）和访问顺序。把accessOrder设为 true，每次 get 或 put 访问过的节点会自动移动到链表尾部。再重写removeEldestEntry，当容量超过阈值时返回 true，就会自动移除最老的条目。

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

这段代码能过力扣，但我要提醒你：如果面试官让你手写 LRU，你直接甩 LinkedHashMap，大概率是要扣分的。因为这不是在考察你对 LRU 的理解，而是考察你对 JDK 源码的熟悉程度。面试官追问一句“LinkedHashMap 底层怎么保证访问顺序的”，如果你答不上来，反而暴露了短板。

正确姿势是：先用双向链表 + 哈希表的手写版本讲清楚原理，最后补一句“实际项目中如果允许用 JDK 库，也可以用 LinkedHashMap 简化实现”，然后解释它的底层也是一个双向链表结构。这样既展示了基本功，又体现了工程思维。

4.2 从 LRU 到 LFU：当淘汰依据从“最近”变成“频率”

面试官把 LRU 讲清楚之后，经常会顺势问一句：“那 LFU（Least Frequently Used，最不经常使用）你会怎么设计？”

LFU 淘汰的是访问频率最低的 key。最朴素的思路是每个 key 维护一个计数器，淘汰时找计数最小的。但“找最小”本身要遍历，如何做到 O(1) 的操作复杂度，是个经典的进阶题。

标准的解法是频率分桶 + 两个哈希表：

• 一个哈希表存key -> 节点。
• 另一个哈希表存频率 -> 双向链表，同一个频率的所有 key 放在同一个链表里。
• 每次访问 key 时，把它从当前频率链表中移除，计数加一，放到更高频率的链表中。
• 淘汰时，直接找到最小频率对应的链表，删除链表的尾部节点。

这套结构的核心思路和 LRU 异曲同工：哈希表定位节点，链表维护同一频率内部的访问顺序。只是多了一层“按频率分桶”的维度。你能把 LRU 讲透，再往 LFU 延伸就会顺畅很多。

我个人觉得，面试官问 LFU 不指望你能 10 分钟写出完整代码，而是看你能不能快速拆解出“需要哪些数据结构”以及“时间复杂度如何保证”。所以重点是讲思路，不是背代码。

4.3 并发场景：从 synchronized 到分段锁，再到 ConcurrentHashMap

力扣上的 LRU 题是单线程的，但真实项目里缓存一定是多线程共享的。面试官很爱在这个地方拦你一下。

最简单的做法是给 get 和 put 都加上synchronized，保护整个 LRU 结构。代码改动很小，但在高并发场景下，所有线程都串行访问缓存，QPS 上不去。加锁粒度太粗是第一个阶段的瓶颈。

进阶一点的做法是读写锁：get 操作加读锁，put 操作加写锁。因为 get 只读数据并改变链表顺序，实际上它也修改了链表结构，所以严格的读写锁对 get 也得加写锁，收益有限。这也是 LRU 并发优化比较棘手的地方——链表顺序本身就是可变状态，每次访问都在改它。

再进阶是分段锁，把缓存按 key 的哈希值分成多个段，每个段独立维护自己的 LRU 链表，不同段的访问互不干扰。代价是全局淘汰时，每段各自淘汰自己的，整体可能不是严格全局 LRU，但工程上通常可以接受。

最极端的优化是采用ConcurrentHashMap存数据，链表操作通过 CAS 或细粒度锁来做，但手写一个无锁双链表难度极高，工业界通常直接上 Caffeine、Guava Cache 这类成熟组件，而不是自己造轮子。

面试时，我建议你的回答思路是：先明确单线程版本是基础，然后按场景逐步加锁，最后点出现有开源方案的做法。这样层次分明，显得你有实际工程经验。

5. 实测中发现的性能细节与个人体会

5.1 为什么每次 get 也要动链表：访问顺序不是插入顺序

我见过不少初学者的代码，get 方法就是简单的map.get(key)，完全不碰链表。跑测试用例时，只要 key 存在都能通过，但放到淘汰场景就错了。

举一个最简单的例子：容量为 2，依次 put (1, a)、(2, b)，此时链表顺序是 [2, 1]，2 是最近使用的。再 get(1)，正确情况下链表变成 [1, 2]，此时 put (3, c) 应该淘汰 2。但如果你 get 不动链表，put (3, c) 时链表还是 [2, 1]，淘汰的是 1，而不是真正“最久没被访问”的 2。这就违背了 LRU 的核心语义。

这个坑在测试用例里很容易被暴露，所以力扣的判题器非常严格，get 后链表顺序不对直接 WA。你刷的时候如果遇到“部分用例过、部分用例挂”，优先检查的就是 get 方法有没有调 moveToHead。

我在实测中还发现，get 已存在 key 后返回的 value 要考虑是否更新访问顺序。虽然返回值是一样的，但内部状态完全不同。这也是为什么“看起来很简单”的代码，实际写出来容易错的原因。

5.2 用 int 还是用泛型：面试里的隐形加分项

力扣原题的 key 和 value 都是 int，所以很多人的代码直接写Map<Integer, Node>。如果面试官把场景扩展成“缓存任意对象”怎么办？

我建议你在写算法的时候就养成泛型的习惯，把 Node 定义成泛型类，LRUCache<K, V>。核心逻辑不变，只是多几个尖括号：

class LRUCache<K, V> { class Node { K key; V value; Node prev; Node next; } private Map<K, Node> cache = new HashMap<>(); // 其余逻辑完全一致 }

这样做的好处是：面试的时候你可以在代码层面直接展示自己的抽象能力，不用面试官提醒才想到“对象缓存”的场景。一个小改动，给面试官的观感完全不同。

另外，如果你用Map<Integer, Node>，Node 里存 key 是为了淘汰时能从哈希表里删掉对应映射。这个细节也值得注意：链表节点里必须存 key。如果只存 value，淘汰尾部节点时你根本不知道它的 key 是什么，没法cache.remove(key)。

5.3 写在最后：这道题究竟在考你什么

刷了这么多遍 LRU，我个人最大的体会是：它其实是**“数据结构组合”思想的一个缩影**。哈希表和链表单独拿出来都不难，但如何让它们协作解决一个真实问题，才是编程能力的体现。

这也解释了为什么力扣 hot100 里它的热度一直居高不下。如果你能不看题解，独立从“为什么是双向链表”推导到“哈希表存 key 到节点的映射”，再快速写出无误代码，同时对 const 时间复杂度给出合理解释，那你在面试中的算法轮已经具备了很强的竞争力。

建议你在刷题时多问自己几个“为什么”：为什么不是数组？为什么不用标准库的 LinkedList？为什么可以做到 O(1)？把这些想透之后，代码怎么写反而成了最简单的事情。这道题的收获，也会反向帮助你去理解 Redis 的缓存淘汰、Caffeine 的设计思路，以及一切和“有限容量缓存”相关的系统设计问题。