当前位置：首页 > PHP

php实现lru

2026-02-14 16:25:01PHP

LRU缓存实现原理

LRU（Least Recently Used）缓存淘汰算法会优先移除最久未被使用的数据。PHP实现通常需要结合哈希表和双向链表，哈希表保证O(1)的查询速度，双向链表维护访问顺序。

双向链表节点类

定义链表节点结构，包含key、value以及前后指针：

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

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

LRU缓存类结构

初始化缓存容量、哈希表和虚拟头尾节点：

class LRUCache {
    private $capacity;
    private $hashmap = [];
    private $dummyHead;
    private $dummyTail;

    public function __construct($capacity) {
        $this->capacity = $capacity;
        $this->dummyHead = new ListNode(null, null);
        $this->dummyTail = new ListNode(null, null);
        $this->dummyHead->next = $this->dummyTail;
        $this->dummyTail->prev = $this->dummyHead;
    }
}

链表操作辅助方法

添加节点到链表头部：

php实现lru

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

移除指定节点：

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

移动节点到头部：

php实现lru

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

移除尾部节点：

private function removeTail() {
    $node = $this->dummyTail->prev;
    $this->removeNode($node);
    return $node;
}

核心缓存操作方法

获取缓存值：

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

写入缓存值：

public function put($key, $value) {
    if (isset($this->hashmap[$key])) {
        $node = $this->hashmap[$key];
        $node->value = $value;
        $this->moveToHead($node);
    } else {
        $node = new ListNode($key, $value);
        $this->hashmap[$key] = $node;
        $this->addToHead($node);

        if (count($this->hashmap) > $this->capacity) {
            $removed = $this->removeTail();
            unset($this->hashmap[$removed->key]);
        }
    }
}

使用示例

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