首先简单介绍下什么是 LRU 缓存，熟悉的可以跳过。
假设我们有一个玩具摊位，用于向顾客展示小玩具。玩具很多，摊位大小有限，不能一次性展示所有玩具，于是大部分玩具放在了仓库里。
https://camo.githubusercontent.com/0dca21fdf6a710c088d22577a29cd252a6bcb192a06198f26d1548c07f30d15d/68747470733a2f2f63646e2e6a7364656c6976722e6e65742f67682f7375756b69692f39312d646179732d616c676f726974686d2f6173736574732f4c52555f302e706e67
如果有顾客来咨询某个玩具，我们就去仓库把该玩具拿出来，摆在摊位上。
https://camo.githubusercontent.com/7bb87a8a586af94e96c3169b23042ce8d02977288c6387f955eea4bcb6e93d24/68747470733a2f2f63646e2e6a7364656c6976722e6e65742f67682f7375756b69692f39312d646179732d616c676f726974686d2f6173736574732f4c52555f312e706e67
因为摊位最上面的位置最显眼，所以我们总是把最新拿出来的玩具放在那。
https://camo.githubusercontent.com/e9a093a529a15771bb31594cc02597e85d0ddb21587a6345db467619849c06bb/68747470733a2f2f63646e2e6a7364656c6976722e6e65742f67682f7375756b69692f39312d646179732d616c676f726974686d2f6173736574732f4c52555f322e706e67
不过由于摊位大小有限，很快就摆满了，这时如果又有顾客想看新玩具。
https://camo.githubusercontent.com/36ed9a1368faa6910cf61134d1c89f2fd196823f75028d75a412f013a512864d/68747470733a2f2f63646e2e6a7364656c6976722e6e65742f67682f7375756b69692f39312d646179732d616c676f726974686d2f6173736574732f4c52555f332e706e67
我们只能把摊位最下面的玩具拿回仓库(因为最下面的位置相对没那么受欢迎)，然后其他玩具往下移，腾出最上面的位置来放新玩具。
https://camo.githubusercontent.com/f0a009f657005f750cb020fec0d0e74dea31cde0117bb4916260edbccd37a19f/68747470733a2f2f63646e2e6a7364656c6976722e6e65742f67682f7375756b69692f39312d646179732d616c676f726974686d2f6173736574732f4c52555f342e706e67
如果顾客想看的玩具就摆在摊位上，我们就可以把这个玩具直接移到摊位最上面的位置，其他的玩具就要往下挪挪位置了。还记得我们的规则吧，最近有人询问的玩具要摆在最上面显眼的位置。
https://camo.githubusercontent.com/7addff0512995fc5e246c09bfcbfd076d6e56c11ba4b9a09146881e8b9b65f7a/68747470733a2f2f63646e2e6a7364656c6976722e6e65742f67682f7375756b69692f39312d646179732d616c676f726974686d2f6173736574732f4c52555f352e706e67
这就是对 LRU 缓存的一个简单解释。回到计算机问题上面来，玩具摊位代表的就是缓存空间，我们首先需要考虑的问题是使用哪种数据结构来表示玩具摊位，以达到题目要求的时间复杂度。
数组？
如果选择数组，因为玩具在摊位上的位置会挪来挪去，这个操作的时间复杂度是$O(N)$，不符合题意，pass。
链表？
// put
if key 存在:
更新节点值
把节点移到链表头部
else:
if 缓存满了:
移除最后一个节点
删除它在哈希表中的映射
新建一个节点
把节点加到链表头部
在哈希表中增加映射
// get
if key 存在:
返回节点值
把节点移到链表头部
else:
返回 -1
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<int, DLinkedListNode*> 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);
*/
class DoubleLinkedListNode {
constructor(key, value) {
this.key = key
this.value = value
this.prev = null
this.next = null
}
}
class LRUCache {
constructor(capacity) {
this.capacity = capacity
this.usedSpace = 0
// Mappings of key->node.
this.hashmap = {}
this.dummyHead = new DoubleLinkedListNode(null, null)
this.dummyTail = new DoubleLinkedListNode(null, null)
this.dummyHead.next = this.dummyTail
this.dummyTail.prev = this.dummyHead
}
_isFull() {
return this.usedSpace === 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)
this.usedSpace--
}
// Create a new node and add it to the head.
const node = new DoubleLinkedListNode(key, value)
this.hashmap[key] = node
this._addToHead(node)
this.usedSpace++
}
}
}
/**
* 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)
*/