当前位置： 面试刷题>> LRU 缓存(经典算法150题)
### LRU 缓存机制
**题目描述**：
设计并实现一个 LRU（最近最少使用）缓存机制。该机制将允许你获取和设置键值对，并且会在每次访问（无论是获取还是设置）后更新键的顺序，使得最近使用的键总是排在最前面。如果缓存容量已满，则应当移除最久未使用的键（即最末尾的键）。
**示例**：
- 缓存容量 `capacity` = 2
- 操作序列：
1. `cache.put(1, 1)`
2. `cache.put(2, 2)`
3. `cache.get(1)` // 返回 1
4. `cache.put(3, 3)` // 该操作会使键 2 作废
5. `cache.get(2)` // 返回 -1 (未找到)
6. `cache.get(3)` // 返回 3
7. `cache.put(4, 4)` // 该操作会使键 1 作废
8. `cache.get(1)` // 返回 -1 (未找到)
9. `cache.get(3)` // 返回 3
10. `cache.get(4)` // 返回 4
**要求**：
- `get(key)` 方法应返回键对应的值，如果键不存在则返回 -1。
- `put(key, value)` 方法应插入或更新键的值。如果缓存达到其容量，则应该在插入新项之前使最近最少使用的项无效。
### PHP 实现
```php
class LRUCache {
private $capacity;
private $cache;
private $keys;
function __construct($capacity) {
$this->capacity = $capacity;
$this->cache = [];
$this->keys = new SplDoublyLinkedList();
}
function get($key) {
if (!$this->keys->contains($key)) {
return -1;
}
// 移除旧的节点
$this->keys->offsetUnset($key);
// 添加到头部（最近使用）
$this->keys->offsetSet(0, $key);
return $this->cache[$key];
}
function put($key, $value) {
if ($this->keys->contains($key)) {
// 如果键已存在，先移除旧的
$this->keys->offsetUnset($key);
}
// 添加新值
$this->cache[$key] = $value;
// 添加到头部（最近使用）
if ($this->keys->count() >= $this->capacity) {
// 移除最久未使用的项
$oldestKey = $this->keys->bottom();
$this->keys->offsetUnset($oldestKey);
unset($this->cache[$oldestKey]);
}
$this->keys->offsetSet(0, $key);
}
}
```
注意：PHP 标准库中并没有直接支持双向链表的类，这里为了演示方便，使用了 `SplDoublyLinkedList` 类来模拟键的顺序，但请注意，它并不直接支持通过值来快速移除节点，因此这里的 `contains` 和 `offsetUnset` 方法仅用于示意，实际实现中可能需要额外的数据结构或逻辑来优化。
### Python 实现
```python
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key: int) -> int:
if key not in self.cache:
return -1
else:
# 将访问的键值对移动到最前面
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
# 如果键已存在，先移除旧的
del self.cache[key]
elif len(self.cache) >= self.capacity:
# 移除最久未使用的项
self.cache.popitem(last=False)
# 插入新键值对到最前面
self.cache[key] = value
```
### JavaScript 实现
```javascript
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
}
get(key) {
if (!this.cache.has(key)) {
return -1;
}
// 移除旧的节点
const value = this.cache.get(key);
this.cache.delete(key);
// 添加到头部（最近使用）
this.cache.set(key, value);
return value;
}
put(key, value) {
if (this.cache.has(key)) {
// 如果键已存在，先移除旧的
this.cache.delete(key);
} else if (this.cache.size >= this.capacity) {
// 移除最久未使用的项
const firstKey = this.cache.keys().next().value;
this.cache.delete(firstKey);
}
// 插入新键值对
this.cache.set(key, value);
}
}
```
以上代码分别用 PHP、Python 和 JavaScript 实现了 LRU 缓存机制，每种语言都利用了其内置的数据结构来优化操作效率。