当前位置： 面试刷题>> LRU缓存策略 (经典算法题500道)
### 题目描述补充
LRU（Least Recently Used）缓存策略是一种常用的页面置换算法，用于管理缓存中的数据，确保当缓存达到其容量限制时，能够移除最久未使用的数据，以便为新的数据腾出空间。具体实现时，通常需要快速判断哪些数据是最久未使用的，并能在常数时间内完成插入、访问和删除操作。
### 题目要求
实现一个基于LRU策略的缓存机制，该机制应支持以下操作：
1. `get(key)`: 如果缓存中存在该键，则返回对应的值，并更新该键为最近使用；如果缓存中不存在该键，则返回-1。
2. `put(key, value)`: 如果缓存中已存在该键，则更新其值并标记为最近使用；如果缓存中不存在该键，则插入该键值对，如果此时缓存达到容量限制，则移除最久未使用的数据项（键值对）。
缓存的容量作为参数传递给缓存类的构造函数。
### 示例代码
#### PHP 示例
```php
class LRUCache {
private $capacity;
private $cache;
private $usedOrder;
function __construct($capacity) {
$this->capacity = $capacity;
$this->cache = [];
$this->usedOrder = new SplDoublyLinkedList();
}
function get($key) {
if (!isset($this->cache[$key])) {
return -1;
}
// 更新使用顺序
$this->moveToFront($key);
return $this->cache[$key]->value;
}
function put($key, $value) {
if (isset($this->cache[$key])) {
// 更新值并移动到链表前端
$this->cache[$key]->value = $value;
$this->moveToFront($key);
return;
}
$newNode = new stdClass();
$newNode->key = $key;
$newNode->value = $value;
$this->cache[$key] = $newNode;
$this->usedOrder->push($newNode);
if (count($this->cache) > $this->capacity) {
$tail = $this->usedOrder->pop();
unset($this->cache[$tail->key]);
}
}
private function moveToFront($key) {
$node = $this->cache[$key];
$this->usedOrder->detach($this->getIteratorByValue($node));
$this->usedOrder->push($node);
}
private function getIteratorByValue($value) {
foreach ($this->usedOrder as $key => $node) {
if ($node === $value) {
return $key;
}
}
return false;
}
}
```
注意：PHP 的 `SplDoublyLinkedList` 不直接支持通过值获取键，这里的 `getIteratorByValue` 方法是模拟的，实际使用时可能需要更复杂的逻辑或数据结构。
#### 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:
self.cache.move_to_end(key) # 更新键的位置
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # 移除最久未使用的数据项（即有序字典的开头）
```
#### 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);
}
this.cache.set(key, value);
if (this.cache.size > this.capacity) {
const firstKey = this.cache.keys().next().value; // 获取最久未使用的键
this.cache.delete(firstKey);
}
}
}
```
请注意，JavaScript 示例中对于 Map 的迭代和删除最久未使用的元素实现可能因环境而异，上述实现依赖于 Map 迭代器的行为，这在大多数现代 JavaScript 环境中是有效的。
---
码小课网站中有更多关于 LRU 缓存策略的实现和优化方法的分享，欢迎大家前往学习。