php 实现lru

LRU 缓存实现原理

LRU（Least Recently Used）缓存淘汰算法会优先移除最近最少使用的数据。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;
        }
        // 更新访问时间
        $this->cache[$key]['time'] = microtime(true);
        return $this->cache[$key]['value'];
    }

    public function put($key, $value) {
        // 存在则更新
        if (isset($this->cache[$key])) {
            $this->cache[$key] = [
                'value' => $value,
                'time' => microtime(true)
            ];
            return;
        }

        // 超过容量时移除LRU项
        if (count($this->cache) >= $this->capacity) {
            $minTime = PHP_FLOAT_MAX;
            $lruKey = null;
            foreach ($this->cache as $k => $v) {
                if ($v['time'] < $minTime) {
                    $minTime = $v['time'];
                    $lruKey = $k;
                }
            }
            unset($this->cache[$lruKey]);
        }

        $this->cache[$key] = [
            'value' => $value,
            'time' => microtime(true)
        ];
    }
}

基于双向链表的实现

双向链表能高效处理节点移动，结合哈希表实现 O(1) 访问：

class ListNode {
    public $key;
    public $value;
    public $prev;
    public $next;

    public function __construct($key, $value) {
        $this->key = $key;
        $this->value = $value;
    }
}

class LRUCache {
    private $capacity;
    private $map = [];
    private $head;
    private $tail;

    public function __construct($capacity) {
        $this->capacity = $capacity;
        $this->head = new ListNode(-1, -1);
        $this->tail = new ListNode(-1, -1);
        $this->head->next = $this->tail;
        $this->tail->prev = $this->head;
    }

    private function moveToHead($node) {
        $this->removeNode($node);
        $this->addNode($node);
    }

    private function addNode($node) {
        $node->prev = $this->head;
        $node->next = $this->head->next;
        $this->head->next->prev = $node;
        $this->head->next = $node;
    }

    private function removeNode($node) {
        $node->prev->next = $node->next;
        $node->next->prev = $node->prev;
    }

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

    public function put($key, $value) {
        if (isset($this->map[$key])) {
            $node = $this->map[$key];
            $node->value = $value;
            $this->moveToHead($node);
            return;
        }

        if (count($this->map) >= $this->capacity) {
            $lru = $this->tail->prev;
            $this->removeNode($lru);
            unset($this->map[$lru->key]);
        }

        $node = new ListNode($key, $value);
        $this->addNode($node);
        $this->map[$key] = $node;
    }
}

性能对比

• 数组实现：代码简单但效率较低，put 操作需遍历所有元素找 LRU，时间复杂度 O(n)。
• 链表实现：get 和 put 均为 O(1)，适合高频访问场景，但代码复杂度较高。

实际应用中推荐链表实现，或直接使用 PHP 扩展如 Redis 内置的 LRU 功能。