# 144 - 146 LRU缓存机制
## 题目
运用你所掌握的数据结构，设计和实现一个 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
## 解答
第一想法是用哈希表。记录一下有哪些数，以及使用次数。
或者多记录一个set，每次get了啥就push进去，超过缓存容量的get，就记录，下次有put就删掉
### 有序字典
```python
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.data = collections.OrderedDict()
def get(self, key: int) -> int:
if key not in self.data:
return -1
self.data.move_to_end(key)
return self.data[key]
def put(self, key: int, value: int) -> None:
if key in self.data:
self.data.move_to_end(key)
self.data[key] = value
if len(self.data) > self.capacity:
self.data.popitem(last=False)
```
> Runtime: 192 ms, faster than 95.99% of Python3 online submissions for LRU Cache.
>
> Memory Usage: 22 MB, less than 27.27% of Python3 online submissions for LRU Cache.
python特有的数据结构，就是一个字典，但是有方法可以把里面元素放到最后。
感觉其他语言也可以写一个类似的函数
```javascript
/**
* @param {number} capacity
*/
var LRUCache = function(capacity) {
this.data = new Map()
this.capacity = capacity
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
if (this.data.has(key)) {
const value = this.data.get(key)
this.data.delete(key)
this.data.set(key, value)
return value
} else {
return -1
}
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
if (this.data.has(key)) {
this.data.delete(key)
} else if (this.data.size === this.capacity) {
const first_key = this.data.keys().next().value
this.data.delete(first_key)
}
this.data.set(key, value)
};
```
> Runtime: 220 ms, faster than 31.35% of JavaScript online submissions for LRU Cache.
>
> Memory Usage: 58.9 MB, less than 30.00% of JavaScript online submissions for LRU Cache.
### 哈希表+双向链表
>
增删查都要O(1)，因此就用哈希表+双向链表
```python
class DLinkedNode():
def __init__(self, key=None, value=None):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.data = {}
self.head = DLinkedNode()
self.tail = DLinkedNode()
self.head.next = self.tail
self.tail.prev = self.head
def move_to_tail(self, key: int) -> None:
node = self.data[key]
node.prev.next = node.next
node.next.prev = node.prev
node.prev = self.tail.prev
node.next = self.tail
self.tail.prev.next = node
self.tail.prev = node
def get(self, key: int) -> int:
if key in self.data:
self.move_to_tail(key)
res = self.data.get(key, -1)
if res == -1:
return -1
else:
return res.value
def put(self, key: int, value: int) -> None:
if key in self.data:
self.data[key].value = value
self.move_to_tail(key)
else:
if len(self.data) == self.capacity:
node = self.head.next
self.data.pop(node.key)
self.head.next = node.next
node.next.prev = self.head
new = DLinkedNode(key, value)
self.data[key] = new
new.next = self.tail
new.prev = self.tail.prev
self.tail.prev.next = new
self.tail.prev = new
```
> Runtime: 216 ms, faster than 70.19% of Python3 online submissions for LRU Cache.
>
> Memory Usage: 22.6 MB, less than 6.06% of Python3 online submissions for LRU Cache.
---
# 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://joey-zhouyicheng.gitbook.io/leetcode/144-146-lru-huan-cun-ji-zhi.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.