LRU 缓存机制
题目描述: 设计并实现一个 LRU(最近最少使用)缓存机制。该机制将允许你获取和设置键值对,并且会在每次访问(无论是获取还是设置)后更新键的顺序,使得最近使用的键总是排在最前面。如果缓存容量已满,则应当移除最久未使用的键(即最末尾的键)。
示例:
- 缓存容量
capacity
= 2 - 操作序列:
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)
// 返回 1cache.put(3, 3)
// 该操作会使键 2 作废cache.get(2)
// 返回 -1 (未找到)cache.get(3)
// 返回 3cache.put(4, 4)
// 该操作会使键 1 作废cache.get(1)
// 返回 -1 (未找到)cache.get(3)
// 返回 3cache.get(4)
// 返回 4
要求:
get(key)
方法应返回键对应的值,如果键不存在则返回 -1。put(key, value)
方法应插入或更新键的值。如果缓存达到其容量,则应该在插入新项之前使最近最少使用的项无效。
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 实现
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 实现
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 缓存机制,每种语言都利用了其内置的数据结构来优化操作效率。