本文详细介绍了LRU（最近最少使用）缓存淘汰算法，并通过实际代码展示了如何在面试中手写LRU Cache。核心数据结构是哈希链表，即LinkedHashMap，确保了O(1)的平均时间复杂度。文章还提醒面试者面对不熟悉的问题时，可以考虑换题或请求提示。

### LRU缓存淘汰算法及其实现 LRU（Least Recently Used）是一种常见的缓存淘汰策略，其核心思想是移除最长时间未被使用的数据项。为了实现在 **O(1)** 时间复杂度下完成 `get` 和 `put` 操作，通常会结合哈希表和双向链表来构建自定义的 LRUCache 数据结构。 #### 基于 LinkedHashMap 的实现 Java 中的 `LinkedHashMap` 是一种内置支持顺序特性的哈希映射容器，默认可以按照插入顺序或者访问顺序维护键值对的关系。通过重写 `removeEldestEntry()` 方法，可以在容量超过指定大小时自动移除最早插入或最近最少使用的条目[^1]。 以下是基于 Java 的 `LinkedHashMap` 实现： ```java import java.util.LinkedHashMap; import java.util.Map; public class LRUCache<K, V> extends LinkedHashMap<K, V> { private final int capacity; public LRUCache(int capacity) { super(capacity, 0.75f, true); // accessOrder=true 表示按访问顺序排列 this.capacity = capacity; } @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > capacity; // 超过容量则移除最早的条目 } } ``` 上述代码利用了 `LinkedHashMap` 提供的功能，简化了手动管理双向链表的过程。然而，在实际面试场景中，可能不会允许直接使用此类工具类，而是要求完全手工实现整个逻辑。 --- #### 手工实现 O(1) 时间复杂度的 LRUCache 当无法依赖现有库函数时，可以通过组合 **哈希表** 和 **双向链表** 来达到目标效果。具体来说： - 使用哈希表快速定位某个节点是否存在； - 双向链表用来记录各个节点的访问次序，靠近头部的是较早访问过的元素，而尾部则是最新操作的对象。 下面是完整的 Java 版本的手动实现方案： ```java class Node<K, V> { K key; V value; Node<K, V> prev; Node<K, V> next; public Node(K key, V value) { this.key = key; this.value = value; } } public class CustomLRUCache<K, V> { private Map<K, Node<K, V>> cacheMap; private int capacity; private Node<K, V> head; // 最久未使用的节点 private Node<K, V> tail; // 最近使用的节点 public CustomLRUCache(int capacity) { this.cacheMap = new HashMap<>(); this.capacity = capacity; this.head = null; this.tail = null; } public V get(K key) { if (!cacheMap.containsKey(key)) { return null; } Node<K, V> node = cacheMap.get(key); moveToTail(node); // 将当前节点移到队列末尾表示刚访问过它 return node.value; } public void put(K key, V value) { if (capacity <= 0) return; if (cacheMap.containsKey(key)) { // 如果已存在，则更新值并将该节点移动到队列末尾 Node<K, V> existingNode = cacheMap.get(key); existingNode.value = value; moveToTail(existingNode); } else { // 否则创建新的节点并加入缓存 if (cacheMap.size() >= capacity) { // 若超出了最大容量，则删除头结点对应的旧数据 evictHead(); } Node<K, V> newNode = new Node<>(key, value); addToTail(newNode); // 新增节点放到最后面 cacheMap.put(key, newNode); } } private void moveToTail(Node<K, V> node) { if (node == tail) return; // 已经处于尾巴位置无需调整 if (node.prev != null) { node.prev.next = node.next; } if (node.next != null) { node.next.prev = node.prev; } if (head == node) { // 更新头指针指向下一个节点 head = node.next; } addAsNewTail(node); // 把这个节点重新挂载到最后作为最新的访问者 } private void addAsNewTail(Node<K, V> node) { if (tail != null) { tail.next = node; node.prev = tail; } tail = node; if (head == null) { // 初始状态设置头等于尾 head = node; } node.next = null; // 确保新尾节点没有后续链接关系 } private void evictHead() { if (head == null) return; cacheMap.remove(head.key); if (head == tail) { // 单一节点情况特殊处理 head = null; tail = null; } else { head = head.next; head.prev = null; } } } ``` 以上代码实现了基本功能需求，并且每次调用 `get` 或 `put` 方法都能保持平均时间复杂度为 **O(1)** 。这是因为所有的关键操作——查找、插入、删除——都可以借助哈希表与双端链表高效完成[^4]。 --- #### 总结 无论是采用标准库中的高级组件还是自行搭建基础架构，理解底层原理始终至关重要。对于技术岗位候选人而言，能够清晰阐述为何选用特定设计方案以及如何平衡性能指标显得尤为重要。