LRU缓存算法实现：哈希表与链表结合详解

小伙伴们对文章编程感兴趣吗？是否正在学习相关知识点？如果是，那么本文《实现LRU缓存算法的数据结构通常需要结合哈希表和双向链表。以下是具体步骤：1. 数据结构选择哈希表（Hash Map）：用于快速查找缓存中的键，时间复杂度为 O(1)。双向链表（Doubly Linked List）：用于维护元素的使用顺序，最近使用的元素移到头部，最久未使用的元素从尾部删除。2. 核心操作插入（Insert）：如果键已存在，更新值并将该节点移动到头部。如果键不存在，创建新节点并插入到头部。若缓存已满，删除尾部节点。访问（Get）：如果键存在，将其对应的节点移动到头部。如果键不存在，返回 null 或 None。3. 代码实现（以 Python 为例） from collections import OrderedDict class LRUCache: def __init__(self, capacity: int): self.cache = OrderedDict() self.capacity = capacity def get(self, key: int) -> int: if key not in self.cache: return -1 # 将访问的键移动到末尾（表示最近使用） self.cache.move_to_end(key) return self.cache[key] def put(self,》，就很适合你，本篇文章讲解的知识点主要包括。在之后的文章中也会多多分享相关知识点，希望对大家的知识积累有所帮助！

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

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

数据结构设计

使用以下两个组件组合：

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

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

核心操作实现

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

• 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 近似策略或浏览器缓存等场景。

以上就是本文的全部内容了，是否有顺利帮助你解决问题？若是能给你带来学习上的帮助，请大家多多支持golang学习网！更多关于文章的相关知识，也可关注golang学习网公众号。