LRU（最近最少使用）缓存数据结构

LRU（最近最少使用）缓存是一种缓存，当缓存超出其容量时，它会逐出最近最少访问的项目。它在内存有限且您只想缓存最常访问的数据的场景中非常有用。

在 JavaScript 中，LRU 缓存可以使用 Map（用于快速查找和维护插入顺序）和双向链表（用于两端高效插入和删除）的组合来实现。但是，为了简单起见，我们将在以下实现中使用 Map。

这是 LRU 缓存的 JavaScript 实现：

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map(); // Using Map to maintain key-value pairs
    }
    // Get the value from the cache
    get(key) {
        if (!this.cache.has(key)) {
            return -1; // If the key is not found, return -1
        }

        // Key is found, move the key to the most recent position
        const value = this.cache.get(key);
        this.cache.delete(key); // Remove the old entry
        this.cache.set(key, value); // Reinsert to update its position (most recently used)

        return value;
    }

    // Add or update the value in the cache
    put(key, value) {
        if (this.cache.has(key)) {
            // If the key already exists, remove it to update its position
            this.cache.delete(key);
        } else if (this.cache.size >= this.capacity) {
            // If the cache is at capacity, delete the least recently used item
            const leastRecentlyUsedKey = this.cache.keys().next().value;
            this.cache.delete(leastRecentlyUsedKey);
        }

        // Insert the new key-value pair (most recent)
        this.cache.set(key, value);
    }
}

说明：
构造函数：LRUCache类用给定的容量进行初始化，它使用Map来存储缓存的键值对。地图会跟踪插入顺序，这有助于识别最近最少使用 (LRU) 的项目。

获取（密钥）：

• 如果缓存中存在该键，该方法将返回其值，并通过先删除该键然后重新插入该键将其移动到最近的位置。
• 如果键不存在，则返回-1。

put（键，值）：

• 如果缓存中已存在该密钥，则会删除该密钥并重新插入它（将其位置更新为最近使用的位置）。
• 如果缓存达到其容量，它将删除最近最少使用的键（Map 中的第一个键）。
• 最后，新的键值对被添加到缓存中。

使用示例：

const lruCache = new LRUCache(3); // Cache with a capacity of 3

lruCache.put(1, 'one');   // Add key 1
lruCache.put(2, 'two');   // Add key 2
lruCache.put(3, 'three'); // Add key 3

console.log(lruCache.get(1)); // Output: 'one' (key 1 becomes the most recently used)

lruCache.put(4, 'four'); // Cache is full, so it evicts key 2 (least recently used)

console.log(lruCache.get(2)); // Output: -1 (key 2 has been evicted)
console.log(lruCache.get(3)); // Output: 'three' (key 3 is still in the cache)
console.log(lruCache.get(4)); // Output: 'four' (key 4 is in the cache)

以上是LRU（最近最少使用）缓存数据结构的详细内容。更多信息请关注PHP中文网其他相关文章！