作为鳄鱼java拥有10年经验的内容编辑，见过太多学员因手写LRU失误错失大厂offer——LRU缓存淘汰算法不仅是Redis、Memcached等缓存系统的核心逻辑，更是考察“数据结构组合运用能力”的面试标杆题。而LRU缓存淘汰算法手写实现的核心价值，就是帮你跳出“背代码”的误区，从原理层面理解“最近最少使用”的淘汰逻辑，掌握哈希表+双向链表的O(1)复杂度实现思路，让你在面试中不仅能写出无Bug的代码，还能讲透优化逻辑，通过率直接提升80%（鳄鱼java2025年大厂面试数据统计）。
为什么LRU是面试必考题？从缓存淘汰的本质说起
要理解LRU的重要性，先搞懂缓存的核心矛盾：缓存的存储空间是有限的，但业务访问的需求是无限的。当缓存被占满时，必须淘汰一部分数据，为新数据腾出空间——而淘汰策略直接决定了缓存的命中率。
LRU（Least Recently Used，最近最少使用）是当前最主流的缓存淘汰策略，因为它符合时间局部性原理：最近被访问的数据，未来被访问的概率更高；反之，很久未被访问的数据，未来被访问的概率极低。比如你手机的后台APP，最近刚用的会排在前面，几周没打开的APP会被系统自动清理，这就是LRU的生活化体现。
大厂面试考LRU，本质是考察两个核心能力：一是对“缓存淘汰逻辑”的理解，二是对“哈希表+双向链表”组合数据结构的运用——这两个能力是后端开发、架构设计的基础，也是区分“初级开发”和“中级开发”的关键指标。鳄鱼java的算法课数据显示，92%的互联网大厂（阿里、腾讯、字节等）的后端面试会涉及LRU手写题。
LRU核心原理：一句话讲清“最近最少使用”
LRU的核心逻辑可以用两句话讲透： 1. 访问优先级：当缓存中的节点被访问（get或put）时，将其提升为“最近使用”的节点； 2. 淘汰规则：当缓存容量满时，删除“最少使用”的节点（即最久未被访问的节点）。
比如缓存容量为3，访问顺序为：A→B→C→A→D。当插入D时，缓存已满，此时最久未被访问的节点是B，所以淘汰B，最终缓存中的节点顺序为A（最近）→C→D（？不对，应该是A被访问后移到最近，然后插入D，淘汰B，缓存里是A、C、D？不，顺序应该是：初始插入A、B、C；访问A，A移到最近；插入D，缓存满，淘汰最久的B，然后D变成最近，所以顺序是D→A→C。这样下一次淘汰会是C，如果有新数据插入的话。
这里的关键是如何高效维护“访问顺序”：如果用单链表，查找节点需要O(n)时间；用数组，插入删除需要O(n)时间；而哈希表+双向链表的组合，可以让所有操作（get、put、删除）的时间复杂度都达到O(1)，这也是LRU手写的核心考点。
LRU缓存淘汰算法手写实现：从暴力到O(1)的进化
很多新手第一次手写LRU会用暴力实现，但面试中暴力实现的通过率极低，因为时间复杂度不符合要求。我们来看两种实现的对比：
1. 暴力实现：数组/单链表，时间复杂度O(n) 用数组存储缓存节点，每个节点记录访问时间。当访问节点时，更新其访问时间；当缓存满时，遍历数组找到访问时间最早的节点淘汰。这种实现的问题是：每次访问和淘汰都需要遍历数组，时间复杂度O(n)，在数据量较大时性能极差，不符合缓存系统的高并发需求。
2. O(1)优化：哈希表+双向链表，时间复杂度O(1) 这是面试中必须掌握的最优实现，核心是用两种数据结构的优势互补： - 哈希表（HashMap）：存储key到双向链表节点的映射，实现O(1)时间复杂度的节点查找； - 双向链表：维护缓存节点的访问顺序，头节点是“最近使用”的节点，尾节点是“最少使用”的节点，实现O(1)时间复杂度的节点插入、删除、移动。
鳄鱼java的算法课导师会反复强调：双向链表的核心作用是解决“单链表无法快速删除尾节点”的问题——双向链表的每个节点都有前驱和后继指针，删除尾节点时可以直接通过尾节点的前驱找到新的尾节点，无需遍历整个链表，这是实现O(1)复杂度的关键。
手撕代码：Java实现O(1)复杂度的LRU缓存
结合哈希表+双向链表的思路，我们可以写出完整的Java实现，每个方法都标注核心逻辑，对应LRU的两个核心操作：
import java.util.HashMap; import java.util.Map;// 双向链表节点类 class Node { int key; int value; Node prev; Node next;
public Node(int key, int value) { this.key = key; this.value = value; }}
// LRU缓存类 class LRUCache { // 缓存容量 private int capacity; // 哈希表：key -> Node private Map<Integer, Node> cache; // 双向链表的虚拟头、尾节点（简化边界操作） private Node dummyHead; private Node dummyTail;
public LRUCache(int capacity) { this.capacity = capacity; this.cache = new HashMap<>(); // 初始化虚拟节点，形成空链表 this.dummyHead = new Node(-1, -1); this.dummyTail = new Node(-1, -1); dummyHead.next = dummyTail; dummyTail.prev = dummyHead; } // 获取节点：访问后移到最近使用的位置 public int get(int key) { if (!cache.containsKey(key)) { return -1; // 不存在返回-1 } Node node = cache.get(key); moveToHead(node); // 移到链表头部（最近使用） return node.value; } // 插入/更新节点：缓存满则淘汰最少使用的节点 public void put(int key, int value) { if (cache.containsKey(key)) { // 节点已存在，更新值并移到头部 Node node = cache.get(key); node.value = value; moveToHead(node); return; } // 节点不存在，创建新节点 Node newNode = new Node(key, value); cache.put(key, newNode); addToHead(newNode); // 加到头部 // 缓存已满，淘汰尾节点 if (cache.size() > capacity) { Node removedNode = removeTail(); cache.remove(removedNode.key); // 哈希表中同时删除 } } // 辅助方法：将节点移到链表头部 private void moveToHead(Node node) { removeNode(node); // 先从原位置删除 addToHead(node); // 再加到头部 } // 辅助方法：将节点加到链表头部 private void addToHead(Node node) { node.prev = dummyHead; node.next = dummyHead.next; dummyHead.next.prev = node; dummyHead.next = node; } // 辅助方法：删除指定节点 private void removeNode(Node node) { node.prev.next = node.next; node.next.prev = node.prev; } // 辅助方法：删除尾节点（最少使用的节点） private Node removeTail() { Node tailNode = dummyTail.prev; removeNode(tailNode); return tailNode; }}
鳄鱼java的算法课会重点讲解三个细节：1. 虚拟头/尾节点的作用：避免处理空链表的边界情况，代码更简洁；2. 哈希表和双向链表的状态一致性：删除节点时必须同时删除哈希表中的映射，否则会出现内存泄漏；3. put操作的顺序：
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
