企业官网建设流程全解析

1. 什么是LRU：面试常问，但你真的理解了吗

先聊一个面试场景。很多同学在简历上写“熟悉常用数据结构”，面试官基本不会直接问你“数组和链表的区别是什么”，而是会挑一个看似简单、实际能一层层挖下去的问题：“你了解LRU吗？手写一个LRU Cache。”

如果你只是回答“Least Recently Used，最近最少使用”，那大概率只能拿到一句“回去等通知”。因为这个问题考察的不是你能不能背出定义，而是你有没有真正理解“缓存淘汰”这件事的本质，以及能不能用代码把思想落地。

LRU的全称是Least Recently Used，翻译过来就是“最近最少使用”。它的核心逻辑很简单：当缓存空间满了，优先淘汰那些最久没被访问过的数据。这个策略背后有一个经典的局部性原理：刚被访问过的数据，在短时间内大概率还会被再次访问；反过来，已经很长时间没被访问的数据，未来被访问的概率也比较低。所以与其留着一个“冷数据”占地方，不如把它清掉，给新数据腾位置。

听起来很简单对不对？但真到了实现层面，事情就没那么轻松了。你需要保证每一项操作的时间复杂度都是O(1)，也就是说，不管是查询一个数据、插入一个新数据，还是淘汰一个旧数据，都不能因为数据量变大而变慢。能做到这一点，才算是真正把LRU吃透了。

这篇文章我就从零开始，把LRU的原理、数据结构选型、手写实现、真实场景里的演进，以及面试中容易被追问的细节，一次讲清楚。

2. 核心思想与数据结构选型：为什么偏偏是双向链表加哈希表

2.1 用生活场景理解LRU的“淘汰逻辑”

先别急着看代码，我用一个特别常见的场景帮大家建立直觉。

假设你手机后台只能同时运行3个App，这时候你打开了第四个App，系统必须杀掉一个才能腾出内存，杀谁？按照LRU的思想，应该杀掉“最久没被重新打开”的那个。

比如你依次打开了微信、抖音、淘宝，然后切回微信回了个消息。这时候后台三个App的使用时间排序就变了：微信是刚用过的，淘宝虽然打开得早但比抖音晚，抖音是最早打开、之后一直没碰过的那个。如果再开一个App，被杀的应该是抖音，而不是淘宝。

你会发现，这个过程中有两个关键动作：一是记录每个数据被访问的先后顺序，二是当容量满了，找到那个最久没被访问的“倒霉蛋”并删掉它。LRU的所有实现思路，本质上都是在解决这两个问题。

2.2 常见方案逐个排除：数组、链表、哈希表，谁不行

既然要记录“访问顺序”，最容易想到的就是给每个数据加一个时间戳，每次访问就更新时间戳，淘汰时扫一遍找最旧的那个。这个方案查询要O(1)，但找最旧的要O(n)，数据一多就废了。

那用数组呢？数组按访问顺序存储，每次访问后要把这个元素挪到末尾，数组挪动元素的代价是O(n)，大数据量下也是灾难。

用单向链表呢？链表插入和删除确实是O(1)，但你要“找到”这个节点才能操作。在链表里找一个节点需要遍历，又是O(n)。另外，如果你只知道要删除某个节点的前驱节点，单向链表还得从头遍历才能找到前驱，同样慢。

这时候你可能会想：能不能用哈希表来直接定位节点？但是哈希表本身是无序的，它只解决“快速找到”的问题，解决不了“知道谁最久没被访问”的问题。

所以结论已经很清晰了：单独用任何一种基础数据结构，都无法同时满足“快速查找”和“有序淘汰”两个要求。很多人在这里卡住，是因为总想着用一个结构搞定所有事，而LRU的经典解法从一开始就是“组合拳”。

2.3 双向链表加哈希表：各自负责什么

最终的标准答案：哈希表加双向链表。

• 哈希表（HashMap）负责快速定位节点，key是缓存的键，value是链表节点的引用。这样你能在O(1)时间内找到任何一个节点在链表中的位置。
• 双向链表负责维护访问顺序。每次访问某个节点，就把它移动到链表头部；链表尾部的节点，就是最久没被访问的节点，淘汰时直接删尾部。

你可能会问：为什么一定要双向链表，单向不行吗？这里有个特别关键的细节。当你要把一个节点移动到头部时，需要先把它从当前位置摘下来，然后让它的前一个节点和后一个节点接上。单向链表只有next指针，你根本不知道某个节点的前驱是谁。而双向链表有prev指针，摘除节点只要O(1)就能完成。这就是为什么面试时你写单向链表，基本会被直接判定不合格。

