LRU (最も最近使用されていない) キャッシュ データ構造

LRU (最も最近使用されていない) キャッシュは、キャッシュの容量を超えた場合に最も最近アクセスされていない項目を削除するキャッシュのタイプです。これは、メモリが限られており、最も頻繁にアクセスされるデータのみをキャッシュしたいシナリオで役立ちます。

JavaScript では、マップ (高速検索と挿入順序の維持用) と二重リンク リスト (両端での効率的な挿入と削除用) の組み合わせを使用して LRU キャッシュを実装できます。ただし、簡単にするために、次の実装では 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) アイテムを特定するのに役立ちます。

get(key):

• キーがキャッシュに存在する場合、メソッドはその値を返し、最初にキーを削除してから再挿入することにより、キーを最新の位置に移動します。
• キーが存在しない場合は、-1 を返します。

put(キー, 値):

• キーがキャッシュにすでに存在する場合は、キーを削除して再挿入します (その位置を最後に使用されたものとして更新します)。
• キャッシュがその容量に達すると、最も最近使用されていないキー (マップ内の最初のキー) が削除されます。
• 最後に、新しいキーと値のペアがキャッシュに追加されます。

使用例:

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 中国語 Web サイトの他の関連記事を参照してください。