LRU（Least Recently Used，最近最少使用）缓存淘汰策略的核心是：当缓存容量满时，淘汰最久未被使用的元素。在 Java 中，最优实现方式是结合HashMap（快速查找）和LinkedList/LinkedHashMap（维护访问顺序），其中LinkedHashMap是官方推荐的简化实现方式，而手动实现双链表 + 哈希表能更深入理解底层原理。
一、核心原理
- 数据结构选择：
- 哈希表（HashMap）：存储「键 - 节点」映射，实现 O (1) 时间复杂度的查找 / 更新。
- 双向链表：维护节点的访问顺序，头部为最近使用的节点，尾部为最久未使用的节点。
- 核心操作：
get(key)：若键存在，将节点移到链表头部（标记为最近使用），返回值；若不存在，返回 -1。put(key, value)：
- 若键存在，更新值并将节点移到链表头部；
- 若键不存在，创建新节点并插入链表头部，同时存入哈希表；
- 若缓存容量超限，删除链表尾部节点（最久未使用），并从哈希表中移除对应键。
二、手动实现（链表 + HashMap）
手动实现能清晰体现 LRU 的核心逻辑，也是面试高频考点：
import java.util.HashMap; import java.util.LinkedList; import java.util.Map; public class LRUCache<K, V> { private final int capacity; // 缓存容量 private final Map<K, V> cache; // 缓存键值对 private final LinkedList<K> keyList; // 维护key的访问顺序（尾部=最近使用，头部=最久未使用） // 初始化：校验容量合法性 public LRUCache(int capacity) { if (capacity <= 0) { throw new IllegalArgumentException("缓存容量必须大于0"); } this.capacity = capacity; this.cache = new HashMap<>(capacity); this.keyList = new LinkedList<>(); } // put操作：存入/更新key-value，保证O(1)核心逻辑（仅修复逻辑，未优化性能） public synchronized void put(K key, V value) { // 1. 若key已存在：先移除keyList中的旧位置，再删除缓存旧值 if (cache.containsKey(key)) { keyList.remove(key); // 注意：此处仍为O(n)，后续优化会解决 cache.remove(key); } // 2. 若缓存已满：删除最久未使用的key（链表头部） if (cache.size() >= capacity) { K oldestKey = keyList.removeFirst(); cache.remove(oldestKey); } // 3. 存入新值，并将key加入链表尾部（标记为最近使用） cache.put(key, value); keyList.addLast(key); } // get操作：获取value并更新访问顺序 public synchronized V get(K key) { // 1. 缓存中不存在key，返回null if (!cache.containsKey(key)) { return null; } // 2. 存在key：更新访问顺序（移除旧位置，加入尾部） keyList.remove(key); // 此处仍为O(n)，后续优化会解决 keyList.addLast(key); return cache.get(key); } // 辅助方法：打印缓存和keyList（用于测试） public void printCache() { System.out.println("缓存内容：" + cache); System.out.println("key访问顺序：" + keyList); } // 测试示例 public static void main(String[] args) { LRUCache<Integer, String> lru = new LRUCache<>(2); lru.put(1, "A"); lru.put(2, "B"); lru.printCache(); // 缓存：{1=A, 2=B}，keyList：[1,2] lru.get(1); // 访问1，更新顺序 lru.printCache(); // 缓存：{1=A, 2=B}，keyList：[2,1] lru.put(3, "C"); // 容量满，删除最久未使用的2 lru.printCache(); // 缓存：{1=A, 3=C}，keyList：[1,3] lru.put(1, "AA"); // 更新1的值，更新顺序 lru.printCache(); // 缓存：{1=AA, 3=C}，keyList：[3,1] } }三、性能优化：解决 LinkedList.remove (key) 的 O (n) 问题
要让get/put操作真正达到 O (1) 时间复杂度，需替换 LinkedList 为「双向链表 + 哈希表记录节点」（即我之前提到的手动实现双链表方案）。以下是优化后的最终版本：
import java.util.HashMap; import java.util.Map; public class LRUCache<K, V> { // 双向链表节点：存储key、value，以及前驱/后继节点 private static 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; } } private final int capacity; // 缓存容量 private final Map<K, Node<K, V>> nodeMap; // key -> 节点（O(1)查找） private final Node<K, V> head; // 虚拟头节点（最近使用） private final Node<K, V> tail; // 虚拟尾节点（最久未使用） // 初始化：虚拟头尾节点相连，避免空指针 public LRUCache(int capacity) { if (capacity <= 0) { throw new IllegalArgumentException("缓存容量必须大于0"); } this.capacity = capacity; this.nodeMap = new HashMap<>(capacity); this.head = new Node<>(null, null); this.tail = new Node<>(null, null); head.next = tail; tail.prev = head; } // put操作：存入/更新key-value（O(1)时间复杂度） public synchronized void put(K key, V value) { Node<K, V> node = nodeMap.get(key); if (node != null) { // 1. key已存在：更新value，并移到头部（最近使用） node.value = value; moveToHead(node); return; } // 2. key不存在：创建新节点 Node<K, V> newNode = new Node<>(key, value); nodeMap.put(key, newNode); addToHead(newNode); // 3. 缓存已满：删除尾节点（最久未使用） if (nodeMap.size() > capacity) { Node<K, V> tailNode = removeTail(); nodeMap.remove(tailNode.key); } } // get操作：获取value并更新访问顺序（O(1)时间复杂度） public synchronized V get(K key) { Node<K, V> node = nodeMap.get(key); if (node == null) { return null; } // 移到头部，标记为最近使用 moveToHead(node); return node.value; } // ========== 双向链表辅助方法（均为O(1)操作） ========== // 将节点添加到虚拟头节点之后（最近使用位置） private void addToHead(Node<K, V> node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } // 移除指定节点 private void removeNode(Node<K, V> node) { node.prev.next = node.next; node.next.prev = node.prev; } // 将节点移到头部（先移除，再添加） private void moveToHead(Node<K, V> node) { removeNode(node); addToHead(node); } // 移除尾节点（最久未使用） private Node<K, V> removeTail() { Node<K, V> tailNode = tail.prev; removeNode(tailNode); return tailNode; } // 辅助方法：打印缓存（用于测试） public void printCache() { StringBuilder sb = new StringBuilder(); Node<K, V> cur = head.next; while (cur != tail) { sb.append(cur.key).append("=").append(cur.value).append(", "); cur = cur.next; } System.out.println("缓存内容（最近使用→最久未使用）：" + sb); } // 测试示例 public static void main(String[] args) { LRUCache<Integer, String> lru = new LRUCache<>(2); lru.put(1, "A"); lru.put(2, "B"); lru.printCache(); // 1=A, 2=B lru.get(1); lru.printCache(); // 2=B, 1=A（1移到最近使用） lru.put(3, "C"); lru.printCache(); // 1=A, 3=C（删除最久未使用的2） lru.put(1, "AA"); lru.printCache(); // 3=C, 1=AA（更新1并移到最近使用） } }
