0146. LRU 缓存【中等】
1. 📝 题目描述
请你设计并实现一个满足 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) 的平均时间复杂度运行。
示例:
txt
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 41
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
提示:
1 <= capacity <= 30000 <= key <= 100000 <= value <= 10^5- 最多调用
2 * 10^5次get和put
2. 🎯 s.1 - 哈希表 + 双向链表
c
// 双向链表节点
typedef struct DLinkedNode {
int key, val;
struct DLinkedNode* prev;
struct DLinkedNode* next;
} DLinkedNode;
// 哈希表条目
typedef struct HashEntry {
int key;
DLinkedNode* node;
struct HashEntry* next; // 链地址法解冲突
} HashEntry;
#define HASH_SIZE 1024
typedef struct {
int capacity;
int size;
DLinkedNode* head; // 哨兵头
DLinkedNode* tail; // 哨兵尾
HashEntry* table[HASH_SIZE];
} LRUCache;
int hashKey(int key) {
return ((key % HASH_SIZE) + HASH_SIZE) % HASH_SIZE;
}
DLinkedNode* hashGet(LRUCache* cache, int key) {
int h = hashKey(key);
HashEntry* e = cache->table[h];
while (e) {
if (e->key == key) return e->node;
e = e->next;
}
return NULL;
}
void hashPut(LRUCache* cache, int key, DLinkedNode* node) {
int h = hashKey(key);
HashEntry* e = (HashEntry*)malloc(sizeof(HashEntry));
e->key = key;
e->node = node;
e->next = cache->table[h];
cache->table[h] = e;
}
void hashRemove(LRUCache* cache, int key) {
int h = hashKey(key);
HashEntry* e = cache->table[h];
HashEntry* prev = NULL;
while (e) {
if (e->key == key) {
if (prev) prev->next = e->next;
else cache->table[h] = e->next;
free(e);
return;
}
prev = e;
e = e->next;
}
}
void removeNode(DLinkedNode* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void addToHead(LRUCache* cache, DLinkedNode* node) {
node->prev = cache->head;
node->next = cache->head->next;
cache->head->next->prev = node;
cache->head->next = node;
}
LRUCache* lRUCacheCreate(int capacity) {
LRUCache* cache = (LRUCache*)calloc(1, sizeof(LRUCache));
cache->capacity = capacity;
cache->head = (DLinkedNode*)malloc(sizeof(DLinkedNode));
cache->tail = (DLinkedNode*)malloc(sizeof(DLinkedNode));
cache->head->next = cache->tail;
cache->tail->prev = cache->head;
return cache;
}
int lRUCacheGet(LRUCache* obj, int key) {
DLinkedNode* node = hashGet(obj, key);
if (!node) return -1;
removeNode(node);
addToHead(obj, node);
return node->val;
}
void lRUCachePut(LRUCache* obj, int key, int value) {
DLinkedNode* node = hashGet(obj, key);
if (node) {
node->val = value;
removeNode(node);
addToHead(obj, node);
} else {
node = (DLinkedNode*)malloc(sizeof(DLinkedNode));
node->key = key;
node->val = value;
hashPut(obj, key, node);
addToHead(obj, node);
obj->size++;
if (obj->size > obj->capacity) {
DLinkedNode* tail = obj->tail->prev;
removeNode(tail);
hashRemove(obj, tail->key);
free(tail);
obj->size--;
}
}
}
void lRUCacheFree(LRUCache* obj) {
DLinkedNode* cur = obj->head;
while (cur) {
DLinkedNode* next = cur->next;
free(cur);
cur = next;
}
for (int i = 0; i < HASH_SIZE; i++) {
HashEntry* e = obj->table[i];
while (e) {
HashEntry* next = e->next;
free(e);
e = next;
}
}
free(obj);
}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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
js
/**
* @param {number} capacity
*/
var LRUCache = function (capacity) {
this.capacity = capacity
this.map = new Map()
}
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function (key) {
if (!this.map.has(key)) return -1
const val = this.map.get(key)
// 删除后重新插入,保证最近使用的在最后
this.map.delete(key)
this.map.set(key, val)
return val
}
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function (key, value) {
if (this.map.has(key)) {
this.map.delete(key)
}
this.map.set(key, value)
if (this.map.size > this.capacity) {
// 删除最早插入的(Map 迭代顺序即插入顺序)
const firstKey = this.map.keys().next().value
this.map.delete(firstKey)
}
}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
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
py
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = OrderedDict()
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, key: int, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
- 时间复杂度:
,get和put操作均为常数时间 - 空间复杂度:
,哈希表和双向链表最多存储capacity个元素
算法思路:
- 哈希表实现
查找,双向链表实现 的插入和删除 - 每次访问或更新时,将节点移到链表头部
- 容量满时删除链表尾部的节点(最久未使用)
- JS 版本利用
Map的插入顺序特性简化实现,Python 版本使用OrderedDict
3. 🔗 引用
- LRU (最近最少使用) 缓存
- 百度百科