LRU 缓存机制

题目描述： 设计并实现一个 LRU（最近最少使用）缓存机制。该机制将允许你获取和设置键值对，并且会在每次访问（无论是获取还是设置）后更新键的顺序，使得最近使用的键总是排在最前面。如果缓存容量已满，则应当移除最久未使用的键（即最末尾的键）。

示例：

• 缓存容量 capacity = 2
• 操作序列：
  1. cache.put(1, 1)
  2. cache.put(2, 2)
  3. cache.get(1) // 返回 1
  4. cache.put(3, 3) // 该操作会使键 2 作废
  5. cache.get(2) // 返回 -1 (未找到)
  6. cache.get(3) // 返回 3
  7. cache.put(4, 4) // 该操作会使键 1 作废
  8. cache.get(1) // 返回 -1 (未找到)
  9. cache.get(3) // 返回 3
  10. cache.get(4) // 返回 4

要求：

• get(key) 方法应返回键对应的值，如果键不存在则返回 -1。
• put(key, value) 方法应插入或更新键的值。如果缓存达到其容量，则应该在插入新项之前使最近最少使用的项无效。

PHP 实现

class LRUCache {
    private $capacity;
    private $cache;
    private $keys;

    function __construct($capacity) {
        $this->capacity = $capacity;
        $this->cache = [];
        $this->keys = new SplDoublyLinkedList();
    }

    function get($key) {
        if (!$this->keys->contains($key)) {
            return -1;
        }

        // 移除旧的节点
        $this->keys->offsetUnset($key);
        // 添加到头部（最近使用）
        $this->keys->offsetSet(0, $key);

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

    function put($key, $value) {
        if ($this->keys->contains($key)) {
            // 如果键已存在，先移除旧的
            $this->keys->offsetUnset($key);
        }

        // 添加新值
        $this->cache[$key] = $value;

        // 添加到头部（最近使用）
        if ($this->keys->count() >= $this->capacity) {
            // 移除最久未使用的项
            $oldestKey = $this->keys->bottom();
            $this->keys->offsetUnset($oldestKey);
            unset($this->cache[$oldestKey]);
        }
        $this->keys->offsetSet(0, $key);
    }
}

注意：PHP 标准库中并没有直接支持双向链表的类，这里为了演示方便，使用了 SplDoublyLinkedList 类来模拟键的顺序，但请注意，它并不直接支持通过值来快速移除节点，因此这里的 contains 和 offsetUnset 方法仅用于示意，实际实现中可能需要额外的数据结构或逻辑来优化。

Python 实现

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        else:
            # 将访问的键值对移动到最前面
            self.cache.move_to_end(key)
            return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # 如果键已存在，先移除旧的
            del self.cache[key]
        elif len(self.cache) >= self.capacity:
            # 移除最久未使用的项
            self.cache.popitem(last=False)
        # 插入新键值对到最前面
        self.cache[key] = value

JavaScript 实现

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
    }

    get(key) {
        if (!this.cache.has(key)) {
            return -1;
        }
        // 移除旧的节点
        const value = this.cache.get(key);
        this.cache.delete(key);
        // 添加到头部（最近使用）
        this.cache.set(key, value);
        return value;
    }

    put(key, value) {
        if (this.cache.has(key)) {
            // 如果键已存在，先移除旧的
            this.cache.delete(key);
        } else if (this.cache.size >= this.capacity) {
            // 移除最久未使用的项
            const firstKey = this.cache.keys().next().value;
            this.cache.delete(firstKey);
        }
        // 插入新键值对
        this.cache.set(key, value);
    }
}

以上代码分别用 PHP、Python 和 JavaScript 实现了 LRU 缓存机制，每种语言都利用了其内置的数据结构来优化操作效率。