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中文網其他相關文章！