Leetcode LRU缓存

LRU 缓存算法思想及代码解析

算法思想

LRU（Least Recently Used，最近最少使用）缓存 需要满足以下要求：

1. 在 O(1) 时间复杂度内完成 get 和 put 操作。
2. 当缓存满时，删除最近最少使用的元素（即最久没有被访问的元素）。
3. 每次访问或插入数据，都需要将该数据提升为最近使用的状态。

为了实现这一目标，我们使用 哈希表（HashMap）+ 双向链表（Doubly Linked List） 的数据结构组合：

• 哈希表（Map<Integer, Node>）用于 O(1) 时间查找键值对。
• 双向链表 维护数据访问的顺序：
  • 最近使用的数据位于链表头部（head.next）。
  • 最久未使用的数据位于链表尾部（tail.prev）。
  • 插入、删除节点均为 O(1) 操作。

---

代码解析

1. 设计数据结构

class Node {int key, value;Node prev, next;Node(int key, int value) {this.key = key;this.value = value;}
}

• Node 结构用于双向链表，每个节点存储 key-value 键值对，并且有 prev 和 next 指针，用于快速在链表中移动。

---

2. LRUCache 构造方法

private final int capacity;
private final Map<Integer, Node> cache;
private final Node head, tail;public LRUCache(int capacity) {this.capacity = capacity;this.cache = new HashMap<>();this.head = new Node(0, 0);  // 虚拟头节点this.tail = new Node(0, 0);  // 虚拟尾节点head.next = tail;tail.prev = head;
}

• capacity：缓存的最大容量。
• cache：哈希表，存储 key -> Node，用于 O(1) 查找。
• head, tail：虚拟头尾节点，方便插入和删除操作。

---

3. get(int key) 方法

public int get(int key) {if (!cache.containsKey(key)) {return -1;}Node node = cache.get(key);moveToHead(node);return node.value;
}

逻辑：

1. 先在 cache 哈希表中查找 key，如果不存在，返回 -1。
2. 如果 key 存在，则获取 node，并调用 moveToHead(node) 将其移动到头部（标记为最近使用）。
3. 返回 node.value。

---

4. put(int key, int value) 方法

public void put(int key, int value) {if (cache.containsKey(key)) {Node node = cache.get(key);node.value = value;moveToHead(node);} else {Node newNode = new Node(key, value);cache.put(key, newNode);addToHead(newNode);if (cache.size() > capacity) {removeLRU();}}
}

逻辑：

1. 如果 key 已经存在：

   • 直接更新 node.value。
   • 调用 moveToHead(node)，将其移动到链表头部。

2. 如果 key 不存在：

   • 创建一个新节点 newNode，插入到头部（addToHead(newNode)）。
   • 在 cache 哈希表中添加新节点。
   • 如果超出 capacity，则调用 removeLRU() 删除最久未使用的节点。

---

5. moveToHead(Node node) 方法

private void moveToHead(Node node) {removeNode(node);addToHead(node);
}

逻辑：

1. 先删除该节点（removeNode(node)）。
2. 再将该节点插入到链表头部（addToHead(node)）。

这样可以保证 node 成为最近使用的数据。

---

6. addToHead(Node node) 方法

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

逻辑：

1. 将 node 插入到 head 之后：

   head -> node -> 旧的第一个节点
   

2. 调整前后指针，保证双向链表结构。

---

7. removeNode(Node node) 方法

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

逻辑：

• 直接修改 prev 和 next 指针，使 node 从链表中移除。

---

8. removeLRU() 方法

private void removeLRU() {Node lru = tail.prev;cache.remove(lru.key);removeNode(lru);
}

逻辑：

1. 找到 tail.prev（最久未使用的节点）。
2. 从 cache 哈希表中删除该节点。
3. 调用 removeNode(lru)，将其从链表中移除。

---

时间复杂度分析

• get(key)：

  • 哈希表查询 O(1)。
  • 移动到头部 O(1)。
  • 总复杂度 O(1)。

• put(key, value)：

  • 哈希表查询 O(1)。
  • 插入到头部 O(1)。
  • 超出容量时删除最久未使用节点 O(1)。
  • 总复杂度 O(1)。

综上，整个 LRUCache 的 get 和 put 都是 O(1) 复杂度，符合题目要求。

---

示例运行

public static void main(String[] args) {LRUCache cache = new LRUCache(2);cache.put(1, 1); // 缓存={1=1}cache.put(2, 2); // 缓存={1=1, 2=2}System.out.println(cache.get(1)); // 返回 1，缓存={2=2, 1=1}cache.put(3, 3); // 淘汰 2，缓存={1=1, 3=3}System.out.println(cache.get(2)); // 返回 -1（未找到）cache.put(4, 4); // 淘汰 1，缓存={3=3, 4=4}System.out.println(cache.get(1)); // 返回 -1（未找到）System.out.println(cache.get(3)); // 返回 3System.out.println(cache.get(4)); // 返回 4
}

---

总结

1. 哈希表 + 双向链表 实现 O(1) get 和 put 操作。
2. 双向链表 用于维护访问顺序：
   • 最近使用的元素放在头部。
   • 最久未使用的元素放在尾部，并在超出容量时删除。
3. 哈希表提供 O(1) 访问节点的能力，结合链表进行快速调整。

这样，我们就高效地实现了 LRU 缓存 机制！🚀

java solution

class LRUCache {//首先定义双向链表节点class Node {int key, value;Node prev, next;//构造函数Node(int key, int value) {this.key = key;this.value = value;}}private final int capacity; //这个是哈希表存储的最大节点数量//private final 确保 cache 这个哈希表 本身不会被重新赋值（但其内容可以改变）private final Map<Integer, Node> cache;//确保 头节点（head）和尾节点（tail）在 LRUCache 生命周期内不会改变private final Node head, tail;//LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存//是类 LRUCache 的构造函数//HashMap 和双向链表中的节点数据始终保持一致,HashMap的作用：O(1) 访问数据//双向链表,维护访问顺序：最近访问的节点在头部 (head.next)，最久未访问的节点在尾部 (tail.prev)//HashMap 仅存储键值对，而双向链表存储缓存的访问顺序，二者始终同步public LRUCache(int capacity) {this.capacity = capacity;this.cache = new HashMap<>();this.head = new Node(0, 0);this.tail = new Node(0, 0);head.next = tail;tail.prev = head;}public int get(int key) {if(!cache.containsKey(key)) {return -1;}Node node = cache.get(key);moveToHead(node);return node.value;}public void put(int key, int value) {if(cache.containsKey(key)) {Node node = cache.get(key);node.value = value;moveToHead(node);} else {Node node = new Node(key, value);cache.put(key, node);addToHead(node);if(cache.size() > capacity) {removeLRU();}}}private void moveToHead(Node node) {removeNode(node);addToHead(node);}private void addToHead(Node node) {//先处理nodenode.next = head.next;node.prev = head;//再处理headhead.next.prev = node;head.next = node;}private void removeNode(Node node) {node.prev.next = node.next;node.next.prev = node.prev;}private void removeLRU() {Node lru = tail.prev;cache.remove(lru.key);//先删除hashmap中的这个键值对removeNode(lru);//再从双向链表中删除掉这个节点}
}