Python实现LRU缓存：基于列表与哈希表的原理及代码解析

小满

发布时间：2026-10-13| 4人浏览过

原创

本文介绍如何使用Python实现LRU（最近最少使用）缓存算法。核心思路结合列表与哈希表，列表用于维护访问顺序，哈希表用于实现O(1)时间的查找与删除。通过移动热点数据至列表头部，并在全满时淘汰尾部数据，高效管理缓存空间。

LRU算法基本概念

LRU

LRU（Least Recently Used，最近最少使用）是一种数据淘汰策略。该算法依据历史访问记录来决定数据的去留，其核心逻辑在于：若某数据近期被频繁访问，则其在未来被再次访问的可能性也相对较大。

Python实现方案

在Python中，可以通过组合使用列表（List）和哈希表（Hash Map）来构建LRU算法。

当访问某个热点数据时，首先需将其从当前所在列表位置移除，随后将其插入到列表的头部，以标记其为最新访问。
为了将读取及删除操作的时间复杂度控制在O(1)，引入哈希表来存储热点数据的键值对信息，从而避免线性查找。

核心代码解析


class LRUCaceh():
   def __init__(self, size=5):
     '''
     默认队列的长度为5
     使用列表来维护，使用字典来查询
     '''
     self.size = size
     self.cache = dict()
     self.key = []
 
   def get(self, key):
     '''
     获取缓存中的key的值
     '''
     if self.cache.get(key):
       self.key.remove(key)
       self.key.insert(0, key)
       return self.cache[key]
     return None
 
   def set(self, key, value):
     '''
     设置缓存，实现缓存淘汰
     '''
     if self.cache.get(key):
       self.cache.pop(key)
       self.cache[key] = value
       self.key.remove(key)
       self.key.insert(0, key)
     elif len(self.key) == self.size:
       old_key = self.key.pop()
       self.key.insert(0, key)
       self.cache.pop(old_key)
       self.cache[key] = value
     else:
       self.key.insert(0, key)
       self.cache[key] = value