LRU 缓存

怎样从“容量 2 的 LRU:put(1,1),put(2,2),get(1),put(3,3) 后 2 被淘汰。”推导出 设计 · LRU，并证明每次状态变化都不会漏掉答案？

中心结论：哈希表 O(1) 定位结点 + 双向链表维护使用顺序;超容删尾,访问/更新移头。

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。 实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

在本站主例中，容量 2 的 LRU:put(1,1),put(2,2),get(1),put(3,3) 后 2 被淘汰。

算法最终需要得到或观察：get(1) 命中;put(3) 后 key=2 不在 cache。

只用一种结构往往让某个操作退化为线性；组合结构让查找、更新和顺序维护共享同一份状态。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“数据结构控制台”，明确答案需要观察什么。
2. 2状态只维护 map(key→node)、链表 head/tail、容量。
3. 3转移每一步按照 哈希表 O(1) 定位结点 + 双向链表维护使用顺序;超容删尾,访问/更新移头。
4. 4收尾读取 get(1) 命中;put(3) 后 key=2 不在 cache。，并复核边界与复杂度。

为每个操作写出复杂度目标，再反推需要组合哪些数据结构。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：map(key→node)、链表 head/tail、容量。

这一题是 LRU 经典面试题，详细解释见第三章 LRUCache 模板。

哈希表 O(1) 定位结点 + 双向链表维护使用顺序;超容删尾,访问/更新移头。

执行过程中持续维护：map(key→node)、链表 head/tail、容量。

正确性依赖以下不变量：链表头 MRU、尾 LRU;map 与链表结点一一对应。

面试时可以压缩为：HashMap+双向链表:get/put 把结点移到头部,超容 removeTail;Java LinkedHashMap 或手写 DLL。

落到当前题，执行机制可以压缩为：哈希表 O(1) 定位结点 + 双向链表维护使用顺序;超容删尾,访问/更新移头。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入容量 2 的 LRU:put(1,1),put(2,2),get(1),put(3,3) 后 2 被淘汰。 因为：哈希表 O(1) 定位结点 + 双向链表维护使用顺序;超容删尾,访问/更新移头。
2. 2哈希表 + 双向链表(此处用 order 数组模拟)O(1) get/put 的关键结构。 因为：map 定位,链表维护使用时间。
3. 3put(2,2),移到 MRU写入并刷新位置。 因为：超容量 pop LRU。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 5get(1) 命中 → 1返回值并刷新。 因为：get 也是访问,需更新 LRU。
6. 6put(3,3),淘汰 LRU key=2写入并刷新位置。 因为：超容量 pop LRU。
7. 7LRU 操作序列完成结构稳定 O(1)。 因为：经典 LRU 设计。
8. 8收尾与复杂度get(1) 命中;put(3) 后 key=2 不在 cache。 因为：时间 O(1) 各操作 · 空间 O(capacity)。哈希表 O(1) 定位结点 + 双向链表维护使用顺序;超容删尾,访问/更新移头。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

type LRUCache struct {
	head, tail *Node
	Keys       map[int]*Node
	Cap        int
}

type Node struct {
	Key, Val   int
	Prev, Next *Node
}

func Constructor(capacity int) LRUCache {
	return LRUCache{Keys: make(map[int]*Node), Cap: capacity}
}

func (this *LRUCache) Get(key int) int {
	if node, ok := this.Keys[key]; ok {
		this.Remove(node)
		this.Add(node)
		return node.Val
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	if node, ok := this.Keys[key]; ok {
		node.Val = value
		this.Remove(node)
		this.Add(node)
		return
	} else {
		node = &Node{Key: key, Val: value}
		this.Keys[key] = node
		this.Add(node)
	}
	if len(this.Keys) > this.Cap {
		delete(this.Keys, this.tail.Key)
		this.Remove(this.tail)
	}
}

func (this *LRUCache) Add(node *Node) {
	node.Prev = nil
	node.Next = this.head
	if this.head != nil {
		this.head.Prev = node
	}
	this.head = node
	if this.tail == nil {
		this.tail = node
		this.tail.Next = nil
	}
}

func (this *LRUCache) Remove(node *Node) {
	if node == this.head {
		this.head = node.Next
		node.Next = nil
		return
	}
	if node == this.tail {
		this.tail = node.Prev
		node.Prev.Next = nil
		node.Prev = nil
		return
	}
	node.Prev.Next = node.Next
	node.Next.Prev = node.Prev
}

func main() {
    // 1. 主例
    //    输入：mode="lru-cache", capacity=2, ops=["put 1 1","put 2 2","get 1","put 3 3","get 2"]
    //    期望：get(1) 命中;put(3) 后 key=2 不在 cache。
    //
    // 2. 失败 / 未命中
    //    检查：更新已有 key 时只改值不移头,顺序错误。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC460 LFU；LC380 O(1) Random
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意容量 2 的 LRU:put(1,1),put(2,2),get(1),put(3,3) 后 2 被淘汰。
2. 2重复只用一种结构往往让某个操作退化为线性；组合结构让查找、更新和顺序维护共享同一份状态。
3. 3优化哈希表 O(1) 定位结点 + 双向链表维护使用顺序;超容删尾,访问/更新移头。
4. 4证明链表头 MRU、尾 LRU;map 与链表结点一一对应。
5. 5复杂度时间 O(1) 各操作，空间 O(capacity)