当前位置：首页 > PHP

php实现lru

2026-01-29 18:29:01PHP

PHP实现LRU缓存算法

LRU（Least Recently Used）是一种常见的缓存淘汰策略，核心思想是当缓存空间不足时优先移除最近最少使用的数据。以下是PHP实现LRU缓存的两种典型方式：

双向链表+哈希表实现

使用双向链表维护访问顺序，哈希表实现快速查找，时间复杂度O(1)：

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

    function __construct($capacity) {
        $this->capacity = $capacity;
        $this->head = new Node(0, 0);
        $this->tail = new Node(0, 0);
        $this->head->next = $this->tail;
        $this->tail->prev = $this->head;
    }

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

    function put($key, $value) {
        if (isset($this->map[$key])) {
            $node = $this->map[$key];
            $node->value = $value;
            $this->removeNode($node);
            $this->addToHead($node);
        } else {
            $node = new Node($key, $value);
            $this->map[$key] = $node;
            $this->addToHead($node);
            if (count($this->map) > $this->capacity) {
                $last = $this->tail->prev;
                $this->removeNode($last);
                unset($this->map[$last->key]);
            }
        }
    }

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

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

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

使用PHP内置数组模拟

简化版实现，利用array_keys()维护访问顺序：

class SimpleLRU {
    private $capacity;
    private $cache = [];

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

    public function get($key) {
        if (!isset($this->cache[$key])) return null;
        $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;
    }
}