LRU-Cache-Datenstruktur (Least Recent Used).

LRU (Least Recent Used) Cache ist eine Art Cache, der das zuletzt aufgerufene Element entfernt, wenn der Cache seine Kapazität überschreitet. Dies ist in Szenarien nützlich, in denen der Speicher begrenzt ist und Sie nur die Daten zwischenspeichern möchten, auf die am häufigsten zugegriffen wird.

In JavaScript kann ein LRU-Cache mithilfe einer Kombination aus einer Karte (für schnelle Suchvorgänge und Beibehaltung der Einfügereihenfolge) und einer doppelt verknüpften Liste (für effiziente Einfügungen und Löschungen an beiden Enden) implementiert werden. Der Einfachheit halber verwenden wir in der folgenden Implementierung jedoch eine Map.

Hier ist eine JavaScript-Implementierung eines 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);
    }
}

Erklärung:
Konstruktor: Die LRUCache-Klasse wird mit einer bestimmten Kapazität initialisiert und verwendet eine Map zum Speichern der zwischengespeicherten Schlüssel-Wert-Paare. Die Karte verfolgt die Einfügungsreihenfolge, was dabei hilft, das am wenigsten kürzlich verwendete Element (LRU) zu identifizieren.

get(key):

• Wenn der Schlüssel im Cache vorhanden ist, gibt die Methode seinen Wert zurück und verschiebt den Schlüssel an die aktuellste Position, indem sie zuerst den Schlüssel löscht und ihn dann erneut einfügt.
• Wenn der Schlüssel nicht existiert, wird -1 zurückgegeben.

put(key, value):

• Wenn der Schlüssel bereits im Cache vorhanden ist, wird er entfernt und erneut eingefügt (wobei seine Position als die zuletzt verwendete aktualisiert wird).
• Wenn der Cache seine Kapazität erreicht, wird der zuletzt verwendete Schlüssel (der erste in der Karte) entfernt.
• Schließlich wird das neue Schlüssel-Wert-Paar zum Cache hinzugefügt.

Verwendungsbeispiel:

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)

Das obige ist der detaillierte Inhalt vonLRU-Cache-Datenstruktur (Least Recent Used).. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!