146. LRU缓存机制
题目来源:https://leetcode-cn.com/problems/lru-cache/
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制
。它应该支持以下操作: 获取数据 get
和 写入数据 put
。
获取数据 get(key)
- 如果关键字 (key) 存在于缓存中,则获取关键字的值(总是正数),否则返回 -1。
写入数据 put(key, value)
- 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字/值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。
进阶:
你是否可以在 O(1)
时间复杂度内完成这两种操作?
示例:
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
解法
题目要求 O(1)
时间复杂度内完成操作,最先应该想到的是哈希表,则通过牺牲空间复杂度来降低时间复杂度。那哈希表存放的是什么内容呢?哈希表应该存放的是每个缓存的键值以方便对所以缓存的管理。
那下面就有一个很重要的问题了,就是应该用什么结构体去存储这些缓存?是线性表?链表?堆栈?还是队列?要明确这一问题,就要从LRU算法本身入手。
LRU算法是操作系统中页面置换算法之一,即最近最久未使用的算法。如字面意思,每次缓存淘汰的都是最近最久未使用的缓存,这就使得缓存区的缓存始终保持一定的新鲜度。
以操作系统中的页面置换为例,假设要访问的页号是:7,0,1,2,0,3,0,4,内存块大小为3.
初始化 | 7替换为2 | 命中 | 1替换为3 | 命中 | 4替换2 |
---|---|---|---|---|---|
7 | 0 | 1 | 2 | 2 | 3 |
0 | 1 | 2 | 0 | 3 | 0 |
1 | 2 | 0 | 3 | 0 | 4 |
(注:第三行始终为最近常使用的缓存块,第一行始终为最近最久未使用的缓存块)
由上图我们可以得到:
1.每次命中的数据块应放置在最近常用的缓存块;
2.每次替换的数据块为最近最久未使用的缓存块,并且将替换的缓存块放入最近常用的缓存块中;
根据以上的特点,这需要更改某些块的位置,显然用双向链表结构体比较合适。
算法大致过程如下:(假设缓存块大小为2)
Head端保持的是最近最常用的缓存块,而Tail端保持的是最近最久未使用的缓存块,如果缓存块已使用的数量达到阈值,那么需要进行替换,删除的是Tail端的缓存块,同时将待替换的缓存块放入Head端。如上图5,由于缓存块已满,所以需要将Tail端的B删除,同时需要将待替换的C插入到Head端之后。
以上算法流程算是清晰了,但是还有一个问题需要解决,那就是在 O(1)
时间复杂度内完成上述操作。
现在存在的问题是get如果通过遍历整个链表的方式去获取键值,那么需要消耗O(n)
的时间复杂度,这与题目相背。为了解决这一问题,我们需要将键与缓存块的地址相映射,以方便我们更快的找到对应的缓存块并取出值。同时,为了满足 O(1)
时间复杂度,需要使用哈希表来存储键与缓存块的映射矩阵。
C++代码:
class Node {
public:
int key;
int value;
Node *pre;
Node *next;
Node():key(0),value(0),pre(nullptr),next(nullptr){}
Node(int key,int value):pre(nullptr),next(nullptr){
this->key = key;
this->value = value;
}
};
class LRUCache {
private:
Node *head,*tail;
unordered_map<int, Node*> cache;
int capacity,size;
public:
LRUCache(int _capacity):capacity(_capacity),size(0) {
head = new Node();
tail = new Node();
head->next = tail;
tail->pre = head;
}
int get(int key) {
if(!cache.count(key)){
return -1;
}
move_to_Head(cache[key]);
return cache[key]->value;
}
void put(int key, int value) {
if(cache.count(key)){
cache[key]->value = value;
move_to_Head(cache[key]);
return;
}else{
Node *p = new Node(key,value);
cache[key] = p;
add_to_Head(p);
size++;
if(size>capacity){
cache.erase(tail->pre->key);
remove_Node(tail->pre);
size--;
}
}
}
void remove_Node(Node *p)
{
p->pre->next = p->next;
p->next->pre = p->pre;
}
void add_to_Head(Node *p)
{
p->next = head->next;
head->next->pre = p;
head->next = p;
p->pre = head;
}
void move_to_Head(Node *p)
{
remove_Node(p);
add_to_Head(p);
}
};
/**
* 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);
*/
复杂度分析:
时间复杂度:
O(1)
空间复杂度:
O(n)
,哈希表。