LRU缓存机制 题目描述 LRU（Least Recently Used）缓存机制是一种常用的缓存淘汰策略。当缓存空间不足时，它会优先淘汰最久未被访问的数据。请你设计并实现一个满足LRU约束的数据结构，该结构需要支持以下两种操作： get(key) ：如果关键字 key 存在于缓存中，则返回其对应的值，并将该数据项标记为最近使用；否则返回 -1。 put(key, value) ：如果关键字 key 已经存在，则变更其数据值 value ，并标记为最近使用；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致缓存数量超过容量 capacity ，则应该淘汰最久未使用的数据项。 解题思路分析 要实现LRU缓存，我们需要解决两个核心问题： 快速查找 ：根据 key 快速找到对应的 value 。哈希表（Hash Table）可以在 O(1) 时间内完成查找。 维护访问顺序 ：需要维护所有数据项的访问时间顺序，以便快速找出最久未使用的项。链表可以高效地进行节点顺序调整，但单链表删除节点需要遍历前驱节点。双向链表（Doubly Linked List）支持 O(1) 时间复杂度的节点删除（已知节点指针时）。 因此，我们采用 哈希表 + 双向链表 的结构： 哈希表以 key 为键，存储对应链表节点的指针。 双向链表按访问时间排序： 最近访问的节点靠近链表头部，最久未访问的节点靠近链表尾部 。 实现细节步骤 定义双向链表节点 每个节点包含三个字段： key （用于反向映射到哈希表）、 value （存储的数据）、 prev （前驱指针）、 next （后继指针）。 初始化LRU缓存 设置缓存容量 capacity 。 创建虚拟头节点（dummy head）和虚拟尾节点（dummy tail），并使它们相互指向。这样可以在实际节点操作时避免边界判断。 初始化一个空的哈希表。 实现 get 操作 在哈希表中查找 key ： 若不存在，返回 -1。 若存在，通过哈希表找到对应链表节点，将其值返回， 并将该节点移动到链表头部 （标记为最近使用）。 实现 put 操作 在哈希表中查找 key ： 若存在：更新节点的 value ，并 将该节点移动到链表头部 。 若不存在： 创建新节点，插入到链表头部，并将 key 和节点指针存入哈希表。 若插入后缓存大小超过容量，则 删除链表尾部的节点 （最久未使用），并在哈希表中删除对应的 key 。 辅助方法：移动节点到头部 从链表中删除该节点（通过修改前后节点的指针）。 将该节点插入到虚拟头节点之后。 辅助方法：删除尾部节点 通过虚拟尾节点的前驱指针找到待删除节点。 从链表中移除该节点，并在哈希表中删除其 key 。 关键点说明 使用虚拟头尾节点可以简化链表操作，避免处理空链表或单节点链表的特殊情况。 在双向链表中删除节点时，需要同时修改该节点前驱节点的 next 指针和后继节点的 prev 指针。 每次访问（get或put）一个已存在的节点时，都需要将其移动到链表头部，保证链表顺序反映访问时间。 复杂度分析 时间复杂度： get 和 put 操作均为 O(1)。 空间复杂度：O(capacity)，由哈希表和双向链表占用。 通过结合哈希表的快速查找和双向链表的顺序维护，LRU缓存机制能够高效地满足访问顺序约束和性能要求。