LRU缓存策略 (经典算法题500道),程序员经典面试笔试题目, 码小课

当前位置：面试刷题>> LRU缓存策略 (经典算法题500道)

题目描述补充

LRU（Least Recently Used）缓存策略是一种常用的页面置换算法，用于管理缓存中的数据，确保当缓存达到其容量限制时，能够移除最久未使用的数据，以便为新的数据腾出空间。具体实现时，通常需要快速判断哪些数据是最久未使用的，并能在常数时间内完成插入、访问和删除操作。

题目要求

实现一个基于LRU策略的缓存机制，该机制应支持以下操作：

get(key): 如果缓存中存在该键，则返回对应的值，并更新该键为最近使用；如果缓存中不存在该键，则返回-1。
put(key, value): 如果缓存中已存在该键，则更新其值并标记为最近使用；如果缓存中不存在该键，则插入该键值对，如果此时缓存达到容量限制，则移除最久未使用的数据项（键值对）。

缓存的容量作为参数传递给缓存类的构造函数。

示例代码

PHP 示例

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

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

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

        // 更新使用顺序
        $this->moveToFront($key);

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

    function put($key, $value) {
        if (isset($this->cache[$key])) {
            // 更新值并移动到链表前端
            $this->cache[$key]->value = $value;
            $this->moveToFront($key);
            return;
        }

        $newNode = new stdClass();
        $newNode->key = $key;
        $newNode->value = $value;

        $this->cache[$key] = $newNode;
        $this->usedOrder->push($newNode);

        if (count($this->cache) > $this->capacity) {
            $tail = $this->usedOrder->pop();
            unset($this->cache[$tail->key]);
        }
    }

    private function moveToFront($key) {
        $node = $this->cache[$key];
        $this->usedOrder->detach($this->getIteratorByValue($node));
        $this->usedOrder->push($node);
    }

    private function getIteratorByValue($value) {
        foreach ($this->usedOrder as $key => $node) {
            if ($node === $value) {
                return $key;
            }
        }
        return false;
    }
}

注意：PHP 的 SplDoublyLinkedList 不直接支持通过值获取键，这里的 getIteratorByValue 方法是模拟的，实际使用时可能需要更复杂的逻辑或数据结构。

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:
            self.cache.move_to_end(key)  # 更新键的位置
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # 移除最久未使用的数据项（即有序字典的开头）

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);
        }
        this.cache.set(key, value);
        if (this.cache.size > this.capacity) {
            const firstKey = this.cache.keys().next().value; // 获取最久未使用的键
            this.cache.delete(firstKey);
        }
    }
}

请注意，JavaScript 示例中对于 Map 的迭代和删除最久未使用的元素实现可能因环境而异，上述实现依赖于 Map 迭代器的行为，这在大多数现代 JavaScript 环境中是有效的。