lru算法PHP实现
LRU算法简介
LRU（Least Recently Used）是一种缓存淘汰策略，优先淘汰最近最少使用的数据。PHP中可通过数组或结合链表实现，以下是两种常见实现方式。
基于数组的简易实现
利用PHP数组的键值对和unset特性，手动维护访问顺序：
class LRUCache {
private $capacity;
private $cache = [];
public function __construct($capacity) {
$this->capacity = $capacity;
}
public function get($key) {
if (!isset($this->cache[$key])) {
return -1;
}
$value = $this->cache[$key];
unset($this->cache[$key]); // 删除原有键
$this->cache[$key] = $value; // 重新插入到末尾（表示最新使用）
return $value;
}
public function put($key, $value) {
if (isset($this->cache[$key])) {
unset($this->cache[$key]);
} elseif (count($this->cache) >= $this->capacity) {
array_shift($this->cache); // 移除最旧的元素
}
$this->cache[$key] = $value;
}
}说明
get操作将访问的键移动到数组末尾，模拟“最近使用”。put操作在容量满时移除数组开头的元素（最久未使用）。
基于链表+哈希表的高效实现
使用双向链表（SplDoublyLinkedList）和哈希表（SplObjectStorage）优化时间复杂度：
class LRUCache {
private $capacity;
private $list;
private $map;
public function __construct($capacity) {
$this->capacity = $capacity;
$this->list = new SplDoublyLinkedList();
$this->map = new SplObjectStorage();
}
public function get($key) {
if (!isset($this->map[$key])) {
return -1;
}
$node = $this->map[$key];
$this->list->push($this->list->offsetGet($node)); // 移动到链表尾部
$this->list->offsetUnset($node);
return $node->value;
}
public function put($key, $value) {
if (isset($this->map[$key])) {
$this->list->offsetUnset($this->map[$key]);
} elseif ($this->list->count() >= $this->capacity) {
$oldest = $this->list->shift();
unset($this->map[$oldest->key]);
}
$node = (object)['key' => $key, 'value' => $value];
$this->list->push($node);
$this->map[$key] = $this->list->count() - 1;
}
}优化点
- 链表操作的时间复杂度为O(1)，适合高频读写场景。
SplObjectStorage用于快速定位链表节点。
注意事项
- 数组实现简单但效率较低，适合小规模数据。
- 链表实现需注意PHP的
SplDoublyLinkedList索引更新逻辑。 - 实际生产环境建议使用成熟的缓存库（如Redis）内置的LRU功能。
