php 实现lru

PHP 实现 LRU 缓存算法

LRU（Least Recently Used）是一种常用的缓存淘汰策略，优先淘汰最近最少使用的数据。以下是 PHP 实现 LRU 的两种常见方法：

方法一：使用数组和哈希表结合

通过数组维护访问顺序，哈希表存储键值对，实现 O(1) 时间复杂度的访问和插入。

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)]);
        array_push($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)]);
        } elseif (count($this->cache) >= $this->capacity) {
            // 淘汰最久未使用的元素
            $lruKey = array_shift($this->order);
            unset($this->cache[$lruKey]);
        }
        $this->cache[$key] = $value;
        array_push($this->order, $key);
    }
}

方法二：使用双向链表和哈希表

通过双向链表维护访问顺序，哈希表存储节点引用，实现更高效的节点移动操作。

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

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 addToHead($node) {
        $node->next = $this->head->next;
        $node->prev = $this->head;
        $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->removeNode($node);
        $this->addToHead($node);
        return $node->val;
    }

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

使用示例

$lru = new LRUCache(2);
$lru->put(1, 1);
$lru->put(2, 2);
echo $lru->get(1); // 返回 1
$lru->put(3, 3);   // 淘汰键 2
echo $lru->get(2); // 返回 -1

注意事项

• 方法一的数组操作在大量数据时性能较低，因为 array_search 和 array_shift 是 O(n) 操作。
• 方法二的双向链表实现更高效，所有操作均为 O(1) 时间复杂度。
• 实际应用中可根据场景选择合适实现，小型缓存使用方法一更简单，高性能场景推荐方法二。