元宝 LeetCode 146. LRU 缓存 Java实现

LeetCode 146 LRU 缓存是一道非常经典的数据结构设计题。要求“get” 和“put” 操作都在 O(1) 时间复杂度内完成。实现 O(1) 时间复杂度的核心思路是哈希表HashMap 双向链表。HashMap用于通过“key” 快速定位到链表中的节点O(1) 查找。双向链表用于维护数据的“最近使用”顺序。头部是最近使用的尾部是最久未使用的。下面提供两种 Java 实现方式。方法一手写双向链表 HashMap面试标准解法这种方式完全手动维护双向链表展示了底层原理是面试中的标准答案。思路定义双向链表节点包含“key”,“value”,“prev”,“next”。初始化设置伪头部dummy head和伪尾部dummy tail简化边界条件处理。get(key)如果 key 不存在返回 -1。如果存在通过哈希表找到节点将该节点移动到链表头部表示最近使用然后返回 value。put(key, value)如果 key 已存在更新 value并将节点移动到头部。如果 key 不存在创建新节点加入链表头部和哈希表。如果容量超限删除链表尾部节点最久未使用并从哈希表中移除对应的 key。Java 代码实现import java.util.HashMap;import java.util.Map;class LRUCache {// 1. 定义双向链表节点 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; // 伪头部最近使用的端 private DLinkedNode tail; // 伪尾部最久未使用的端 // 2. 初始化 public LRUCache(int capacity) { this.size 0; this.capacity capacity; head new DLinkedNode(); tail new DLinkedNode(); head.next tail; tail.prev head; } // 3. get 操作 public int get(int key) { DLinkedNode node cache.get(key); if (node null) { return -1; } // 将访问的节点移动到头部 moveToHead(node); return node.value; } // 4. put 操作 public void put(int key, int value) { DLinkedNode node cache.get(key); if (node ! null) { // key 存在更新值并移到头部 node.value value; moveToHead(node); } else { // key 不存在创建新节点 DLinkedNode newNode new DLinkedNode(key, value); cache.put(key, newNode); addToHead(newNode); size; // 如果超出容量删除尾部节点 if (size capacity) { DLinkedNode removedNode removeTail(); cache.remove(removedNode.key); size--; } } } // 5. 辅助方法在头部添加节点 private void addToHead(DLinkedNode node) { node.prev head; node.next head.next; head.next.prev node; head.next node; } // 6. 辅助方法移除节点 private void removeNode(DLinkedNode node) { node.prev.next node.next; node.next.prev node.prev; } // 7. 辅助方法将节点移动到头部 private void moveToHead(DLinkedNode node) { removeNode(node); addToHead(node); } // 8. 辅助方法删除尾部节点并返回 private DLinkedNode removeTail() { DLinkedNode node tail.prev; removeNode(node); return node; }}方法二继承 LinkedHashMap工程/偷懒写法Java 标准库中的“LinkedHashMap” 本身就维护了一个按访问顺序accessOrder排列的双向链表。通过重写“removeEldestEntry” 方法可以非常简洁地实现 LRU 缓存。注意面试时通常要求手写方法一但在实际项目或竞赛中这种写法既优雅又不易出错。import java.util.LinkedHashMap;import java.util.Map;class LRUCache extends LinkedHashMapInteger, Integer {private int capacity;public LRUCache(int capacity) { // 参数初始容量负载因子accessOrdertrue 表示按访问顺序排序 super(capacity, 0.75f, true); this.capacity capacity; } public int get(int key) { // 如果找不到返回 -1 return super.getOrDefault(key, -1); } public void put(int key, int value) { super.put(key, value); } // 当插入新元素且 size capacity 时LinkedHashMap 会自动调用此方法 // 返回 true 则会删除最久未使用的元素即链表头部的元素 Override protected boolean removeEldestEntry(Map.EntryInteger, Integer eldest) { return size() capacity; }}复杂度分析时间复杂度“get” 和“put” 操作均为 O(1)。哈希表的增删改查是 O(1)双向链表的节点移动和删除也是 O(1)。空间复杂度O(capacity)哈希表和双向链表最多存储“capacity 1” 个元素。如果你对双向链表的指针操作或“LinkedHashMap” 的底层机制有疑问我可以单独为你拆解讲解