Keshawn_lu's Blog

Leetcode 146. LRU缓存机制

字数统计: 1.2k阅读时长: 4 min
2020/05/25 Share

题目简介:

运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put

获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。

写入数据 put(key, value) - 如果密钥已经存在,则变更其数据值;如果密钥不存在,则插入该组「密钥/数据值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作?

示例:

1
2
3
4
5
6
7
8
9
10
11
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4

思路:

LRU淘汰算法(Least Recently Used)上学期操作系统里学到过,也就是每次淘汰最久没有用到过的数据。

由于时间复杂度要求O(1),所以为了查找快,我们使用哈希表;因为 cache 必须有顺序之分,以区分最近使用的和最久未使用的数据,且我们要在 cache 中查找键是否已存在,如果容量满了要删除最后一个数据;每次访问还要把数据插入到队头,所以我们使用双向链表。结合一下就成了哈希链表,就是像下图一样的结构:

这样以来,我们首先使用哈希表进行定位,找出缓存项在双向链表中的位置,随后将其移动到双向链表的头部,即可在 O(1) 的时间内完成 get 或者 put 操作。具体的方法如下:

  • 对于 get 操作,首先判断 key 是否存在:

    • 如果 key 不存在,则返回 -1
    • 如果 key 存在,则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置,并将其移动到双向链表的头部(该节点为最近使用的节点),最后返回该节点的值。
  • 对于 put 操作,首先判断 key 是否存在:

    • 如果 key 不存在,使用 keyvalue 创建一个新的节点,在双向链表的头部添加该节点,并将该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量,如果超出容量,则删除双向链表的尾部节点,并删除哈希表中对应的项;

    • 如果 key 存在,则与 get 操作类似,先通过哈希表定位,再将对应的节点的值更新为 value,并将该节点移到双向链表的头部。

tip:

  • 在双向链表的实现中,使用一个伪头部(dummy head)和伪尾部(dummy 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
103
104
105
106
107
108
109
110
111
112
class LRUCache {
public:

//定义双向链表
struct DoubleLinkNode{

int key, value;
DoubleLinkNode* pre;
DoubleLinkNode* next;

DoubleLinkNode() : key(0), value(0), pre(NULL), next(NULL){}
DoubleLinkNode(int _key, int _value) : key(_key), value(_value),
pre(NULL), next(NULL){}
};

unordered_map<int, DoubleLinkNode*> cache;
DoubleLinkNode* head;
DoubleLinkNode* tail;
int size;
int capacity;

LRUCache(int _capacity) : capacity(_capacity), size(0){

head = new DoubleLinkNode();
tail = new DoubleLinkNode();

head -> next = tail;
tail -> pre = head;

}

int get(int key) {

if(cache.count(key) == 0)
return -1;

DoubleLinkNode* node = cache[key];
//最近的使用,移至头部
moveToHead(node);

return node -> value;
}

void put(int key, int value) {

//秘钥不存在
if(cache.count(key) == 0){

//加入数据
DoubleLinkNode* newnode = new DoubleLinkNode(key, value);
addToHead(newnode);
cache[key] = newnode;
size++;

if(size > capacity){

//容量不足,删除最久未使用的数据
DoubleLinkNode* node = removeTail();
cache.erase(node -> key); //根据键值删除元素
size--;

}
}
//秘钥存在
else{
DoubleLinkNode* node = cache[key];
node -> value = value; //修改新的value
//移至链表头
moveToHead(node);
}

}

//将结点添加至头部
void addToHead(DoubleLinkNode* node){

node -> pre = head;
node -> next = head -> next;
head -> next -> pre = node;
head -> next = node;
}

//删除结点
void removeNode(DoubleLinkNode* node){

node -> pre -> next = node -> next;
node -> next -> pre = node -> pre;
}

//将结点在原本处删除,并添加至头部
void moveToHead(DoubleLinkNode* node){

removeNode(node);
addToHead(node);
}

//将尾部结点删除
DoubleLinkNode* removeTail(){

DoubleLinkNode* node = tail -> pre;
removeNode(node);

return node;
}
};

/**
* 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);
*/
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: