当前位置：首页 > PHP

lru php实现

2026-02-14 20:54:17PHP

LRU 缓存算法的 PHP 实现

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

使用数组和时间戳实现

通过维护一个数组记录键值对，并为每个键附加最后访问时间戳来实现 LRU 逻辑。

class LRUCache {
    private $capacity;
    private $cache = [];
    private $timestamps = [];

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

    public function get($key) {
        if (isset($this->cache[$key])) {
            $this->timestamps[$key] = microtime(true);
            return $this->cache[$key];
        }
        return -1;
    }

    public function put($key, $value) {
        if (count($this->cache) >= $this->capacity && !isset($this->cache[$key])) {
            asort($this->timestamps);
            $oldest = key($this->timestamps);
            unset($this->cache[$oldest], $this->timestamps[$oldest]);
        }
        $this->cache[$key] = $value;
        $this->timestamps[$key] = 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 addNode($node) {
        $node->prev = $this->head;
        $node->next = $this->head->next;
        $this->head->next->prev = $node;
        $this->head->next = $node;
    }

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

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

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

    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);
        } else {
            if (count($this->map) >= $this->capacity) {
                $tail = $this->popTail();
                unset($this->map[$tail->key]);
            }
            $node = new ListNode($key, $value);
            $this->map[$key] = $node;
            $this->addNode($node);
        }
    }
}

使用 SplDoublyLinkedList 实现

PHP 标准库提供的双向链表可以简化实现：

class LRUCache {
    private $capacity;
    private $map = [];
    private $list;

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

    public function get($key) {
        if (!isset($this->map[$key])) return -1;
        $this->list->unshift($this->map[$key]);
        $this->list->offsetUnset($this->list->key());
        return $this->map[$key]['value'];
    }

    public function put($key, $value) {
        if (isset($this->map[$key])) {
            $this->list->unshift(['key' => $key, 'value' => $value]);
            $this->list->offsetUnset($this->list->key());
        } else {
            if (count($this->map) >= $this->capacity) {
                $oldest = $this->list->pop();
                unset($this->map[$oldest['key']]);
            }
            $this->list->unshift(['key' => $key, 'value' => $value]);
        }
        $this->map[$key] = $this->list->bottom();
    }
}