php实现lru

PHP实现LRU缓存算法

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

双向链表+哈希表实现

使用双向链表维护数据的使用顺序，哈希表存储键值对以实现快速访问。

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

    function __construct($capacity) {
        $this->capacity = $capacity;
        $this->head = new Node(0, 0);
        $this->tail = new Node(0, 0);
        $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->remove($node);
        $this->add($node);
        return $node->value;
    }

    function put($key, $value) {
        if (isset($this->map[$key])) {
            $this->remove($this->map[$key]);
        }
        $node = new Node($key, $value);
        $this->map[$key] = $node;
        $this->add($node);
        if (count($this->map) > $this->capacity) {
            $node = $this->tail->prev;
            $this->remove($node);
            unset($this->map[$node->key]);
        }
    }

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

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

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

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

使用PHP内置数组实现

利用PHP数组的键值对和array_shift等函数简化实现。

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

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

    function get($key) {
        if (!isset($this->cache[$key])) return -1;
        $value = $this->cache[$key];
        unset($this->cache[$key]);
        $this->cache[$key] = $value;
        return $value;
    }

    function put($key, $value) {
        if (isset($this->cache[$key])) {
            unset($this->cache[$key]);
        } elseif (count($this->cache) >= $this->capacity) {
            array_shift($this->cache);
        }
        $this->cache[$key] = $value;
    }
}

使用SplDoublyLinkedList实现

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

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

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

    function get($key) {
        if (!isset($this->map[$key])) return -1;
        $node = $this->map[$key];
        $this->list->detach($node);
        $this->list->push($node);
        return $node->value;
    }

    function put($key, $value) {
        if (isset($this->map[$key])) {
            $node = $this->map[$key];
            $this->list->detach($node);
        }
        $node = new SplDoublyLinkedListNode($value);
        $node->key = $key;
        $this->map[$key] = $node;
        $this->list->push($node);
        if (count($this->map) > $this->capacity) {
            $oldest = $this->list->shift();
            unset($this->map[$oldest->key]);
        }
    }
}

性能比较

双向链表+哈希表实现提供了O(1)时间复杂度的get和put操作，是最优的实现方式。PHP数组实现简单但性能较差，特别是在缓存较大时。SplDoublyLinkedList实现介于两者之间。

实际应用中应根据具体需求选择实现方式，对于高性能要求的场景推荐使用第一种实现。