146.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) 的平均时间复杂度运行。
示例：
输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
提示：
1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 10^5
最多调用 2 * 10^5 次 get 和 put
思路：
1. LRU 缓存（Least Recently Used）要求：
- 有一个固定容量
capacity的缓存。 - 每次访问某个 key（
get或put），这个 key 都会变成“最近使用”的。 - 超过容量时，删除最久未使用的 key。
get和put要求平均 O(1) 时间复杂度。
所以本质上，需要维护两方面的数据结构：
数据的顺序：
- 用双向链表维护 key 的使用顺序，
链表头表示最近使用，链表尾表示最久未使用。 - 将一个节点移到链表头可以分成两步：
- 删除该节点（O(1)）
- 在链表头插入该节点（O(1)）
- 删除最久未使用的节点（链表尾）同样是 O(1)。
- 用双向链表维护 key 的使用顺序，
快速查找 key：
- 使用哈希表
map[key] -> node，保证get操作可以在 O(1) 时间直接找到对应节点，然后链表节点数据部分存储了键值对 entry 结构，根据 key 找到 value。 put操作时，- 如果 key 已存在，同样可以在 O(1) 时间通过哈希表找到节点并更新；
- 如果 key 不存在，也可以通过
哈希表当前长度快速判断是否超过容量。
- 使用哈希表
即：
get操作：查哈希表 + 移动节点到头部 → O(1)put操作：查哈希表 + 插入/更新节点 + 删除尾部节点（如超过容量） → O(1)
因此，通过「哈希表 + 双向链表」的组合，LRU 缓存能够在平均 O(1) 时间完成 get 和 put 操作，同时维护最近使用顺序。
2. 核心数据结构
为实现上述要求，经典做法是 哈希表 + 双向链表：
| 数据结构 | 作用 |
|---|---|
哈希表 map[key] -> node |
通过 key 快速找到对应节点，O(1) 查找 |
| 双向链表 | 保存使用顺序：链表头是最近使用，链表尾是最久使用。可以 O(1) 删除和插入节点 |
解释：
- 双向链表比单向链表合适，因为需要删除操作。删除一个节点不光要得到该节点本身的指针，也需要操作其前驱节点的指针，而
双向链表才能支持直接查找前驱，保证操作的时间复杂度 O(1)。 - 链表头：
最近使用的元素。 - 链表尾：
最久未使用的元素。当缓存满了，要删除的就是链表尾节点。 - 哈希表：直接通过 key 找到链表节点，无需遍历。
3. 注意点
最近使用的定义：
- 不管是
get还是put，访问过的 key 都算最近使用。 - 如果两个 key 都没被访问过，插入时间更晚的那个算最近使用（链表头）。
- 不管是
虚拟头尾节点：
- 用虚拟头尾节点可以简化链表操作，不需要判断头尾是否为空。
- 虚拟节点不是必需的，但面试写链表时非常常用，减少逻辑错误。
容量限制：
- 插入前判断长度是否超过 capacity，如果超过，要删除链表尾节点，同时删除哈希表记录。
实现（Go）：
- 使用哈希表快速查找 key
map[key]*list.Element，可以在 O(1) 时间找到链表中的节点。
- 使用双向链表维护访问顺序
- Go 的
container/list是双向链表。- 链表头表示最近使用（Most Recently Used）。
- 链表尾表示最久未使用（Least Recently Used）。
- 访问操作（get）
- 查找 key 对应的节点，如果存在，把它移动到链表头（表示最近使用），返回值。
- 如果不存在，返回 -1。
- 插入/更新操作（put）
- 如果 key 已存在：
- 更新 value
- 移动到链表头
- 如果 key 不存在：
- 判断是否超出容量
- 如果没有：
- 插入新节点到链表头
- 如果超出：
- 插入新节点到链表头
- 删除链表尾节点（最久未使用）
- 同时从哈希表删除对应 key
使用结构体类型 List 表示双向链表
List 讲解
包和类型
import "container/list" // 引入 Go 内置双向链表包
// List 表示整个双向链表
type List struct {
root Element // 哨兵节点（循环链表，简化边界处理，头尾不为 nil）
len int // 链表长度
}
// Element 表示链表中的一个节点
type Element struct {
Next, Prev *Element // 前驱和后继节点指针
list *List // 指向所属链表
Value interface{} // 节点存储的值，可以是任意类型
}
说明：
Value可以存任意类型，Go 用interface{}实现泛型效果。- 内部使用循环哨兵节点，空链表时
root.Next和root.Prev都指向root本身，操作无需处理特殊情况。
常用操作
创建
l := list.New() // *list.List 类型，表示整个链表
// 内部结构：
type List struct {
root Element // 哨兵节点，root.Next是头节点，root.Prev是尾节点
len int // 链表长度
}
插入
l.PushFront(v) // 在链表头插入值 v，返回新节点 *Element
l.PushBack(v) // 在链表尾插入值 v，返回新节点 *Element
- 时间复杂度：O(1)
- 特点：直接操作指针，无需遍历链表。
- 返回值：新插入的节点，可以用来快速删除或移动。
删除
l.Remove(e) // 删除节点 e（*Element）
- 时间复杂度：O(1)
- 说明：通过节点指针直接删除，无需遍历链表。
- 注意：删除后节点的
Next、Prev指针会被清空，防止误用。
移动节点
l.MoveToFront(e) // 将节点 e 移动到链表头部
l.MoveToBack(e) // 将节点 e 移动到链表尾部
本质操作：
- 从当前位置删除节点（O(1)）
- 在新位置插入节点（O(1)）
访问头尾节点
l.Front() // 返回链表头节点 *Element
l.Back() // 返回链表尾节点 *Element
- 访问值：
e.Value - 链表为空：返回
nil
代码实现：
力扣提交需自行注释或者去掉 包声明、导入部分以及Go 程序的入口 main 函数。
package main
import (
"container/list"
"fmt"
)
// entry 结构表示缓存中的一条记录
// key: 缓存的 key
// value: 缓存的 value
type entry struct {
key, value int
}
// LRUCache 数据结构，一个整体容器
// 存储 容量、双向链表（维护访问顺序）、哈希表（快速访问），实现 LRU 缓存
type LRUCache struct {
capacity int // 缓存容量
cacheList *list.List // 双向链表，维护使用顺序，头是最近使用，尾是最久未使用
keyToNode map[int]*list.Element // 哈希表，快速通过 key 查找对应的链表节点
}
// 构造函数，初始化 LRU 缓存
func Constructor(capacity int) LRUCache {
return LRUCache{
capacity: capacity,
cacheList: list.New(), // 创建一个空的双向链表
keyToNode: make(map[int]*list.Element), // 创建空哈希表
}
}
// Get 方法：获取 key 的值，如果不存在返回 -1
func (c *LRUCache) Get(key int) int { // c：方法的指针接收者 (*LRUCache)：修改会影响原对象。
node := c.keyToNode[key] // O(1) 哈希表查找
if node == nil {
return -1 // key 不存在
}
// key 存在，将节点移动到链表头，表示最近使用
c.cacheList.MoveToFront(node) // O(1)，删除 + 插入头部
return node.Value.(entry).value
// 1. 取出链表节点 node 的 Value（类型是 interface{}）
// 2. 把 node.Value 从 interface{} 类型断言成 entry 类型
// 3. 访问 entry 里的 value 字段
// 4. 返回结果（就是缓存的值）
}
// Put 方法：插入或更新 key-value
func (c *LRUCache) Put(key int, value int) {
if node := c.keyToNode[key]; node != nil {
// key 已存在
c.cacheList.MoveToFront(node) // 把节点移动到链表头，表示最近使用
node.Value = entry{key, value} // 更新 value
return
}
// key 不存在，创建新节点，放到链表头
newNode := c.cacheList.PushFront(entry{key, value}) // O(1)
c.keyToNode[key] = newNode // 更新哈希表
// 如果超出容量，需要删除最久未使用的节点（链表尾部）
if c.cacheList.Len() > c.capacity {
backNode := c.cacheList.Back() // 获取尾节点 O(1)
c.cacheList.Remove(backNode) // 从链表中删除 O(1)
delete(c.keyToNode, backNode.Value.(entry).key) // 从哈希表中删除 O(1)
}
}
func main() {
cache := Constructor(2) // 容量为 2
cache.Put(1, 1) // 缓存 {1=1}
cache.Put(2, 2) // 缓存 {2=2, 1=1}
fmt.Println(cache.Get(1)) // 返回 1，缓存更新为 {1=1, 2=2}
cache.Put(3, 3) // 插入 3=3, 删除最久未使用 key=2, 缓存 {3=3, 1=1}
fmt.Println(cache.Get(2)) // 返回 -1, key=2 已被删除
cache.Put(4, 4) // 插入 4=4, 删除最久未使用 key=1, 缓存 {4=4, 3=3}
fmt.Println(cache.Get(1)) // 返回 -1
fmt.Println(cache.Get(3)) // 返回 3, 缓存更新为 {3=3, 4=4}
fmt.Println(cache.Get(4)) // 返回 4, 缓存更新为 {4=4, 3=3}
}
内置函数 delete
在 Go 里，，用来从 map 中删除指定的键值对。
语法
delete(map, key)
map：要操作的 mapkey：要删除的键
删除后：
map[key]再访问就是零值（如果是指针就是nil，如果是 int 就是0等）- map 长度减少 1
双向链表的删除插入
删除节点x：
前节点（prev）的 next 指向当前节点的 next
后节点（next）的 prev 指向当前节点的 prev
在头部插入节点x：
新节点的 prev 指向 虚拟头节点。
新节点的 next 指向 虚拟头节点的下一个节点（原第一个节点）。
虚拟头节点的 next 指向新节点。
原第一个节点的 prev 指向新节点。