当前位置：首页 > PHP

lru php实现

2026-01-29 23:01:18PHP

PHP实现LRU缓存算法

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

使用双向链表+哈希表实现

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

    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;
    }

    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 {
            if (count($this->map) >= $this->capacity) {
                $last = $this->tail->prev;
                $this->removeNode($last);
                unset($this->map[$last->key]);
            }
            $node = new Node($key, $value);
            $this->map[$key] = $node;
            $this->addToHead($node);
        }
    }

    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;
    }
}

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

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

使用PHP内置数据结构实现

class SimpleLRUCache {
    private $capacity;
    private $cache = [];
    private $order = [];

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

    public function get($key) {
        if (!isset($this->cache[$key])) {
            return null;
        }

        // 更新访问顺序
        $index = array_search($key, $this->order);
        unset($this->order[$index]);
        array_unshift($this->order, $key);

        return $this->cache[$key];
    }

    public function put($key, $value) {
        if (isset($this->cache[$key])) {
            // 更新现有值
            $this->cache[$key] = $value;
            $index = array_search($key, $this->order);
            unset($this->order[$index]);
        } else {
            // 检查容量
            if (count($this->cache) >= $this->capacity) {
                $oldest = array_pop($this->order);
                unset($this->cache[$oldest]);
            }
            $this->cache[$key] = $value;
        }
        array_unshift($this->order, $key);
    }
}