如何用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

想象一下，我们缓存了1000个项目，突然访问了第500个。如果用普通列表，我们得先找到它（O(N)），然后删除它（O(N)），再把它加到列表开头（又是一个O(N)），这简直是性能灾难。而双向链表就不同了。每个节点都存储了指向前一个和后一个节点的引用。这意味着一旦我们通过字典以O(1)时间找到某个节点，我们就可以在O(1)时间内完成它的删除（只需修改它前后节点的

next

prev

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

处理LRU缓存的容量限制和淘汰策略，是整个实现的关键。我的做法是，在

LRUCache

__init__

capacity

capacity

立即学习“Python免费学习笔记（深入）”；

当

put

key

self.cache

html5动态显示媒体视频播放器代码

html5动态显示媒体视频播放器代码,这个我们在企业网站或者教学网站会用到，教学网站，有一些视频要播放，那么就会用到播放器，可以参考源码，看看播放器的效果是如何实现的，php中文网推荐下载！

下载

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

OrderedDict

move_to_end

一个基于

OrderedDict

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

不过，话说回来，尽管

OrderedDict

OrderedDict

OrderedDict