面试必备：LRU缓存算法深度剖析与手写实现（附完整代码）

面试必备LRU缓存算法深度剖析与手写实现附完整代码引言在计算机系统中缓存无处不在。无论是CPU的L1/L2/L3缓存、数据库的Buffer Pool还是Redis这类内存数据库都在利用缓存来提升数据访问速度。然而缓存空间有限当缓存满了就需要淘汰一些数据以容纳新数据。这时缓存淘汰策略就显得至关重要。在众多淘汰策略中LRULeast Recently Used最近最少使用是面试和实际应用中最常见的一种。它基于“如果数据最近被访问过那么将来被访问的几率也更高”的假设淘汰最长时间未被访问的数据。本文将带你深入理解LRU的思想剖析双向链表哈希表的经典实现并提供完整的可运行代码让你不仅能在面试中应对自如还能真正应用于项目中。核心概念什么是LRULRU算法可以用一句话概括当缓存空间满时优先淘汰最久未被访问的数据。这里的“访问”包括读(get)和写(put)操作。每次访问某个数据该数据就变成了“最近被使用”的从而被移到淘汰队列的最末尾或最前面依实现而定。那些长时间不被访问的数据会逐步被推到“淘汰区”当需要腾出空间时就会被移除。设计需求我们需要实现一个满足如下要求的LRU缓存-get(key)如果key存在返回对应的value并将该数据标记为最近使用如果不存在返回-1或null。-put(key, value)如果key已存在更新value并将其提升为最近使用如果不存在则插入新数据。插入时若缓存已满需要先淘汰最久未使用的数据再插入。- 操作的时间复杂度必须为O(1)。哈希表可以让我们在O(1)时间内完成查找但无法处理“顺序”问题。我们需要一种数据结构能够高效地在头部和尾部进行增删并且能够在O(1)时间内将某个已存在的节点移动到头部或尾部。双向链表Doubly Linked List恰好满足这一点。为什么是双向链表 哈希表双向链表存储实际的数据节点按照访问时间排序。最近访问的节点在链表头部或尾部最久未访问的在另一端。删除节点、在头部插入节点、将任意节点移动到头部这些操作都可以在O(1)完成前提是我们有该节点的引用。哈希表建立key到链表节点的映射使得我们可以O(1)找到节点进而进行后续的指针操作。两者的组合堪称完美哈希表提供快速查找双向链表维护顺序。实战示例手写LRU缓存下面我们用Java来实现一个LRU缓存同样思路也适用于Python文末会提供Python版本。Java实现完整可运行我们设计LRUCache类构造函数传入容量capacity。内部使用HashMap存储key到节点的映射双向链表的头尾哨兵节点简化边界操作。import java.util.HashMap; import java.util.Map; public class LRUCache { // 双向链表节点类 class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; public DLinkedNode() {} public DLinkedNode(int key, int value) { this.key key; this.value value; } } private MapInteger, DLinkedNode cache new HashMap(); private int size; private int capacity; private DLinkedNode head, tail; // 哨兵节点 public LRUCache(int capacity) { this.size 0; this.capacity capacity; // 初始化头尾哨兵节点并连接 head new DLinkedNode(); tail new DLinkedNode(); head.next tail; tail.prev head; } public int get(int key) { DLinkedNode node cache.get(key); if (node null) { return -1; // 不存在 } // 访问后将该节点移动到头部表示最近使用 moveToHead(node); return node.value; } public void put(int key, int value) { DLinkedNode node cache.get(key); if (node ! null) { // key已存在更新值并移动到头部 node.value value; moveToHead(node); } else { // 创建新节点 DLinkedNode newNode new DLinkedNode(key, value); cache.put(key, newNode); addToHead(newNode); size; if (size capacity) { // 缓存满移除尾部节点最久未使用 DLinkedNode tailNode removeTail(); cache.remove(tailNode.key); size--; } } } // 将节点添加到头部虚拟头节点之后 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); // 再加到头部 } // 移除尾部节点最久未使用返回被移除的节点 private DLinkedNode removeTail() { DLinkedNode res tail.prev; removeNode(res); return res; } // 测试主函数 public static void main(String[] args) { LRUCache lru new LRUCache(2); lru.put(1, 1); // 缓存: {11} lru.put(2, 2); // 缓存: {11, 22} System.out.println(lru.get(1)); // 返回 1, 缓存: {22, 11}顺序代表最近程度 lru.put(3, 3); // 容量满淘汰key 2缓存: {11, 33} System.out.println(lru.get(2)); // 返回 -1 (不存在) lru.put(4, 4); // 容量满淘汰key 1缓存: {33, 44} System.out.println(lru.get(1)); // -1 System.out.println(lru.get(3)); // 3 System.out.println(lru.get(4)); // 4 } }代码解析- 头节点和尾节点是哨兵节点不存储实际数据这样在添加/删除时不需要判空简化了边界条件。-moveToHead是LRU的核心当一个节点被get或put更新时将其从链表中删除再插入到头部。-removeTail返回尾部的前一个节点即实际尾节点然后从哈希表中删除对应的键。- 所有操作的时间复杂度都是O(1)因为哈希表查找O(1)链表指针调整也是O(1)。Python实现简洁版同样的思路Python中使用内置的OrderedDict可以一行调用move_to_end但面试中通常要求手动实现。以下是一个基于字典和双向链表的Python版本class DLinkedNode: def __init__(self, key0, value0): self.key key self.value value self.prev None self.next None class LRUCache: def __init__(self, capacity: int): self.cache {} self.capacity capacity self.size 0 self.head DLinkedNode() self.tail DLinkedNode() self.head.next self.tail self.tail.prev self.head def get(self, key: int) - int: if key not in self.cache: return -1 node self.cache[key] self._move_to_head(node) return node.value def put(self, key: int, value: int) - None: if key in self.cache: node self.cache[key] node.value value self._move_to_head(node) else: node DLinkedNode(key, value) self.cache[key] node self._add_to_head(node) self.size 1 if self.size self.capacity: removed self._remove_tail() self.cache.pop(removed.key) self.size - 1 def _add_to_head(self, node): node.prev self.head node.next self.head.next self.head.next.prev node self.head.next node def _remove_node(self, node): node.prev.next node.next node.next.prev node.prev def _move_to_head(self, node): self._remove_node(node) self._add_to_head(node) def _remove_tail(self): node self.tail.prev self._remove_node(node) return node常见问题与注意事项1. 为什么要自己实现而不直接使用LinkedHashMapJava或OrderedDictPython面试时面试官希望考察你对数据结构的理解和DIY能力。实际项目中如果语言标准库提供了类似结构直接使用更可靠但理解其内部原理能更好地调试和优化。Java中LinkedHashMap可以设置accessOrdertrue轻松实现LRUPython的OrderedDict配合move_to_end也十分方便。2. 哨兵节点的作用很多初学者容易在头尾节点的空指针问题上犯错。使用哨兵节点后链表始终非空插入和删除操作不需要检查前后节点是否为null代码更加简洁健壮。3. 并发环境下的LRU上述实现都不是线程安全的。如果在多线程环境下使用最简单的方式是在get和put方法上添加synchronized关键字Java或加锁Python。但加锁会降低并发性能。高级方案可以使用分段锁或无锁队列但这已超出本文范围。4. LRU的一些变种LRU-K记录数据最近第K次访问的时间淘汰第K次访问时间最久的数据。比传统LRU更能抵抗“缓存污染”。Two Queues使用两条链表一条FIFO队列接收新数据另一条LRU队列存储再次被访问的数据。ARCAdaptive Replacement Cache同时跟踪LRU和LFU最少使用频率动态调整比例。5. 内存开销每个节点除了存储key和value还额外持有两个指针prev/next有一定内存开销。在实际海量数据的缓存系统中如果无法接受这种开销可以考虑其他紧凑的数据结构或者使用基于时间戳的淘汰策略精度略低但节省空间。总结LRU缓存通过哈希表双向链表的组合完美地实现了O(1)时间复杂度的get和put操作。其核心在于1. 哈希表维护键到节点的映射实现快速定位。2. 双向链表按访问时间排序支持O(1)的节点移动和删除。3. 哨兵节点简化了链表操作。本文提供的Java和Python实现都是面试中的标准答案建议你亲自手写几遍彻底掌握指针操作的细节。最终不仅能在面试中写出来还能清晰地表达设计的原理和边界情况处理这才是真正的掌握。希望这篇文章能帮助你彻底吃透LRU算法让缓存设计不再成为你的软肋。