设计LRU缓存结构_牛客题霸_牛客网
设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 capacity ，操作次数是 n ，并有如下功能:

  1. Solution(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  2. get(key)：如果关键字 key 存在于缓存中，则返回key对应的value值，否则返回 -1 。
  3. set(key, value)：将记录(key, value)插入该结构，如果关键字 key 已经存在，则变更其数据值 value，如果不存在，则向缓存中插入该组 key-value ，如果key-value的数量超过capacity，弹出最久未使用的key-value

提示:
1.某个key的set或get操作一旦发生，则认为这个key的记录成了最常使用的，然后都会刷新缓存。
2.当缓存的大小超过capacity时，移除最不经常使用的记录。
3.返回的value都以字符串形式表达，如果是set，则会输出”null”来表示(不需要用户返回，系统会自动输出)，方便观察
4.函数set和get必须以O(1)的方式运行

想法：

用一个容器维护按最近访问时间的值，需要满足：

  1. O（1）时间插入到最后，O（1）时间删除第一个，类似队列
  2. O（1）时间找到元素，并且将元素移到队尾，实现更新
  3. 每次淘汰时，判断长度超容，然后淘汰第一个位置

为什么不用双端队列？双端队列只能操作首尾，且双端队列可能就是基于双链表实现的；而LRU需要移动中间的，所以使用双向链表

综上所述，该容器是有序、分散分布的，因此是一个双向链表，哈希表指向队列中节点的地址.
❌错误代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class BiListNode:
    def __init__(self, val) -> None:
        self.val = val
        self.pre = None
        self.next = None


class Solution:
    def __init__(self, capacity: int):
        self.length = 0
        self.capacity = capacity
        self.head = None
        self.rear = None
        self.hashtable = {}

    def print_(self):
        this_node = self.head
        str_ = []
        while this_node is not None:
            str_.append(this_node.val)
            this_node = this_node.next
        print(str_)
        
    def get(self, key: int) -> int:
        value = self.hashtable.get(key)
        if value is None:
            self.print_()
            return -1
        else:
            if value.pre is not None:  # 如果不是头节点
                value.pre.next = value.next
            if value.next is not None: # 非尾节点
                value.next.pre = value.pre

            # 插头
            value.pre = None
            value.next = self.head
            self.head.pre = value
            self.head = value
            self.print_()
            return value.val

    def set(self, key: int, value: int) -> None:
        if self.length == 0:
            new_node = BiListNode(value)
            self.head = new_node
            self.rear = new_node
            self.length += 1
            self.hashtable[key] = new_node
            self.print_()
            return
        
        node = self.hashtable.get(key)
        if node is not None:
            node.val = value
            # 插头
            node.pre = None
            node.next = self.head
            self.head.pre = node
            self.head = node
        else:
            new_node = BiListNode(value)
            self.hashtable[key] = new_node
            # 插头
            new_node.pre = None
            new_node.next = self.head
            self.head.pre = new_node
            self.head = new_node
            self.length += 1
            if self.length > self.capacity:
                self.rear.pre.next = None
                rear = self.rear.pre
                del self.rear
                self.rear = rear
        self.print_()

根据代码调试需求，我发现当前实现存在以下几个关键问题：

🚨 核心问题分析

  1. Node 结构缺失 key 字段（关键缺陷）
    1
    2
    3
    4
    5
    class BiListNode:
        def __init__(self, val) -> None:  # ❌ 缺少 key 参数
            self.val = val
            self.pre = None
            self.next = None
  • 后果：当删除尾节点时无法获取对应的 key，导致哈希表无法正确清理旧数据
  1. 容量管理逻辑错误
    1
    2
    3
    4
    5
    if self.length > self.capacity:  # ❌ 容量判断逻辑错误
        self.rear.pre.next = None
        rear = self.rear.pre
        del self.rear
        self.rear = rear
  • 问题：length 没有被正确减少，且删除尾节点时没有更新哈希表
  1. 链表操作边界条件问题
  • 当链表只有一个节点时，移动节点会导致 rear 指针失效
  • 没有使用 dummy head/tail 导致边界处理复杂（参考 labuladong.online）

简单修正：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class BiListNode:
    def __init__(self, key, val) -> None:
        self.key = key
        self.val = val
        self.pre = None
        self.next = None


class Solution:
    def __init__(self, capacity: int):
        self.length = 0
        self.capacity = capacity
        self.head = None
        self.rear = None
        self.hashtable = {}

    def print_(self):
        cur = self.head
        res = []
        while cur:
            res.append(f"({cur.key}:{cur.val})")
            cur = cur.next
        print(" -> ".join(res))

    def _move_to_head(self, node):
        """从链表当前位置，移动到头部"""
        if node == self.head:
            return  # 已经是头部
        # detach
        if node.pre:
            node.pre.next = node.next
        if node.next:
            node.next.pre = node.pre
        if node == self.rear:
            self.rear = node.pre

        # insert at head
        node.pre = None
        node.next = self.head
        if self.head:
            self.head.pre = node
        self.head = node
        if self.rear is None:  # only one node
            self.rear = node

    def get(self, key: int) -> int:
        node = self.hashtable.get(key)
        if node is None:
            return -1
        self._move_to_head(node)
        return node.val

    def set(self, key: int, value: int) -> None:
        node = self.hashtable.get(key)
        if node:  # 如果 key 存在
            node.val = value
            self._move_to_head(node)
        else:
            new_node = BiListNode(key, value)
            self.hashtable[key] = new_node

            # 插入到头部
            new_node.pre = None
            new_node.next = self.head
            if self.head:
                self.head.pre = new_node
            self.head = new_node

            if not self.rear:
                self.rear = new_node

            self.length += 1

            if self.length > self.capacity:
                # 删除尾部节点
                to_remove = self.rear
                if to_remove.pre:
                    to_remove.pre.next = None
                self.rear = to_remove.pre

                del self.hashtable[to_remove.key]
                del to_remove
                self.length -= 1

    def debug(self):
        self.print_()

✅ 正确实现方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class BiListNode:
    def __init__(self, key, val):  # ✅ 增加 key 字段
        self.key = key
        self.val = val
        self.pre = None
        self.next = None

class Solution:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.hashtable = {}
        # ✅ 使用 dummy 节点简化操作
        self.dummy_head = BiListNode(-1, -1)
        self.dummy_tail = BiListNode(-1, -1)
        self.dummy_head.next = self.dummy_tail
        self.dummy_tail.pre = self.dummy_head

    def _remove_node(self, node):
        """移除指定节点"""
        prev = node.pre
        next = node.next
        prev.next = next
        next.pre = prev

    def _add_to_head(self, node):
        """添加节点到头部"""
        node.next = self.dummy_head.next
        node.pre = self.dummy_head
        self.dummy_head.next.pre = node
        self.dummy_head.next = node

    def get(self, key: int) -> int:
        if key not in self.hashtable:
            return -1
        node = self.hashtable[key]
        self._remove_node(node)  # ✅ 统一操作逻辑
        self._add_to_head(node)
        return node.val

    def set(self, key: int, value: int) -> None:
        if key in self.hashtable:
            node = self.hashtable[key]
            node.val = value
            self._remove_node(node)
            self._add_to_head(node)
        else:
            if len(self.hashtable) >= self.capacity:  # ✅ 正确容量判断
                # 移除最久未使用的节点
                last_node = self.dummy_tail.pre
                self._remove_node(last_node)
                del self.hashtable[last_node.key]  # ✅ 清理哈希表
            
            new_node = BiListNode(key, value)
            self.hashtable[key] = new_node
            self._add_to_head(new_node)

🛠️ 关键改进点说明

改进点 原代码问题 新方案优势
Node 结构 无法追踪 key 导致哈希表泄漏 通过存储 key 实现完整清理
Dummy 节点 头尾边界处理复杂 统一操作逻辑，避免空指针
容量管理 length 计数不准确 直接通过哈希表大小判断
链表操作 分散的指针操作易出错 封装成 _remove_node 和 _add_to_head

🔍 测试用例验证

1
2
3
4
5
6
cache = Solution(2)
cache.set(1, 100)  # 链表: [100]
cache.set(2, 200)  # 链表: [200, 100]
print(cache.get(1))  # 输出 100，链表变为 [100, 200]
cache.set(3, 300)   # 淘汰 key=2，链表: [300, 100]
print(cache.get(2))  # 输出 -1（已淘汰）

建议结合双向链表的基础原理（参考 labuladong.online）和 LRU 的标准实现模式进行理解。