如何实现一个高效的 LRU 缓存？

LRU（Least Recently Used）缓存是一种移除最少近期使用的元素的策略，广泛应用于优化系统性能。以下是基于主流技术和参考内容的实现方法：

关键原理：LRU 使用双向链表（代表最近访问时间序列，头为最新，尾为最旧）和哈希映射（key-值映射，提升访问速度 O(1)）。缓存操作包括：

1. get(key)：哈希键是否存在，存在时移动对应节点到链表头部并返回值；否则返回未命中（如 -1）。确保更新最近使用记录。
2. put(key, value)：检查键是否已在缓存：
   • 如果存在，更新值，并移动到链表头部。
   • 如果不存在，检查容量：若满了，从链表尾部移除节点（最旧使用记录），添加新节点到头部；若未满，直接添加至头部。
     需要控制操作复杂度均接近 O(1)。在配置时选择合适的淘汰策略以确保高效。

代码实现（Python）

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.double_linked_list = DoubleLinkedList()  # 辅助双向链表类（见下文）
    
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        # 移动节点到链表头部（最近使用）
        node = self.cache[key]
        self.double_linked_list.remove(node)
        self.double_linked_list.add_to_head(node)
        return node.value
    
    def put(self, key: int, value: int) -> None:
        if key in self.cache:  # 已存在则更新并刷新位置
            node = self.cache[key]
            node.value = value
            self.double_linked_list.remove(node)
            self.double_linked_list.add_to_head(node)
        else:
            # 新节点添加后需检查溢出规则
            node = Node(key, value)
            self.cache[key] = node
            self.double_linked_list.add_to_head(node)
            
            if len(self.cache) > self.capacity:
                # 移除尾节点（最近最不用的）
                tail = self.double_linked_list.remove_from_tail()
                del self.cache[tail.key]
    
# 辅助结构和类：
class Node:
    def __init__(self, key: int, value: int):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class DoubleLinkedList:
    def __init__(self):
        self.head = Node(0, 0)  # 伪头节点
        self.tail = Node(0, 0)  # 伪尾节点
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def remove(self, node: Node):
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node
    
    def add_to_head(self, node: Node):
        temp_next = self.head.next
        self.head.next = node
        node.prev = self.head
        node.next = temp_next
        temp_next.prev = node
    
    def remove_from_tail(self) -> Node:
        old_tail = self.tail.prev
        self.remove(old_tail)
        return old_tail  # 键在移除逻辑中被检索以更新 cache

优化策略:

• 内存管理：对于大数据或高性能应用，结合语言内置内存优化，设置容量上限避免 OOM（如 Python 中定义明确范围）。
• 高性能工具：在语言栈中利用优化结构（Java 的 LinkedHashMap 默认支持 LRU）或第三方库（Python 的 cachetools 带淘汰策略简化开发。
• 一致性处理：对于线程安全或分布式扩展需求，使用中间件如 Redis 内置 LRU 策略，并在配置中指定。配置淘汰策略解决缓存穿透/雪崩（设空值入口或随机时间逻辑）。实践步骤包括：选择淘汰规则并定期监控吞吐量和命中率来优化策略。