当前位置：首页 > PHP

lru算法PHP实现

2026-03-13 07:31:20PHP

LRU算法的基本概念

LRU（Least Recently Used）算法是一种常用的缓存淘汰策略，其核心思想是淘汰最近最少使用的数据。当缓存空间不足时，优先移除最久未被访问的数据。

PHP实现LRU算法的关键步骤

使用哈希表和双向链表结合的方式可以实现高效的LRU算法。哈希表用于快速查找键值，双向链表用于维护访问顺序。

lru算法PHP实现

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

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

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

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

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

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

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

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

实现细节说明

Node类：表示双向链表的节点，包含键、值、前驱和后继指针。
LRUCache类：包含哈希表（$map）和双向链表（$head和$tail）。
get方法：获取键对应的值，并将节点移到链表头部表示最近使用。
put方法：插入或更新键值对，如果超过容量则移除链表尾部节点。
removeNode和addToFront：维护双向链表的操作，确保O(1)时间复杂度。

使用示例

$cache = new LRUCache(2);
$cache->put(1, 1);
$cache->put(2, 2);
echo $cache->get(1); // 返回 1
$cache->put(3, 3);   // 移除键 2
echo $cache->get(2); // 返回 -1