# 146. LRU 缓存机制
* [146. LRU 缓存机制](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDon3ZyaYhKsHQDOM#146-lru-缓存机制)
* [题目描述](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDon3ZyaYhKsHQDOM#题目描述)
* [方法1: 哈希表+双向链表](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDon3ZyaYhKsHQDOM#方法1-哈希表双向链表)
* [思路](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDon3ZyaYhKsHQDOM#思路)
* [复杂度分析](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDon3ZyaYhKsHQDOM#复杂度分析)
* [伪代码](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDon3ZyaYhKsHQDOM#伪代码)
* [代码(JavaScript/C++)](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDon3ZyaYhKsHQDOM#代码javascriptc)
## 题目描述
```
运用你所掌握的数据结构，设计和实现一个 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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lru-cache
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
```
## 方法1: 哈希表+双向链表
### 思路
先来看个非计算机的例子理解下题意，假设我们有一个玩具摊位，可以向顾客展示小玩具。玩具很多，但摊位大小有限，不能一次性展示所有玩具，于是我们就把大部分的玩具都放在了仓库里。
如果有顾客来询问某个玩具，我们就去仓库把那个玩具拿出来，摆在摊位上。
因为摊位最上面的位置最显眼，所以我们总是把最新拿出来的玩具放在那。
不过由于摊位大小有限，很快就摆满了，这时如果又来了顾客想看新玩具。
我们只能把摊位最下面的玩具拿回仓库(因为最下面的位置相对没那么受欢迎)，然后其他玩具往下移，腾出最上面的位置来放新玩具。
如果顾客想看的玩具就摆在摊位上，我们就可以把这个玩具直接移到摊位最上面的位置，其他的玩具就要往下挪挪位置了。还记得我们的规则吧，最近有人询问的玩具要摆在最上面显眼的位置。
回到计算机问题上面来，玩具摊位代表的就是缓存空间，我们需要考虑的问题是使用哪种数据结构来表示玩具摊位。
**选择1: 数组**
如果选择数组，因为玩具在摊位上的位置会挪来挪去，时间复杂度是 $O(N)$，不符合题意。
**选择2: 链表**
* 如果选择链表，我们知道在已知位置上新增节点，或者移除一个已知节点的时间复杂度是 $O(1)$。不过，链表查找节点的时间复杂度是 $O(N)$，同样不符合题意，但这还有办法补救。
* 在玩具摊位的例子中，我们手动移动玩具的时候，只需要看一眼就知道要找的玩具在哪个位置上，但计算机没那么聪明，因此还需要给它一个脑子(哈希表)来记录什么玩具在什么位置上，也就是要用一个哈希表来记录每个 key 对应的链表节点引用。这样查找链表节点的时间复杂度就降到了 $O(1)$，不过代价是空间复杂度增加到了 $O(N)$。
* 另外，由于移除链表节点后还需要把该节点前后的两个节点连起来，因此我们需要的是双向链表而不是单向链表。
### 复杂度分析
* 时间复杂度：$O(1)$。
* 空间复杂度：链表 $O(N)$，哈希表 $O(N)$，结果还是 $O(N)$，N 为容量大小。
### 伪代码
```
// put
if key 存在:
更新节点值
把节点移到链表头部
else:
if 缓存满了:
移除最后一个节点
删除它在哈希表中的映射
新建一个节点
把节点加到链表头部
在哈希表中增加映射
// get
if key 存在:
返回节点值
把节点移到链表头部
else:
返回 -1
```
### 代码(JavaScript/C++)
JavaScript Code
```javascript
class DoubleLinkedListNode {
constructor(key, value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
// Mappings of key->node.
this.hashmap = {};
// Use two dummy nodes so that we don't have to deal with the head/tail seperately.
this.dummyHead = new DoubleLinkedListNode(null, null);
this.dummyTail = new DoubleLinkedListNode(null, null);
this.dummyHead.next = this.dummyTail;
this.dummyTail.prev = this.dummyHead;
}
_isFull() {
return Object.keys(this.hashmap).length === this.capacity;
}
_removeNode(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
node.prev = null;
node.next = null;
return node;
}
_addToHead(node) {
const head = this.dummyHead.next;
node.next = head;
head.prev = node;
node.prev = this.dummyHead;
this.dummyHead.next = node;
}
get(key) {
if (key in this.hashmap) {
const node = this.hashmap[key];
this._addToHead(this._removeNode(node));
return node.value;
} else {
return -1;
}
}
put(key, value) {
if (key in this.hashmap) {
// If key exists, update the corresponding node and move it to the head.
const node = this.hashmap[key];
node.value = value;
this._addToHead(this._removeNode(node));
} else {
// If it's a new key.
if (this._isFull()) {
// If the cache is full, remove the tail node.
const node = this.dummyTail.prev;
delete this.hashmap[node.key];
this._removeNode(node);
}
// Create a new node and add it to the head.
const node = new DoubleLinkedListNode(key, value);
this.hashmap[key] = node;
this._addToHead(node);
}
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* var obj = new LRUCache(capacity)
* var param_1 = obj.get(key)
* obj.put(key,value)
*/
```
C++ Code
```cpp
class DLinkedListNode {
public:
int key;
int value;
DLinkedListNode *prev;
DLinkedListNode *next;
DLinkedListNode() : key(0), value(0), prev(NULL), next(NULL) {};
DLinkedListNode(int k, int val) : key(k), value(val), prev(NULL), next(NULL) {};
};
class LRUCache {
public:
LRUCache(int capacity) : capacity_(capacity) {
// 创建两个 dummy 节点来简化操作，这样就不用特殊对待头尾节点了
dummy_head_ = new DLinkedListNode();
dummy_tail_ = new DLinkedListNode();
dummy_head_->next = dummy_tail_;
dummy_tail_->prev = dummy_head_;
}
int get(int key) {
if (!key_exists_(key)) {
return -1;
}
// 1. 通过哈希表找到 key 对应的节点
// 2. 将节点移到链表头部
// 3. 返回节点值
DLinkedListNode *node = key_node_map_[key];
move_to_head_(node);
return node->value;
}
void put(int key, int value) {
if (key_exists_(key)) {
// key 存在的情况
DLinkedListNode *node = key_node_map_[key];
node->value = value;
move_to_head_(node);
} else {
// key 不存在的情况：
// 1. 如果缓存空间满了，先删除尾节点，再新建节点
// 2. 否则直接新建节点
if (is_full_()) {
DLinkedListNode *tail = dummy_tail_->prev;
remove_node_(tail);
key_node_map_.erase(tail->key);
}
DLinkedListNode *new_node = new DLinkedListNode(key, value);
add_to_head_(new_node);
key_node_map_[key] = new_node;
}
}
private:
unordered_map key_node_map_;
DLinkedListNode *dummy_head_;
DLinkedListNode *dummy_tail_;
int capacity_;
void move_to_head_(DLinkedListNode *node) {
remove_node_(node);
add_to_head_(node);
};
void add_to_head_(DLinkedListNode *node) {
DLinkedListNode *prev_head = dummy_head_->next;
dummy_head_->next = node;
node->prev = dummy_head_;
node->next = prev_head;
prev_head->prev = node;
};
void remove_node_(DLinkedListNode *node) {
node->prev->next = node->next;
node->next->prev = node->prev;
node->prev = node->next = NULL;
};
bool key_exists_(int key) {
return key_node_map_.count(key) > 0;
};
bool is_full_() {
return key_node_map_.size() == capacity_;
};
};
/**
* 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);
*/
```
更多题解可以访问：
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://suki.gitbook.io/91-days-algorithm/basic/linked-list/12.lru-cache.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.