LRU缓存淘汰算法原理与实现

题目描述
LRU（Least Recently Used）缓存淘汰算法是一种常用的缓存管理策略，其核心思想是"淘汰最久未使用的数据"。当缓存空间不足时，LRU会优先移除最长时间未被访问的数据项。该算法需要高效支持数据的插入、查找和删除操作，时间复杂度应接近O(1)。

核心原理

1. 访问顺序决定优先级：最近被访问的数据在未来被再次访问的概率更高
2. 淘汰策略：当缓存满时，淘汰链表中最久未被访问的节点（表头或表尾取决于设计）
3. 数据结构需求：需要快速定位数据位置（哈希表）和维护访问顺序（双向链表）

算法实现步骤

步骤1：设计节点结构
每个缓存节点包含三个部分：

class Node:
    def __init__(self, key, value):
        self.key = key      # 用于哈希表查找
        self.value = value  # 存储的数据
        self.prev = None    # 前驱节点
        self.next = None    # 后继节点

步骤2：初始化数据结构

• 使用哈希表（字典）实现O(1)查询
• 使用带头尾哨兵节点的双向链表维护访问顺序

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity        # 缓存容量
        self.cache = {}                 # 哈希表：key -> Node
        # 创建哨兵节点，简化链表操作
        self.head = Node(0, 0)          # 最近访问的节点
        self.tail = Node(0, 0)          # 最久未访问的节点
        self.head.next = self.tail
        self.tail.prev = self.head

步骤3：实现节点操作辅助方法

• 添加到链表头部（表示最新访问）

def _add_node(self, node):
    # 将节点插入到head之后
    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):
    last_node = self.tail.prev  # 最久未使用的节点
    self._remove_node(last_node)
    return last_node

步骤4：实现核心接口

• get操作（查询数据）

def get(self, key):
    if key not in self.cache:
        return -1  # 缓存未命中
    
    node = self.cache[key]
    self._move_to_head(node)  # 更新为最近访问
    return node.value

• put操作（插入数据）

def put(self, key, value):
    if key in self.cache:
        # 键已存在，更新值并提升优先级
        node = self.cache[key]
        node.value = value
        self._move_to_head(node)
    else:
        # 创建新节点
        new_node = Node(key, value)
        self.cache[key] = new_node
        self._add_node(new_node)
        
        # 检查容量，触发淘汰
        if len(self.cache) > self.capacity:
            last_node = self._pop_tail()
            del self.cache[last_node.key]  # 从哈希表删除

复杂度分析

• 时间复杂度：get和put操作均为O(1)
• 空间复杂度：O(capacity)，容量固定

实际应用场景

1. 数据库查询缓存（Redis、Memcached）
2. 浏览器缓存最近访问的页面
3. 操作系统页面置换算法
4. 微服务架构中的API响应缓存

优化变种

• LRU-K：考虑最近K次访问历史
• 2Q：使用两个队列区分热点数据
• LFU：基于访问频率的淘汰策略