Python实现LRU缓存的完整方法

答案：LRU缓存通过字典和双向链表结合实现，字典提供O(1)查找，双向链表维护访问顺序，确保插入、删除和访问更新均为O(1)操作。每次get或put操作都会将对应节点移至链表头部，当缓存满时，尾部节点被移除，从而保证最久未使用项优先淘汰。虚拟头尾节点简化边界处理，而OrderedDict虽可替代实现，但自定义方式更利于理解底层机制。

在Python中实现LRU（Least Recently Used）缓存，核心思路在于巧妙地结合哈希表（Python的字典）和双向链表。字典确保我们能以O(1)的平均时间复杂度快速查找缓存中的任何项，而双向链表则负责维护项的访问顺序，使得最近使用的项总在链表头部，最久未使用的项（即待淘汰项）总在链表尾部，这样无论是更新访问顺序还是进行淘汰，都能保持高效。

解决方案

class Node:
    """双向链表节点定义"""
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    """
    LRU缓存实现，结合字典和双向链表
    """
    def __init__(self, capacity: int):
        if capacity <= 0:
            raise ValueError("缓存容量必须大于0")
        self.capacity = capacity
        self.cache = {}  # 存储key到Node的映射，用于O(1)查找
        self.head = Node(0, 0) # 虚拟头节点
        self.tail = Node(0, 0) # 虚拟尾节点
        self.head.next = self.tail
        self.tail.prev = self.head

    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 get(self, key: int) -> int:
        """
        获取缓存项。如果存在，将其移动到链表头部并返回其值；否则返回-1。
        """
        if key not in self.cache:
            return -1

        node = self.cache[key]
        self._move_to_head(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        """
        放入缓存项。
        如果key已存在，更新其值并将其移动到链表头部。
        如果key不存在：
            如果缓存未满，创建新节点并添加到链表头部。
            如果缓存已满，移除链表尾部（最久未使用）的节点，再添加新节点到头部。
        """
        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:
                # 移除最久未使用的节点 (tail.prev)
                lru_node = self.tail.prev
                self._remove_node(lru_node)
                del self.cache[lru_node.key]

LRU缓存为何偏爱双向链表而非普通列表？

在我看来，LRU缓存选择双向链表，这背后是性能和操作复杂度的深思熟虑。我们都知道，Python的list在末尾添加（append）和删除（pop）通常是O(1)操作，但如果在中间或头部进行插入或删除，其时间复杂度就直接飙升到O(N)，因为需要移动后续所有元素。对于LRU缓存来说，每次访问一个元素，都需要将其“提升”到“最近使用”的位置，这通常意味着从当前位置删除，再插入到链表头部。如果用普通列表，这个“提升”操作会非常昂贵。

想象一下，我们缓存了1000个项目，突然访问了第500个。如果用普通列表，我们得先找到它（O(N)），然后删除它（O(N)），再把它加到列表开头（又是一个O(N)），这简直是性能灾难。而双向链表就不同了。每个节点都存储了指向前一个和后一个节点的引用。这意味着一旦我们通过字典以O(1)时间找到某个节点，我们就可以在O(1)时间内完成它的删除（只需修改它前后节点的next和prev指针）和插入（同样是修改几个指针）。这种效率上的巨大差异，正是双向链表在LRU实现中不可或缺的原因。它让我们的缓存操作，特别是“更新访问顺序”这一核心逻辑，保持了极高的效率。

如何处理缓存容量限制和淘汰策略？

处理LRU缓存的容量限制和淘汰策略，是整个实现的关键。我的做法是，在LRUCache的__init__方法中，我们首先设定一个capacity。这个capacity就是缓存能容纳的最大项目数。

当put方法被调用时，我们首先检查要插入的key是否已经存在于self.cache字典中。

1. 如果key已存在：这表示我们只是更新一个现有项。在这种情况下，我们更新其value，然后最关键的一步是调用_move_to_head方法，将其对应的节点从链表当前位置移除，再添加到链表的头部。这反映了它刚刚被“使用”了，所以现在是最新的。
2. 如果key不存在：这是一个全新的项。我们首先创建一个新的Node，然后将其添加到self.cache字典中，并调用_add_node方法将其添加到链表的头部。 紧接着，我们就需要检查缓存是否“超载”了。我们通过len(self.cache) > self.capacity来判断当前缓存中的项目数量是否超过了设定的capacity。如果超载了，这意味着我们必须淘汰一个项目来为新项目腾出空间。LRU的策略是淘汰“最久未使用的”项目。在我们的双向链表中，这个项目就是紧挨着虚拟尾节点self.tail的前一个节点（即self.tail.prev）。我们称之为lru_node。我们调用_remove_node(lru_node)将其从链表中移除，然后通过del self.cache[lru_node.key]将其从字典中也删除，完成彻底的淘汰。

这种机制确保了缓存始终在容量限制内运行，并且每次淘汰都严格遵循了“最久未使用”的原则。虚拟头尾节点的设计，更是简化了链表边缘情况的处理，让代码逻辑更清晰。

Python内置的OrderedDict能否替代自定义LRU实现？

当然可以，而且在很多简单场景下，使用Python标准库collections模块中的OrderedDict来实现LRU缓存会显得非常简洁高效。OrderedDict本身就维护了键值对的插入顺序。它的move_to_end方法和在插入时检查容量并删除最老项的机制，与LRU缓存的逻辑高度契合。

一个基于OrderedDict的LRU实现大致会是这样：

from collections import OrderedDict

class LRUCacheOrderedDict:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key) # 将key移动到末尾，表示最近使用
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key) # 存在则移动到末尾
        self.cache[key] = value # 更新或添加
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False) # 移除最老（最久未使用）的项

这种实现方式确实非常优雅，代码量大大减少，并且由于OrderedDict是用C实现的，其内部操作通常效率很高。

不过，话说回来，尽管OrderedDict能很好地完成任务，但它也隐藏了LRU缓存底层双向链表的精妙机制。对于初学者或者需要深入理解数据结构和算法的开发者来说，自己动手实现一个基于字典和双向链表的LRU缓存，就像我们前面做的那样，其教育价值是OrderedDict无法替代的。它能让我们更清晰地看到每个操作是如何影响底层数据结构的，以及为什么这些数据结构的选择如此关键。在面试或者需要对性能有极致掌控的场景下，理解并能手写底层逻辑，往往比仅仅会用库函数更能体现技术深度。所以，选择哪种方式，最终还是取决于具体的需求：追求简洁快速就用OrderedDict，追求深入理解和精细控制则倾向于自定义实现。