如何用Python实现一个LRU缓存？-Python教程-PHP中文网

如何用Python实现一个LRU缓存？

狼影

发布： 2025-09-05 13:54:02

原创

705人浏览过

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

如何用python实现一个lru缓存？

在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

登录后复制

就是缓存能容纳的最大项目数。

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

当

put

登录后复制

方法被调用时，我们首先检查要插入的

key

登录后复制

是否已经存在于

self.cache

登录后复制

字典中。

如果
key
登录后复制
已存在：这表示我们只是更新一个现有项。在这种情况下，我们更新其
```
value
```
登录后复制
，然后最关键的一步是调用
```
_move_to_head
```
登录后复制
方法，将其对应的节点从链表当前位置移除，再添加到链表的头部。这反映了它刚刚被“使用”了，所以现在是最新的。
如果
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) # 移除最老（最久未使用）的项

登录后复制

这种实现方式确实非常优雅，代码量大大减少，并且由于