一、什么是LRULRU 是 Least Recently Used 的缩写中文名叫“最近最少使用”算法本质是一种缓存淘汰策略。缓存的核心矛盾的是“空间有限”——我们不可能把所有数据都存在缓存比如Redis、内存缓存里当缓存空间满了新数据要进来就必须删掉一部分旧数据。而LRU的规则很简单淘汰掉“最久没有被使用”的数据。举个最贴近生活的例子你的手机后台APP管理。你先后打开了微信、抖音、小红书、浏览器手机内存有限当你再打开淘宝时系统会自动关掉最久没操作的APP比如微信只保留最近使用的几个——这个逻辑就是LRU的核心思想。再举个技术场景的例子假设缓存容量是3我们依次执行以下操作看看LRU是怎么工作的结合具体流程更易理解存入A → 缓存[A]只有A无淘汰存入B → 缓存[B, A]最近使用的B在前面存入C → 缓存[C, B, A]容量满无淘汰访问A → 缓存[A, C, B]A被访问变为最近使用移到最前存入D → 缓存满淘汰最久未使用的B → 新缓存[D, A, C]这个流程的核心依据是计算机科学中的时间局部性原理最近被访问的数据在未来一段时间内被再次访问的概率更高反之很久没被访问的数据未来被访问的概率极低——LRU正是基于这个原理实现了“高效利用缓存空间”的目标。二、LRU的核心原理与关键操作理解了LRU的基本思想我们再拆解它的核心原理和关键操作这是实现LRU的基础也是面试中常考的点。2.1 核心原理LRU的核心是“维护一个访问顺序”通过这个顺序快速判断出“最久未使用”的数据具体要满足两个核心需求快速访问给定一个key能快速判断它是否在缓存中若在能快速获取对应value时间复杂度尽量低快速更新当数据被访问、新增时能快速调整它的访问顺序当缓存满时能快速删除最久未使用的数据。2.2 关键操作必记LRU有两个最核心的操作所有实现方案都围绕这两个操作展开面试时被问“LRU怎么工作”其实就是让你讲清这两个操作get(key)获取缓存中key对应的值若key不存在返回-1或自定义未命中标识若key存在将该key对应的节点“提升为最近使用”调整访问顺序再返回value。put(key, value)向缓存中存入键值对若key已存在更新该key对应的value并将其提升为最近使用若key不存在新建节点存入缓存若存入后缓存容量超过限制淘汰“最久未使用”的节点即访问顺序最靠后的节点。三、LRU的3种实现方案从简单到高效实现LRU的关键是选择合适的数据结构来维护“访问顺序”和“快速查找”。不同的数据结构决定了实现的复杂度和性能下面介绍3种常见方案从易到难适合不同场景。3.1 方案1数组时间戳入门级不推荐用于生产这是最直观、最简单的实现方式适合初学者理解LRU思想但性能较差实际开发中很少用。实现思路用数组存储缓存数据每个数据项额外记录一个“访问时间戳”每次访问数据时更新该数据的时间戳为当前时间每次存入新数据时若缓存满遍历数组找到时间戳最小最久未使用的数据替换掉它。优缺点优点逻辑简单容易理解和实现缺点所有操作查找、更新、淘汰都需要遍历数组时间复杂度为O(n)数据量较大时性能会严重下降。3.2 方案2单链表进阶级仍有缺陷为了优化数组的遍历问题我们可以用链表来维护访问顺序减少遍历操作。实现思路用单链表存储缓存数据链表头部为“最近使用”的数据尾部为“最久未使用”的数据访问数据时若存在将该节点从原位置删除插入到链表头部存入新数据时直接插入到链表头部若缓存满删除链表尾部节点。优缺点优点更新访问顺序时无需遍历数组插入/删除操作更高效缺点查找数据时仍需从链表头部遍历到尾部时间复杂度还是O(n)不适用于缓存数据较多的场景。3.3 方案3双向链表哈希表工业级推荐这是工业界最常用、最高效的实现方案结合了双向链表“快速调整顺序”和哈希表“快速查找”的优点所有操作的时间复杂度都能做到O(1)也是面试中要求手写的核心方案。核心设计重点理解用“双向链表”维护访问顺序用“哈希表”维护key到链表节点的映射两者结合实现“查找快、更新快、淘汰快”双向链表节点存储key、value以及前驱指针prev和后继指针next引入“伪头”和“伪尾”哨兵节点避免操作首尾节点时的边界判断比如空链表、只有一个节点的情况链表头部伪头后面是最近使用的节点尾部伪尾前面是最久未使用的节点。哈希表key是缓存的键value是双向链表中对应的节点通过哈希表能在O(1)时间内找到key对应的节点避免链表遍历。import java.util.HashMap; import java.util.Map; // 双向链表节点 class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; public DLinkedNode() {} public DLinkedNode(int key, int value) { this.key key; this.value value; } } public class LRUCache { // 缓存容量 private int capacity; // 哈希表key - 双向链表节点实现O(1)查找 private MapInteger, DLinkedNode cache new HashMap(); // 伪头、伪尾哨兵节点避免边界判断 private DLinkedNode head, tail; public LRUCache(int capacity) { this.capacity capacity; // 初始化伪头和伪尾建立连接 head new DLinkedNode(); tail new DLinkedNode(); head.next tail; tail.prev head; } // 将节点添加到链表头部最近使用 private void addToHead(DLinkedNode node) { node.prev head; node.next head.next; head.next.prev node; head.next node; } // 删除链表中的某个节点 private void removeNode(DLinkedNode node) { node.prev.next node.next; node.next.prev node.prev; } // 将节点移动到头部更新为最近使用 private void moveToHead(DLinkedNode node) { removeNode(node); addToHead(node); } // 删除链表尾部节点最久未使用并返回该节点用于删除哈希表中的key private DLinkedNode removeTail() { DLinkedNode node tail.prev; removeNode(node); return node; } // 获取缓存值 public int get(int key) { DLinkedNode node cache.get(key); if (node null) { return -1; // 未命中返回-1 } // 访问后移动到头部标记为最近使用 moveToHead(node); return node.value; } // 存入缓存键值对 public void put(int key, int value) { DLinkedNode node cache.get(key); if (node null) { // 键不存在新建节点 DLinkedNode newNode new DLinkedNode(key, value); cache.put(key, newNode); addToHead(newNode); // 检查容量超出则删除最久未使用节点 if (cache.size() capacity) { DLinkedNode removedNode removeTail(); cache.remove(removedNode.key); } } else { // 键存在更新值并移动到头部 node.value value; moveToHead(node); } } // 测试示例 public static void main(String[] args) { LRUCache lru new LRUCache(3); lru.put(1, 1); lru.put(2, 2); lru.put(3, 3); System.out.println(lru.get(1)); // 输出1此时缓存[1,3,2] lru.put(4, 4); // 淘汰最久未使用的2缓存[4,1,3] System.out.println(lru.get(2)); // 输出-1已被淘汰 lru.put(3, 30); // 更新3的值移动到头部缓存[3,4,1] System.out.println(lru.get(3)); // 输出30 } }四、LRU的实际应用场景LRU不是单纯的算法题在实际开发中应用非常广泛了解这些场景能帮你更好地理解“为什么需要LRU”也能在面试中展现你的工程思维。操作系统页面置换当内存缓存满时操作系统会用LRU淘汰最久未使用的页面腾出空间给新页面这是LRU最经典的应用场景之一。缓存系统Redis、Memcached等分布式缓存都支持LRU作为缓存淘汰策略Redis默认支持LRU可通过配置开启用于淘汰长期未被访问的缓存数据提升缓存命中率。浏览器缓存浏览器会缓存最近访问的网页资源CSS、JS、图片等当缓存空间满时会用LRU淘汰最久未访问的资源加快后续页面加载速度。框架与开发工具Python的functools.lru_cache装饰器本质就是LRU缓存用于缓存函数的调用结果避免重复计算Java的LinkedHashMap底层也是用“哈希表双向链表”实现可直接用于实现LRU缓存。手机APP后台管理如前文所说手机系统会用LRU淘汰最久未使用的APP释放内存资源保证当前使用的APP流畅运行。五、LRU的局限性与优化方向LRU虽好但并非万能它也有局限性实际应用中需要根据场景进行优化这也是面试中常考的“延伸问题”。5.1 局限性缓存污染问题如果一次性访问大量“只使用一次”的数据比如批量查询历史日志会将缓存中常用的数据挤掉导致后续缓存命中率下降。缺乏时间衰减机制LRU仅基于“最近访问”判断无法区分“1小时前访问”和“1天前访问”的数据——若1天前的数据偶尔被访问一次会挤掉1小时前的高频数据。5.2 优化方案LRU-K需访问K次才进入缓存减少临时数据对缓存的污染比如K2只有被访问2次以上的数据才会被保留在缓存中常用于数据库查询缓存优化。ARC自适应替换缓存结合LRU和LFU最少使用次数的优点动态调整两者的权重平衡“访问时间”与“访问频率”解决LRU的时间衰减问题。结合TTL过期时间给缓存数据设置过期时间即使数据最近被访问过到期后也会自动淘汰避免缓存中留存无效数据。