答案：结合哈希表和双向链表实现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)：
狼群淘客 免费开源淘宝客程序
下载
狼群淘客系统基于canphp框架进行开发，MVC结构、数据库碎片式缓存机制，使网站支持更大的负载量，结合淘宝开放平台API实现的一个淘宝客购物导航系统采用php+mysql实现，任何人都可以免费下载使用 。狼群淘客的任何代码都是不加密的，你不用担心会有任何写死的PID，不用担心你的劳动成果被窃取。
-
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 近似策略或浏览器缓存等场景。
