当前位置：首页 > PHP

php 实现lru

2026-02-14 19:53:27PHP

LRU 缓存实现原理

LRU（Least Recently Used）是一种缓存淘汰策略，当缓存空间不足时，优先移除最久未被使用的数据。PHP 实现 LRU 通常需要结合哈希表（快速查找）和双向链表（维护访问顺序）。

基于数组和链表的实现

PHP 中可以通过数组模拟哈希表，结合 SplDoublyLinkedList 实现 LRU：

class LRUCache {
    private $capacity;
    private $map = [];
    private $list;

    public function __construct($capacity) {
        $this->capacity = $capacity;
        $this->list = new SplDoublyLinkedList();
    }

    public function get($key) {
        if (!isset($this->map[$key])) {
            return -1;
        }

        $node = $this->map[$key];
        $this->list->push($this->list->shift()); // 移动到链表尾部
        return $node['value'];
    }

    public function put($key, $value) {
        if (isset($this->map[$key])) {
            unset($this->map[$key]);
            $this->list->shift(); // 移除旧节点
        }

        if (count($this->map) >= $this->capacity) {
            $oldKey = $this->list->shift();
            unset($this->map[$oldKey]);
        }

        $this->list->push(['key' => $key, 'value' => $value]);
        $this->map[$key] = end($this->list);
    }
}

使用 SplDoublyLinkedList 优化

SplDoublyLinkedList 提供高效的头尾操作，适合 LRU 场景：

class LRUCache {
    private $capacity;
    private $map = [];
    private $list;

    public function __construct($capacity) {
        $this->capacity = $capacity;
        $this->list = new SplDoublyLinkedList();
        $this->list->setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO);
    }

    public function get($key) {
        if (!isset($this->map[$key])) {
            return -1;
        }

        $node = $this->map[$key];
        $this->list->push($node);
        $this->list->offsetUnset($this->list->key());
        return $node['value'];
    }

    public function put($key, $value) {
        if (isset($this->map[$key])) {
            $this->list->offsetUnset($this->list->key());
        }

        if (count($this->map) >= $this->capacity) {
            $oldNode = $this->list->shift();
            unset($this->map[$oldNode['key']]);
        }

        $node = ['key' => $key, 'value' => $value];
        $this->list->push($node);
        $this->map[$key] = $node;
    }
}

纯数组实现方案

如果环境限制不能使用 SPL，可以用纯数组模拟：

php 实现lru

class LRUCache {
    private $capacity;
    private $cache = [];
    private $order = [];

    public function __construct($capacity) {
        $this->capacity = $capacity;
    }

    public function get($key) {
        if (!isset($this->cache[$key])) {
            return -1;
        }

        unset($this->order[array_search($key, $this->order)]);
        $this->order[] = $key;
        return $this->cache[$key];
    }

    public function put($key, $value) {
        if (isset($this->cache[$key])) {
            unset($this->order[array_search($key, $this->order)]);
        }

        if (count($this->cache) >= $this->capacity) {
            $oldKey = array_shift($this->order);
            unset($this->cache[$oldKey]);
        }

        $this->cache[$key] = $value;
        $this->order[] = $key;
    }
}