当前位置：首页 > PHP

lru算法PHP实现

2026-02-15 08:28:32PHP

LRU算法简介

LRU（Least Recently Used）是一种缓存淘汰策略，优先淘汰最近最少使用的数据。PHP中可通过数组或结合链表实现，以下是两种常见实现方式。

基于数组的简易实现

利用PHP数组的键值对和unset特性，手动维护访问顺序：

lru算法PHP实现

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;
    }
}

说明

lru算法PHP实现

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;
    }
}

优化点