Hot 146 LRU Cache 实现详解-深圳市維司達科技有限公司

一、问题背景

LRU（Least Recently Used）缓存是一种缓存淘汰策略：

当缓存容量满时，删除最近最少使用的数据

要求 get 和 put 操作的时间复杂度为 O(1)

二、数据结构选择

要实现 O(1) 操作，需要两种数据结构配合：

HashMap：实现 O(1) 的查找

Map<Integer, Node>：key 到节点的映射

2.双向链表：实现 O(1) 的插入和删除，维护访问顺序

头部：最近使用的节点

尾部：最近最少使用的节点

三、核心设计：虚拟头尾节点

使用虚拟头尾节点简化边界处理：

head（虚拟）<-> Node1 <-> Node2 <-> Node3 <-> tail（虚拟）
↑最近使用 ↑最近最少使用

优势：

统一处理：所有实际节点都有前驱和后继

代码简洁：不需要特殊判断边界情况

减少错误：避免空指针异常

四、完整代码实现

import java.util.*; class LRUCache { // 双向链表节点 class Node { int key; int value; Node prev; Node next; Node() {} Node(int key, int value) { this.key = key; this.value = value; } } private int capacity; private Map<Integer, Node> cache; private Node head; // 虚拟头节点 private Node tail; // 虚拟尾节点 public LRUCache(int capacity) { this.capacity = capacity; this.cache = new HashMap<>(); this.head = new Node(); this.tail = new Node(); head.next = tail; tail.prev = head; } public int get(int key) { Node node = cache.get(key); if (node == null) { return -1; } moveToHead(node); // 移到头部，标记为最近使用 return node.value; } public void put(int key, int value) { Node node = cache.get(key); if (node == null) { // key不存在，插入新节点 Node newNode = new Node(key, value); if (cache.size() >= capacity) { // 容量已满，删除最近最少使用的节点 Node lastNode = removeTail(); cache.remove(lastNode.key); } addToHead(newNode); cache.put(key, newNode); } else { // key已存在，更新值并移到头部 node.value = value; moveToHead(node); } } // 将节点添加到头部 private void addToHead(Node node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } // 移除节点 private void removeNode(Node node) { node.prev.next = node.next; node.next.prev = node.prev; } // 将节点移到头部 private void moveToHead(Node node) { removeNode(node); addToHead(node); } // 移除尾部节点（最近最少使用） private Node removeTail() { Node lastNode = tail.prev; removeNode(lastNode); return lastNode; } }

五、关键方法详解

1. get(int key) - 获取值

public int get(int key) { Node node = cache.get(key); if (node == null) { return -1; } moveToHead(node); // 关键：移到头部标记为最近使用 return node.value; }

流程：

从 HashMap 查找：O(1)
不存在返回 -1
存在则移到头部（标记为最近使用）
返回 value

2. put(int key, int value) - 插入/更新

public void put(int key, int value) { Node node = cache.get(key); if (node == null) { // 插入新节点 Node newNode = new Node(key, value); if (cache.size() >= capacity) { Node lastNode = removeTail(); cache.remove(lastNode.key); // 从HashMap中删除 } addToHead(newNode); cache.put(key, newNode); } else { // 更新已存在的节点 node.value = value; moveToHead(node); } }

两种情况：

key 不存在：创建新节点，容量满时删除尾部节点

key 已存在：更新 value 并移到头部

3. addToHead(Node node) - 添加到头部

private void addToHead(Node node){ node.prev=head; node.next=head.next; head.next.prev=node; head.next=node; }

操作步骤：

原来：head <-> node1 <-> tail
插入 node：head <-> node <-> node1 <-> tail
1. node.prev = head (node的前驱指向head)
2. node.next = head.next (node的后继指向原来的第一个节点)
3. head.next.prev = node (原来第一个节点的前驱指向node)
4. head.next = node (head的后继指向node)

4. removeNode(Node node) - 移除节点

private void removeNode(Node node){ node.prev.next=node.next; node.next.prev=node.prev; }

操作步骤：

原来：prev <-> node <-> next 删除后：prev <-> next 1. node.prev.next = node.next (前驱的后继指向node的后继) 2. node.next.prev = node.prev (后继的前驱指向node的前驱)

六、执行流程示例

假设 capacity = 2，执行以下操作：
1. put(1, 1)
cache: {1 -> Node(1,1)}
链表: head <-> Node(1,1) <-> tail
2. put(2, 2)
cache: {1 -> Node(1,1), 2 -> Node(2,2)}
链表: head <-> Node(2,2) <-> Node(1,1) <-> tail
3. get(1)
找到 Node(1,1)，移到头部
链表: head <-> Node(1,1) <-> Node(2,2) <-> tail
返回: 1
4. put(3, 3)
容量已满，删除尾部 Node(2,2)
插入新节点 Node(3,3) 到头部
cache: {1 -> Node(1,1), 3 -> Node(3,3)}
链表: head <-> Node(3,3) <-> Node(1,1) <-> tail