LRU缓存机制

题目描述：
设计一个LRU（最近最少使用）缓存机制。它应该支持以下操作：获取数据get和写入数据put。当缓存容量达到上限时，在写入新数据之前需要删除最久未被使用的数据项。

解题过程：

1. 需求分析

   • get(key)：如果key存在于缓存中，则获取对应的value，并将该数据项标记为最近使用
   • put(key, value)：如果key不存在，则写入数据；如果缓存已满，则需要删除最久未使用的数据后再写入
   • 时间复杂度要求：get和put操作的时间复杂度都应该是O(1)

2. 数据结构选择

   • 哈希表：提供O(1)的查找能力，但无法记录使用顺序
   • 双向链表：可以快速在头部插入、尾部删除，且能记录访问顺序
   • 组合方案：哈希表 + 双向链表
     • 哈希表存储key到链表节点的映射
     • 双向链表按使用顺序排列节点（最近使用的在头部，最久未使用的在尾部）

3. 详细设计

   • 链表节点定义：

     class DLinkedNode:
         def __init__(self, key=0, value=0):
             self.key = key
             self.value = value
             self.prev = None
             self.next = None
     

   • 缓存类结构：

     class LRUCache:
         def __init__(self, capacity: int):
             self.cache = {}  # 哈希表：key -> 节点
             self.capacity = capacity
             self.size = 0
             # 虚拟头尾节点，简化边界处理
             self.head = DLinkedNode()
             self.tail = DLinkedNode()
             self.head.next = self.tail
             self.tail.prev = self.head
     

4. 核心操作实现

   • 添加节点到头部（标记为最近使用）：

     def addToHead(self, node):
         # 将节点插入到头节点之后
         node.prev = self.head
         node.next = self.head.next
         self.head.next.prev = node
         self.head.next = node
     

   • 移除节点：

     def removeNode(self, node):
         # 从链表中移除指定节点
         node.prev.next = node.next
         node.next.prev = node.prev
     

   • 移动到头部（先移除再添加到头部）：

     def moveToHead(self, node):
         self.removeNode(node)
         self.addToHead(node)
     

   • 移除尾部节点（删除最久未使用）：

     def removeTail(self):
         node = self.tail.prev
         self.removeNode(node)
         return node  # 返回被移除的节点，用于从哈希表中删除
     

5. get操作实现

   def get(self, key: int) -> int:
       if key not in self.cache:
           return -1
   
       node = self.cache[key]
       self.moveToHead(node)  # 标记为最近使用
       return node.value
   

6. put操作实现

   def put(self, key: int, value: int) -> None:
       if key in self.cache:
           # key已存在，更新value并移动到头部
           node = self.cache[key]
           node.value = value
           self.moveToHead(node)
       else:
           # 创建新节点
           node = DLinkedNode(key, value)
           self.cache[key] = node
           self.addToHead(node)
           self.size += 1
   
           # 如果超出容量，删除尾部节点
           if self.size > self.capacity:
               removed = self.removeTail()
               del self.cache[removed.key]
               self.size -= 1
   

7. 复杂度分析

   • 时间复杂度：get和put操作都是O(1)
   • 空间复杂度：O(capacity)，由哈希表和链表共同使用

8. 实际应用场景

   • 浏览器缓存最近访问的页面
   • 操作系统内存页面置换
   • 数据库查询缓存
   • Redis等内存数据库的缓存策略

这种设计巧妙地结合了哈希表的快速查找和双向链表的顺序维护能力，完美满足了LRU缓存的功能和性能要求。