news 2026/4/16 10:46:48

《手撕 LRU Cache：从 @lru_cache 底层原理到双向链表 + 哈希表的高性能实现》

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
《手撕 LRU Cache：从 @lru_cache 底层原理到双向链表 + 哈希表的高性能实现》

《手撕 LRU Cache：从 @lru_cache 底层原理到双向链表 + 哈希表的高性能实现》

一、写在前面：为什么每个 Python 开发者都应该理解 LRU Cache？

Python 自 1991 年诞生以来，以其简洁优雅的语法、强大的生态系统和“胶水语言”的特性，成为 Web 开发、数据科学、人工智能、自动化运维等领域的首选语言。随着 Python 在高性能计算、分布式系统和数据密集型应用中的使用越来越广，**缓存（Cache）**的重要性也日益凸显。

在实际项目中，你一定遇到过这些场景：

  • 某个函数计算量巨大，希望缓存结果避免重复计算
  • 某个接口被频繁调用，希望减少数据库压力
  • 某个数据结构需要快速淘汰旧数据，保持固定容量
  • 某个服务需要实现本地缓存，提高响应速度

这些问题的核心解决方案之一，就是LRU Cache（Least Recently Used Cache）。

Python 内置的functools.lru_cache是一个极其强大的工具，但你是否真正理解它的底层原理？你是否知道它内部使用了什么数据结构？你是否能手写一个高性能的 LRU Cache？

这篇文章将带你从基础到进阶，彻底掌握：

  • LRU Cache 的核心思想
  • @lru_cache 的底层实现原理
  • 如何手写一个双向链表 + 哈希表的 O(1) LRU Cache
  • 如何在实际项目中使用 LRU 提升性能
  • 如何避免 LRU Cache 的常见坑

无论你是初学者还是资深开发者，这篇文章都能帮助你构建对缓存机制的深刻理解。

二、基础部分：什么是 LRU Cache？

1. LRU 的定义

LRU（Least Recently Used）是一种缓存淘汰策略：

当缓存满时，淘汰最近最少使用的数据。

它的核心思想是：

  • 最近使用过的数据未来更可能被使用
  • 很久没用的数据未来被使用的概率更低

因此，当缓存容量有限时，LRU 是一种非常合理的淘汰策略。

2. LRU Cache 的核心操作

一个 LRU Cache 必须支持两个操作，且都要达到 O(1) 时间复杂度：

（1）get(key)

  • 如果 key 存在，返回 value，并将该 key 标记为“最近使用”
  • 如果 key 不存在，返回 -1 或 None

（2）put(key, value)

  • 如果 key 已存在，更新 value，并将其标记为“最近使用”
  • 如果 key 不存在：
    • 如果缓存未满，直接插入
    • 如果缓存已满，淘汰“最久未使用”的节点

3. 为什么必须使用“双向链表 + 哈希表”？

为了实现 O(1)：

  • 哈希表（dict）用于 O(1) 查找 key
  • 双向链表用于 O(1) 移动节点（最近使用的放头部，最久未使用的放尾部）

结构如下：

哈希表 key -> 双向链表节点 双向链表： head <-> node1 <-> node2 <-> ... <-> tail

三、深入理解：Python 内置 @lru_cache 的底层原理

Python 的functools.lru_cache是 CPython 用 C 实现的高性能缓存机制。

示例：

fromfunctoolsimportlru_cache@lru_cache(maxsize=128)deffib(n):ifn<2:returnnreturnfib(n-1)+fib(n-2)

1. @lru_cache 的核心特性

  • 使用哈希表 + 双向链表实现
  • key 必须是可哈希的（hashable）
  • 自动淘汰最久未使用的数据
  • 提供缓存统计信息（hits、misses）
  • 提供 cache_clear() 清空缓存
  • 提供 cache_info() 查看缓存状态

2. @lru_cache 的底层结构（简化版）

内部结构类似：

