哈希算法题目：设计一个LRU缓存

题目描述
设计一个LRU（最近最少使用）缓存机制，需要支持以下操作：

• get(key)：如果key存在于缓存中，则返回对应的值，否则返回-1
• put(key, value)：如果key已存在，则更新其值；如果不存在，则插入该键值对。当缓存容量达到上限时，应删除最久未使用的键值对

要求所有操作的时间复杂度为O(1)

解题思路分析

1. 需要O(1)时间完成查找 → 哈希表（字典）存储key到节点的映射
2. 需要维护访问顺序 → 双向链表（头部放最新访问的节点，尾部放最久未使用的节点）
3. 结合哈希表的快速查找和链表的快速插入/删除特性

实现步骤

步骤1：设计双向链表节点

class DLinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None  # 前驱指针
        self.next = None  # 后继指针

步骤2：初始化LRU缓存结构

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity  # 缓存容量
        self.size = 0  # 当前大小
        self.cache = {}  # 哈希表：key -> 节点
        
        # 创建伪头节点和伪尾节点（简化边界处理）
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head

步骤3：实现链表辅助方法

def _add_node(self, node):
    """将新节点添加到链表头部（最近使用）"""
    node.prev = self.head
    node.next = self.head.next
    
    self.head.next.prev = node
    self.head.next = node

def _remove_node(self, node):
    """从链表中删除指定节点"""
    prev_node = node.prev
    next_node = node.next
    
    prev_node.next = next_node
    next_node.prev = prev_node

def _move_to_head(self, node):
    """将节点移动到头部（标记为最近使用）"""
    self._remove_node(node)  # 先从原位置移除
    self._add_node(node)     # 再添加到头部

def _pop_tail(self):
    """弹出尾部的节点（最久未使用）"""
    tail_node = self.tail.prev
    self._remove_node(tail_node)
    return tail_node

步骤4：实现get操作

def get(self, key: int) -> int:
    # 在哈希表中查找key
    node = self.cache.get(key, None)
    
    if not node:  # key不存在
        return -1
    
    # key存在，将节点移到头部（标记为最近使用）
    self._move_to_head(node)
    return node.value

步骤5：实现put操作

def put(self, key: int, value: int) -> None:
    # 检查key是否已存在
    node = self.cache.get(key, None)
    
    if not node:  # key不存在
        # 创建新节点
        new_node = DLinkedNode(key, value)
        
        # 添加到哈希表和链表头部
        self.cache[key] = new_node
        self._add_node(new_node)
        self.size += 1
        
        # 如果超出容量，删除最久未使用的节点
        if self.size > self.capacity:
            tail_node = self._pop_tail()
            del self.cache[tail_node.key]  # 从哈希表删除
            self.size -= 1
    else:  # key已存在
        # 更新值并移到头部
        node.value = value
        self._move_to_head(node)

操作示例演示
假设容量为2，操作序列：

1. put(1,1) → 缓存: {1=1}
2. put(2,2) → 缓存: {1=1, 2=2}（1最近使用）
3. get(1) → 返回1，缓存顺序变为：2→1
4. put(3,3) → 容量已满，淘汰2，加入3 → 缓存: {1=1, 3=3}
5. get(2) → 返回-1（已被淘汰）

复杂度分析

• 时间复杂度：get和put操作都是O(1)
• 空间复杂度：O(capacity)，哈希表和链表各存储capacity个元素

这个设计完美结合了哈希表的快速查找和链表的顺序维护能力，是LRU缓存的经典实现方案。