如何实现一个支持LRU缓存算法的数据结构？-js教程-PHP中文网

如何实现一个支持LRU缓存算法的数据结构？

betcha

发布： 2025-09-30 16:26:25

原创

648人浏览过

答案：结合哈希表和双向链表实现LRU缓存，哈希表支持O(1)查找，双向链表维护访问顺序，头结点为最近使用，尾结点为最久未使用；get操作查找不到返回-1，找到则移到头部并返回值；put操作若键存在则更新并移至头部，否则创建新节点插入头部，超容量时删除尾部节点；通过add_to_head、remove_node、move_to_head和pop_tail等辅助方法实现O(1)时间复杂度的插入、删除与移动操作，适用于页面置换、Redis及浏览器缓存等场景。

如何实现一个支持lru缓存算法的数据结构？

要实现一个支持LRU（Least Recently Used）缓存算法的数据结构，核心是结合哈希表和双向链表，以达到快速查找、插入、删除和维护访问顺序的目的。关键点在于：当缓存满时，淘汰最久未使用的数据；每次访问（get 或 put）某个键时，该键对应的数据要被移到最近使用的位置。

数据结构设计

使用以下两个组件组合：

哈希表（dict / map）：用于存储键到节点的映射，实现 O(1) 的查找时间。
双向链表：维护元素的访问顺序，头部为最近使用，尾部为最久未使用。

每个链表节点包含 key、value、prev 和 next 指针。

核心操作实现

需要支持 get 和 put 两个主要操作，并保证时间复杂度为 O(1)：

即构数智人

即构数智人是由即构科技推出的AI虚拟数字人视频创作平台，支持数字人形象定制、短视频创作、数字人直播等。

查看详情

get(key)：
- 如果 key 不存在，返回 -1。
- 如果存在，将对应节点移到链表头部（表示最近使用），并返回 value。
put(key, value)：
- 如果 key 已存在，更新其 value 并移到头部。
- 如果 key 不存在，创建新节点插入头部。
- 插入后若超出容量，删除尾部节点（最久未使用）。

辅助方法：移动到头部与删除尾部

为了简化逻辑，可以封装几个工具函数：

add_to_head(node)：将节点插入双向链表头部。
remove_node(node)：从链表中移除指定节点。
move_to_head(node)：先删除再添加到头部。
pop_tail()：移除并返回尾部节点，用于淘汰。

这些操作通过调整 prev 和 next 指针完成，不涉及遍历，因此是 O(1)。

Python 示例代码

class ListNode:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _add_to_head(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.prev
        nxt = node.next
        prev.next = nxt
        nxt.prev = prev

    def _move_to_head(self, node):
        self._remove_node(node)
        self._add_to_head(node)

    def _pop_tail(self):
        node = self.tail.prev
        self._remove_node(node)
        return node

    def get(self, key: int) -> int:
        node = self.cache.get(key)
        if not node:
            return -1
        self._move_to_head(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        node = self.cache.get(key)
        if node:
            node.val = value
            self._move_to_head(node)
        else:
            new_node = ListNode(key, value)
            self.cache[key] = new_node
            self._add_to_head(new_node)
            if len(self.cache) > self.capacity:
                tail = self._pop_tail()
                del self.cache[tail.key]

登录后复制

基本上就这些。这套实现确保了 get 和 put 都在常数时间内完成，符合 LRU 缓存的基本要求。实际应用中可用于页面置换、Redis 近似策略或浏览器缓存等场景。

以上就是如何实现一个支持LRU缓存算法的数据结构？的详细内容，更多请关注php中文网其它相关文章！