structlru_cache{PyObject*cache_dict;// 哈希表PyObject*root;// 双向链表的哨兵节点intmaxsize;inthits;intmisses;};

链表节点结构：

structnode{PyObject*key;PyObject*value;structnode*prev;structnode*next;};

3. 为什么 @lru_cache 如此高效？

  • C 实现，性能极高
  • 使用 PyDict（哈希表）快速查找
  • 使用双向链表快速移动节点
  • 使用哨兵节点（root）避免边界判断
  • 使用 key 的 hash 值作为缓存索引

四、手撕 LRU Cache：双向链表 + 哈希表版（Python 实现）

下面我们手写一个高性能 LRU Cache，完全模拟 @lru_cache 的底层结构。

1. 定义双向链表节点

classNode:def__init__(self,key=None,value=None):self.key=key self.value=value self.prev=Noneself.next=None

2. 定义 LRU Cache 主体

classLRUCache:def__init__(self,capacity:int):self.capacity=capacity self.cache={}# key -> Node# 创建伪头尾节点（哨兵节点）self.head=Node()self.tail=Node()self.head.next=self.tail self.tail.prev=self.head

3. 工具方法：添加节点到头部

def_add_node(self,node):node.prev=self.head node.next=self.head.nextself.head.next.prev=node self.head.next=node

4. 工具方法：删除节点

def_remove_node(self,node):prev=node.prev nxt=node.nextprev.next=nxt nxt.prev=prev

5. 工具方法：移动节点到头部（标记为最近使用）

def_move_to_head(self,node):self._remove_node(node)self._add_node(node)

6. 工具方法：弹出尾部节点（最久未使用）

def_pop_tail(self):node=self.tail.prev self._remove_node(node)returnnode

7. 实现 get()

defget(self,key):node=self.cache.get(key)ifnotnode:return-1self._move_to_head(node)returnnode.value

8. 实现 put()

defput(self,key,value):node=self.cache.get(key)ifnode:node.value=value self._move_to_head(node)else:new_node=Node(key,value)self.cache[key]=new_node self._add_node(new_node)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]

9. 完整代码（可直接运行）

classNode:def__init__(self,key=None,value=None):self.key=key self.value=value self.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacity self.cache={}self.head=Node()self.tail=Node()self.head.next=self.tail self.tail.prev=self.headdef_add_node(self,node):node.prev=self.head node.next=self.head.nextself.head.next.prev=node self.head.next=nodedef_remove_node(self,node):prev=node.prev nxt=node.nextprev.next=nxt nxt.prev=prevdef_move_to_head(self,node):self._remove_node(node)self._add_node(node)def_pop_tail(self):node=self.tail.prev self._remove_node(node)returnnodedefget(self,key):node=self.cache.get(key)ifnotnode:return-1self._move_to_head(node)returnnode.valuedefput(self,key,value):node=self.cache.get(key)ifnode:node.value=value self._move_to_head(node)else:new_node=Node(key,value)self.cache[key]=new_node self._add_node(new_node)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]

五、实战案例：LRU Cache 在真实项目中的应用

1. 场景：数据库查询缓存

cache=LRUCache(1000)defget_user(uid):result=cache.get(uid)ifresult!=-1:returnresult result=db.query("SELECT * FROM users WHERE id=?",uid)cache.put(uid,result)returnresult

2. 场景：Web API 本地缓存

cache=LRUCache(500)defget_weather(city):if(data:=cache.get(city))!=-1:returndata data=requests.get(f"https://api.weather.com/{city}").json()cache.put(city,data)returndata

3. 场景：复杂计算缓存

cache=LRUCache(2000)defheavy_compute(x):if(res:=cache.get(x))!=-1:returnres res=slow_function(x)cache.put(x,res)returnres

六、最佳实践：如何正确使用 LRU Cache？

1. 使用 @lru_cache 时注意参数必须可哈希

错误：

@lru_cache()deff(x:list):...

正确：

@lru_cache()deff(x:tuple):...

2. 不要缓存过大的对象

否则会导致内存暴涨。

3. 不要缓存带副作用的函数

例如：

  • 写文件
  • 发请求
  • 修改数据库

4. 使用 cache_clear() 清空缓存

fib.cache_clear()

5. 使用 cache_info() 查看缓存命中率

