.jpg)
676 字
3 分钟
LRU 缓存
题目描述
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity)以 正整数 作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
解题思路
- 数据结构设计：
- 双向链表：维护访问顺序（头节点最新访问，尾节点最久未用）
- 哈希表：实现 O(1) 的键值查找
- 核心操作：
- 访问元素：将节点移至链表头部（
get操作） - 添加元素：
- 键存在：更新值并移至头部
- 键不存在：创建节点插入头部，超容时删除尾部节点
- 访问元素：将节点移至链表头部（
- 链表操作：
- 删除节点：直接调整前后指针
- 插入头部：头节点后插入新节点
- 容量管理：
- 维护精确尺寸计数
- 淘汰策略：删除尾部节点并移除哈希表对应项
关键洞察
- 双向链表优势：支持 O(1) 时间删除任意节点（单链表无法做到）
- 哈希表定位：通过键直接定位链表节点，避免遍历查找
- 保护节点设计：
- 头部保护节点（
head）简化插入操作 - 尾部保护节点（
tail）简化删除操作
- 头部保护节点（
- 访问即更新：任何
get成功操作自动更新节点为最新使用 - 尺寸同步：显式维护
size避免依赖Map.size计算
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
get | O(1) | O(capacity) |
put | O(1) | O(capacity) |
总空间复杂度：双向链表 O(n) + 哈希表 O(n) = O(n)，其中 n 为缓存容量
代码实现
class Node { constructor(key, value) { this.key = key; this.value = value; this.prev = this.next = null; }}class LRUCache { constructor(capacity) { this.capacity = capacity; this.size = 0; this.map = new Map(); this.head = new Node(); this.tail = new Node(); this.head.next = this.tail; this.tail.prev = this.head; } get(key) { if (!this.map.get(key)) return -1; const node = this.map.get(key); this.moveToHead(node); return node.value } put(key, value) { if (this.map.has(key)) { const node = this.map.get(key); node.value = value; this.moveToHead(node); } else { if (this.size === this.capacity) { this.removeTail(); } const newNode = new Node(key, value); this.map.set(key, newNode); this.addToHead(newNode); this.size++; } } addToHead(node) { node.prev = this.head; node.next = this.head.next; this.head.next.prev = node; this.head.next = node; } moveToHead(node) { this.removeNode(node); this.addToHead(node); } removeNode(node) { node.prev.next = node.next; node.next.prev = node.prev; } removeTail() { const tailNode = this.tail.prev; this.removeNode(tailNode); this.map.delete(tailNode.key); this.size--; }}