Python实现LRU缓存算法：基于双向链表与哈希表

小岛来信

发布时间：2026-10-15| 5人浏览过

原创

本文介绍如何使用Python基于双向链表和哈希表实现LRU（最近最少使用）缓存算法。通过get和put操作，结合DoubleLinkedList类与字典映射，实现O(1)时间复杂度的数据访问与更新。文章包含完整代码示例及测试逻辑，适用于Redis淘汰机制等场景的学习与参考。

在上一节中，我们已经完成了双向链表DoubleLinkedList类的构建。本节将在此基础上，利用该链表实现LRU（Least Recently Used，最近最少使用）缓存置换算法。这种机制常见于Redis等系统的淘汰策略中，用于移除长期未被访问的数据，具体配置可通过Redis配置文件进行调整。

一、LRU算法的实现

核心逻辑主要包含get和put两种操作。在get操作中，若目标元素存在，需将其从当前链表位置移除并移至头部，以标记其为最近访问节点；在put操作中，无论元素是否已存在，均需将其移动至链表头部。同时，借助哈希表（map）实现O(1)复杂度的查找效率。

class LRUCache(object):

    def __init__(self, capacity=0xffffffff):
        """
        LRU缓存置换算法 最近最少使用
        :param capacity:
        """
        self.capacity = capacity
        self.size = 0
        self.map = {}
        self.list = DoubleLinkedList(capacity)

    def get(self, key):
        """
        获取元素
            获取元素不存在 返回None
            获取元素已存在 将节点从当前位置删除并添加至链表头部
        :param key:
        :return:
        """
        # 元素不存在
        if key not in self.map:
            return None

        node = self.map.get(key)
        self.list.remove(node)
        self.list.append_front(node)

        return node.value

    def put(self, key, value):
        """
        添加元素
            被添加的元素已存在 更新元素值并已到链表头部
            被添加的元素不存在
                链表容量达到上限 删除尾部元素
                链表容量未达上限 添加至链表头部
        :param key:
        :param value:
        :return:
        """
        if key in self.map:
            node = self.map.get(key)
            node.value = value
            self.list.remove(node)
            self.list.append_front(node)
        else:
            if self.size >= self.capacity:
                old_node = self.list.remove()
                del self.map[old_node.key]
                self.size -= 1

            node = Node(key, value)
            self.map[key] = node
            self.list.append_front(node)
            self.size += 1

        return node

    def print(self):
        """
        打印当前链表
        :return:
        """
        self.list.print()

二、测试逻辑

if __name__ == '__main__':
    lru_cache = LRUCache(3)
    lru_cache.put(1, 1)
    lru_cache.print()
    lru_cache.put(2, 2)
    lru_cache.print()
    print(lru_cache.get(1))
    lru_cache.print()
    lru_cache.put(3, 3)
    lru_cache.print()
    lru_cache.put(1, 100)
    lru_cache.print()
    lru_cache.put(4, 4)
    lru_cache.print()
    print(lru_cache.get(1))
    lru_cache.print()

测试结果如下：