print(fib.cache_info())

七、前沿视角：LRU Cache 的未来与 Python 生态

随着 Python 在 AI、数据工程、云计算中的使用越来越广，缓存机制也在不断演进：

  • Python 3.12+ 更高效的字典实现
  • Redis + Python 的分布式缓存
  • FastAPI + async LRU 的协程缓存
  • Rust + Python 混合开发的高性能缓存系统
  • 新一代缓存库（cachetools、aiocache）

未来的 Python 缓存系统将更加智能、可观测、可扩展。

八、总结与互动

本文我们系统讨论了：

  • LRU Cache 的核心思想
  • @lru_cache 的底层原理
  • 如何手写一个双向链表 + 哈希表的 LRU Cache
  • 实战级应用场景
  • 最佳实践与未来趋势

希望这篇文章能帮助你在未来的项目中写出更高性能、更优雅的 Python 代码。

我也非常想听听你的经验：

  • 你在项目中使用过 LRU Cache 吗？
  • 你是否踩过 @lru_cache 的坑？
  • 你希望我继续写哪些 Python 底层原理文章？

欢迎在评论区分享你的故事，我们一起交流、一起成长。

版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/4/11 5:37:48

3分钟学会在Windows电脑安装安卓应用：告别繁琐模拟器时代

3分钟学会在Windows电脑安装安卓应用&#xff1a;告别繁琐模拟器时代 【免费下载链接】APK-Installer An Android Application Installer for Windows 项目地址: https://gitcode.com/GitHub_Trending/ap/APK-Installer APK Installer是一款革命性的Windows安卓应用安装…

作者头像 李华
网站建设 2026/4/15 17:53:28

音频内容本地化管理的终极方案：效率革命从这里开始

音频内容本地化管理的终极方案&#xff1a;效率革命从这里开始 【免费下载链接】xmly-downloader-qt5 喜马拉雅FM专辑下载器. 支持VIP与付费专辑. 使用GoQt5编写(Not Qt Binding). 项目地址: https://gitcode.com/gh_mirrors/xm/xmly-downloader-qt5 面对海量音频资源无…

作者头像 李华
网站建设 2026/4/16 9:18:04

VideoSrt终极指南：快速掌握AI智能字幕生成技术

VideoSrt终极指南&#xff1a;快速掌握AI智能字幕生成技术 【免费下载链接】video-srt-windows 这是一个可以识别视频语音自动生成字幕SRT文件的开源 Windows-GUI 软件工具。 项目地址: https://gitcode.com/gh_mirrors/vi/video-srt-windows VideoSrt是一款基于人工智能…

作者头像 李华
网站建设 2026/4/16 9:18:56

阿里云盘自动化管理工具：从手动操作到智能调度的技术演进

阿里云盘自动化管理工具&#xff1a;从手动操作到智能调度的技术演进 【免费下载链接】aliyundrive-subscribe 阿里云盘 【订阅】【转存】 【下载】【命名】 项目地址: https://gitcode.com/gh_mirrors/al/aliyundrive-subscribe 在数字化资源日益丰富的今天&#xff0c…

作者头像 李华
网站建设 2026/4/15 10:36:10

终极指南：如何快速上手Notepad--跨平台文本编辑器

终极指南&#xff1a;如何快速上手Notepad--跨平台文本编辑器 【免费下载链接】notepad-- 一个支持windows/linux/mac的文本编辑器&#xff0c;目标是做中国人自己的编辑器&#xff0c;来自中国。 项目地址: https://gitcode.com/GitHub_Trending/no/notepad-- 还在为不…

作者头像 李华
网站建设 2026/4/15 11:34:08

漫画应用版本发布质量保障实战指南

漫画应用版本发布质量保障实战指南 【免费下载链接】kobi 拷贝漫画客户端 项目地址: https://gitcode.com/gh_mirrors/ko/kobi 从0.0.20到0.0.21版本升级的深度剖析 核心要点速览 版本管理盲区&#xff1a;手动更新导致文件不同步质量保障策略&#xff1a;构建自动化检…

作者头像 李华