用一张简化的流程来说明：

• 查询某个key时，先从HashMap里拿Node引用，然后把该Node移动到链表头部，返回value。
• 插入新key时，如果key已存在，更新value并把Node移到头部；如果不存在，创建新Node放到头部，同时放进HashMap。
• 如果插入后链表长度超过容量，就删除尾部节点，同时把HashMap里对应的key删掉。

整套操作下来，每一步都只用O(1)时间，完美满足要求。

2.4 HashMap的value为什么要存Node，而不是value本身

这又是一个很容易被问到的细节。有些人会想，HashMap<Key, Value>不是已经很方便了吗，为什么value还要包一层Node？

原因是：你不仅要根据key找到value，还要在O(1)时间内修改这个节点在链表中的位置。如果value直接存String或Integer，你在链表里移动它的时候，还得在HashMap里再查一次才知道对应哪个节点，根本没有节点的引用，移动操作根本无法在常数时间内完成。

把value设计成Node节点，相当于在HashMap和双向链表之间建立了“桥梁”：

• HashMap的value指向链表中的某一个节点。
• 链表节点里又存了key、value、prev、next。

这样你拿到一个Node，既能改它的值，又能操作它在链表里的位置。这也是LRU实现中最容易想不明白的一个点，一旦想通，代码基本就顺了。

3. 手写LRU Cache：一份面试能直接默写的Java实现

篇幅有限，我不讲太多废话，直接把一份完整、可运行的Java实现放出来，再逐段拆解。

3.1 完整代码

