题目

146. LRU 缓存 - 力扣（LeetCode）

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

思路

操作系统中学习过LRU的相关知识，中文是最长最久未使用，是页面置换算法的一部分。即页表在置换算法的时候，从当前时刻往前找，找到以载入页面中最长时间没有被使用的哪一个，将其置换出去。

对于代码而言，可以用双向链表+哈希表的结构来实现。

  • 哈希表存放key和node的关系；
  • node中存放key和value（注意get的时候需要返回的是value）；

我们使用list来维护节点被使用的时间，一个节点被访问就插入到链表头，这样就能保证链表尾部的就是那个最久没有被使用的节点。链表元素超出capacity需要删除节点的时候，就将尾部的节点删除即可。

哈希表是用来判断某一个节点是否已经存在于链表中的，链表的查找时间复杂度是O(N)，哈希表能将其降至O(1)；注意，删除某个节点的时候也需要将这个节点从哈希表中剔除，调用erase函数即可。

如果一个key已经存在与list中，访问的时候就需要将其先删除，再头插，相当于更新了被使用的时间。为了满足题目中O(1)时间复杂度的要求，使用双向链表才能保证删除的时间复杂度是O(1)。

get

get操作的思路如下

  • 查询需要的key是否存在于哈希表中，如果不存在直接返回-1；
  • 如果存在，则获得该key对应的链表节点，并从节点中读取value值（返回值）；
  • 如果存在，将对应节点从链表中删除，再头插，以更新访问时间。
  • 因为删除和插入操作用的都是原来的节点，key和节点地址的映射关系没有变化，所以不需要修改哈希表，也不需要修改size。
  • 返回刚刚记录的存在节点的value值。

put

put操作的思路如下

  • 查询需要的插入的key是否存在于哈希表中，如果存在则和get操作类似，将其从链表中删除再头插，注意需要修改node节点中的value。
  • 需要的key不在哈希表中，则判断当前长度
    • 未超出限制，new一个新的链表节点，头插到链表中，并将节点值和节点地址的映射关系插入哈希表，size+1；
    • 链表已有长度等于最大值了，尾删节点并删除该节点值在哈希表中的映射；new一个新的链表节点，头插到链表中，并将节点值和节点地址的映射关系插入哈希表。因为删除又新增了一个节点，size不变。

这样就能保证链表中的节点是按最近访问（get或者put）的时间来按顺序排列的，末尾节点是最久没有被操作过的节点。

代码

刚开始用的头删+尾插的方式，结果弄了好久都还有段错误，改成头插+尾删好处理一些。

为了方便处理头节点和尾部节点的插入和删除，在初始化链表的时候会初始化一个head和tail节点，这样后序新增/删除节点的所有操作都能统一处理。

刚开始我作死用了双向循环链表+单头节点，结果写了好久都没把链表头插和尾删搞明白，只能说自己实在是太菜了。还是用现在这种方式更好控制一些。

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
struct Node
{
    int _val;
    int _key;
    Node* _prev;
    Node* _next;

    Node():_val(0),_key(0),_prev(nullptr),_next(nullptr){}
    Node(int key,int val):_val(val),_key(key),_prev(nullptr),_next(nullptr){}
};

class LRUCache {
    Node* _head;
    Node* _tail;
    unordered_map<int,Node*> _map;
    int _size = 0;
    int _capa = 0;
public:
    LRUCache(int capacity) {
        _head = new Node();
        _tail = new Node();
        // 维持头尾节点的链接关系
        // 当前是双向链表，不是循环链表
        _head->_next = _tail;
        _tail->_prev = _head;
        // 初始化允许的最大值
        _capa = capacity;
    }
	// 头插
	void addNodeToHead(Node* node)
    {
	    // 当前节点的上一个是头
	    // 注意这个head是多出来的带头节点，并非第一个节点
        node->_prev = _head; 
        // 当前节点的下一个是原本的头节点
        node->_next = _head->_next;
        // 原本头节点的上一个是当前节点
        _head->_next->_prev = node;
        // 更新新的头节点
        _head->_next = node;
    }
	// 删除某个节点
    void removeNode(Node* node)
    {
	    // 将前置节点的next指向当前节点的next
        node->_prev->_next = node->_next;
        // 将下一个节点的prev指向前置节点
        node->_next->_prev = node->_prev;
        // 这样就相当于从链表结构中剔除了当前节点
        // 注意，因为删除后可能还需要头插这个node，所以不能delete
    }

    int get(int key) {
        if(_map.count(key))
        {
            Node* node = _map[key];
            removeNode(node);
            addNodeToHead(node);
            // 删除又插入，不需要修改map的映射和size
            return node->_val;
        }
        return -1;
    }
    
    void put(int key, int value) {
        // 存在
        if(_map.count(key))
        {
            Node* node = _map[key];
            node->_val = value; // 修改value
            removeNode(node);
            addNodeToHead(node);
            // 删除又插入，不需要修改map的映射和size
        }
        else
        {
            // 超长了
            if(_size == _capa)
            {
                Node* remove = _tail->_prev;
                _map.erase(remove->_key);
                removeNode(remove);
                _size--; // 删除，链表长度减一
                // 这里可以不free节点，因为OJ不考虑内存泄漏
                delete remove;
            }
            Node* node = new Node(key,value);
            addNodeToHead(node);
            _map[key] = node;
            _size++;
        }
    }

    
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

image.png