LRU (Least Recently Used) Cache Data Structure

LRU (Least Recently Used) Cache is a type of cache that evicts the least recently accessed item when the cache exceeds its capacity. It's useful in scenarios where memory is limited, and you want to cache only the most frequently accessed data.

In JavaScript, an LRU Cache can be implemented using a combination of a Map (for fast lookups and maintaining insertion order) and a Doubly Linked List (for efficient insertions and deletions at both ends). However, for simplicity, we'll use a Map in the following implementation.

Here’s a JavaScript implementation of an LRU Cache:

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

Explanation:
Constructor: The LRUCache class is initialized with a given capacity, and it uses a Map to store the cached key-value pairs. The Map keeps track of the insertion order, which helps identify the least recently used (LRU) item.

get(key):

• If the key exists in the cache, the method returns its value and moves the key to the most recent position by first deleting the key and then reinserting it.
• If the key doesn't exist, it returns -1.

put(key, value):

• If the key already exists in the cache, it removes the key and reinserts it (updating its position as the most recently used).
• If the cache reaches its capacity, it removes the least recently used key (the first one in the Map).
• Finally, the new key-value pair is added to the cache.

Usage Example:

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)

The above is the detailed content of LRU (Least Recently Used) Cache Data Structure. For more information, please follow other related articles on the PHP Chinese website!