import java.util.HashMap; import java.util.Map; public class LRUCache<K, V> { // 双向链表节点定义 static class Node<K, V> { K key; V value; Node<K, V> prev; Node<K, V> next; Node(K key, V value) { this.key = key; this.value = value; } } private final int capacity; private final Map<K, Node<K, V>> map = new HashMap<>(); // 虚拟头尾节点，省去大量空指针判断 private final Node<K, V> head = new Node<>(null, null); private final Node<K, V> tail = new Node<>(null, null); public LRUCache(int capacity) { if (capacity <= 0) { throw new IllegalArgumentException("capacity must be positive"); } this.capacity = capacity; head.next = tail; tail.prev = head; } public V get(K key) { Node<K, V> node = map.get(key); if (node == null) { return null; } // 访问了就要更新位置：先摘除，再移到头部 removeNode(node); addToHead(node); return node.value; } public void put(K key, V value) { Node<K, V> node = map.get(key); if (node != null) { // key 已存在，更新值并移到头部 node.value = value; removeNode(node); addToHead(node); return; } // 新增节点 Node<K, V> newNode = new Node<>(key, value); map.put(key, newNode); addToHead(newNode); if (map.size() > capacity) { // 删除尾部节点，也就是最久未使用的 Node<K, V> tailNode = tail.prev; removeNode(tailNode); map.remove(tailNode.key); } } private void removeNode(Node<K, V> node) { node.prev.next = node.next; node.next.prev = node.prev; } private void addToHead(Node<K, V> node) { node.next = head.next; node.next.prev = node; head.next = node; node.prev = head; } public int size() { return map.size(); } }

3.2 为什么使用虚拟头尾节点

新手最容易在这里翻车。如果你不用虚拟头节点，那么当链表为空时，往头部插入节点，或者从头部删除节点，都要专门写if判断头节点是不是null，极其容易漏判断然后抛NullPointerException。

有了head和tail这两个虚拟节点，整个链表永远不为空，插入和删除的代码逻辑就统一了。你可以把虚拟头尾理解为“哨兵”，它们不存业务数据，只是让边界处理变简单。

这在工程上也是一个很常见的技巧。不只是LRU，很多链表的题目（反转链表、删除倒数第N个节点）用上虚拟头节点都能少写不少分支判断。

3.3 每次get都在修改数据，这说明了什么

有同学可能会疑惑：我只是查一个数据，为什么还要在链表里移动它？

因为get操作本身就是一次“访问”，LRU判断“谁最久没被使用”，靠的就是每一次访问的记录。如果一个数据只是被反复查询，那它应该被保留；如果一个数据已经很久没人查了，它才应该被淘汰。如果get不更新顺序，那你无法区分“最近被查过很多次”和“很早查过一次再也没查过”的数据，淘汰策略就失效了。

所以只要执行了get，就必须把节点挪到链表头部。这也是面试里经常被追问的细节之一，我见过很多候选人在put里记得维护顺序，到了get里就忘了，直接返回value，这种实现是不完整的。

3.4 复杂度分析

• get操作：HashMap查一次O(1)，拆节点和插头部都是O(1)。
• put操作：HashMap查一次O(1)，如果更新或新增，拆节点、插头部、删除尾部也都是O(1)。

因为链表节点在内存中不是连续存储的，链表操作和数组不同，不需要搬移大量元素，所以“移动到头部”这个动作无论缓存多大，耗时都是恒定的。

空间复杂度是O(capacity)，因为HashMap最多存capacity个key，双向链表最多存capacity个节点。

3.5 测试代码：用数据验证正确性

写完了不能光看着，直接跑个测试：

public class LRUTest { public static void main(String[] args) { LRUCache<Integer, String> cache = new LRUCache<>(3); cache.put(1, "A"); cache.put(2, "B"); cache.put(3, "C"); System.out.println(cache.get(1)); // 输出 A，此时访问顺序变为 1,3,2 cache.put(4, "D"); // 容量3已满，最久未使用的2应该被淘汰 System.out.println(cache.get(2)); // 输出 null，因为2已被淘汰 System.out.println(cache.get(3)); // 输出 C System.out.println(cache.get(4)); // 输出 D } }

测试结果应该依次输出：

A null C D

跑通这个用例，说明基本逻辑没问题。但是面试官不会只满足于“能跑”，他大概率会继续追问边界情况，这部分我在最后一章统一讲。

4. 从LRU到LRU-K：真实系统里是怎么演进的

4.1 经典LRU有什么硬伤

标准LRU虽然在面试中够用，但真放在生产环境里，它有一个非常明显的问题：缓存污染。

什么叫缓存污染？举个例子，某个冷门数据在某个瞬间被批量访问了一次（比如定时任务扫了一批历史数据），它的“最近使用时间”会被顶得很靠前，把真正热的数据挤出去了。但这一批数据其实以后几乎不会再被访问。结果就是：缓存里留着一堆“刚被用过一次但从此冷掉”的数据，真正的热数据反而被淘汰了，缓存命中率直线下降。

用一句话概括就是：一次性的偶发访问，把高频热点数据挤掉了。

4.2 LRU-K：多一次观察窗口

为了解决缓存污染，业界提出了LRU-K。这里的K不是指容量，而是指“访问K次之后才进入缓存”。

它的思路也很直接：数据第一次被访问时，不直接放进缓存，而是放进一个“候选区”，只记录访问次数和最近访问时间。只有当这个数据被访问的次数达到K次（通常K取2），才被认为有缓存价值，正式进入缓存。一旦进入缓存，再按照标准的LRU规则进行维护。

这样做的好处是，那些只被临时访问一次的数据根本进不了缓存，自然也就不会污染真正的热点数据。代价是实现更复杂，你需要维护一个额外的访问记录队列，存储开销更大。

在真实系统里，很多自研缓存组件的底层其实就是LRU-2的变种。

4.3 Redis的近似LRU：不追求精确，只追求性价比

还有一个大家经常听说的场景是Redis。Redis明明有内存淘汰机制，但它并没有用严格的LRU，而是用了一种近似LRU的策略，因为严格LRU需要维护一个双向链表，对Redis这种单线程模型来说，额外内存开销和操作开销都不小。

Redis的近似LRU做法是：给每个key记录一个最后一次访问的时间戳（LRU时钟），淘汰时随机采样若干个key，淘汰其中空闲时间最长的那个。你可以把它理解为“抽样淘汰”，不保证全局最优，但大概率合理。

从Redis 3.0开始，Redis还引入了淘汰池（pool），每次随机采样之后，把候选key放进一个池子里，新采样的key和池子里的key比较，淘汰最旧的。这样经过多轮淘汰后，池子里保留的key越来越接近全局最久未使用的key，效果直逼严格LRU，但成本低很多。

这个演进过程其实说明了一个很朴素的道理：在工程上，我们往往不是追求理论最优，而是在效果和成本之间找一个平衡点。这个思路写进简历的项目里，会显得你对问题的理解不止停留在“背出LRU”这一层。

4.4 MySQL的Buffer Pool：LRU也要分层

另一个经典案例是MySQL的InnoDB Buffer Pool，它也有类似的改进。

MySQL的Buffer Pool把LRU链表分成两段：young区域和old区域，默认比例是5比3。新读入的数据页先放进old区域，只有再次被访问到，才会被提升到young区域。这个设计和LRU-K其实是同一个思路：给新数据一个“观察期”，避免全表扫描这种一次性读入大量冷页，把真正的热页全部挤出内存。

如果你在面试时能主动提到“MySQL的Buffer Pool也是这么做的”，面试官对你的评价通常会高不少，因为这说明你真的在平时积累过这类系统设计，而不是死记硬背。

5. 高频追问与避坑指南：实战中容易踩的坑，我一次说清楚

5.1 容量为1的时候会怎样

这是面试官最爱问的边界条件之一。当capacity等于1时，你put一个数据进去，再put第二个数据，第一个数据会被立刻淘汰。这要求你的代码在链表只有1个节点的情况下，remove和add操作不能出错。

用虚拟头尾节点实现的话，这个场景天然安全。但如果你用的是裸Node（即不使用虚拟节点）的实现，这里就要小心了：删除尾部节点的时候，如果尾部正好是头节点，你得把head也置空，否则下一次addToHead操作就会出现悬空引用。

所以我的建议是：面试时直接用虚拟头尾节点的写法，能少踩一半的坑。

5.2 key已存在时，要不要删除再插入？

有些同学实现put时，遇到key已存在的情况，会把旧节点删掉，再new一个新节点插到头部。这也能实现功能，但有一个隐患：

如果你在put过程中先删除了旧节点，还没来得及把新节点放进HashMap，此时如果代码抛出异常（比如内存分配失败），HashMap里的旧节点引用还在，但链表里的节点已经被拆掉了，整个缓存结构就损坏了。

更优雅的做法是：命中已存在的key时，直接复用旧节点，只更新value，然后移动到头部。这样能避免频繁创建对象，减少GC压力，也让结构始终保持一致。

5.3 并发场景下LRU怎么写

如果你给面试官说“我这份代码可以用于生产环境”，对方可能会追问：多线程同时get和put，你的HashMap会怎样？

答案是：HashMap在多线程下扩容时会形成循环链表，导致CPU飙到100%。所以生产环境里的LRU Cache至少有几种方案：

• 最简单：给get和put都加synchronized，变成线程安全版本，但并发度很低。
• 更好：使用ConcurrentHashMap + 双向链表的CAS操作，这也是Redis、Guava Cache等组件实际采用的方向。
• 最实用：Java的LinkedHashMap本身就是“哈希表+双向链表”的组合，重写removeEldestEntry方法就能实现LRU，再配合Collections.synchronizedMap或者使用并发容器，能快速得到线程安全LRU。

这里我多说一句，如果你只是想在日常开发中快速实现一个LRU，完全没必要自己手写链表。

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

LinkedHashMap的构造方法里第三个参数传true，表示开启访问顺序模式，每次get都会把对应Entry移动到链表尾部。配合重写removeEldestEntry，当容量超过阈值时自动删除最老的Entry。这是日常开发中最快的LRU实现方式。

不过面试官通常不满足于你用现成容器，他问“手撕LRU”就是要看你能不能从底层原理出发独立实现。所以LinkedHashMap的写法适合作为“补充玩法”来展示，核心还是你手写的那份。

5.4 面试追问：为什么不用数组加时间戳

这个问题我在前面已经提到过，这里集中整理成一张对比表，方便你记忆：

5.5 常见错误自查清单

我总结了几个手写LRU时最容易犯的错误，写完代码后对照检查一遍，能少踩很多坑：

• 是否忘了在get时更新节点顺序。
• 删除尾部节点时，是否忘了从HashMap里删掉对应的key。
• 移动节点时，是先把节点摘下来再插入头部，还是直接修改了指针导致链表断裂。
• addToHead时，新节点的prev是否指向了head。
• 容量是否在构造时做了合法性校验。
• 使用LinkedHashMap时，是否把accessOrder参数设成了true。

如果你写的版本能通过这一串检查，基本就不用担心面试官在代码层面挑毛病了。

最后说点我的个人感受

LRU这题我前前后后看过不下几十遍，自己也面试过不少人。我发现一个规律：能把原理讲清楚的候选人很多，但能在纸上把代码写对、写干净、还能应对追问的人其实不多。原因在于很多人习惯了“看得懂”就觉得自己“会写了”，但实际上手一写就漏洞百出。

所以如果你正在准备面试或者复习数据结构，我的建议是：不要只看我的代码，自己拿纸笔手写一遍，再跑几个测试用例，特别是容量为1、key重复、get不存在的key这几个边界场景。写完再思考一下“如果我想把它改成LRU-K，需要加哪些结构”。这样练过一轮之后，LRU就不再是一个需要死记硬背的答案，而是真正变成你自己的东西了。这份功夫，在面试里往往最容易被看出来，也最值得花时间。