LRU(Least Recent Used) 캐시 데이터 구조

LRU(Least Recent Used) 캐시는 캐시가 용량을 초과할 때 가장 최근에 액세스한 항목을 제거하는 캐시 유형입니다. 메모리가 제한되어 있고 가장 자주 액세스하는 데이터만 캐시하려는 시나리오에서 유용합니다.

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 클래스는 지정된 용량으로 초기화되며 맵을 사용하여 캐시된 키-값 쌍을 저장합니다. 지도는 삽입 순서를 추적하여 가장 최근에 사용되지 않은(LRU) 항목을 식별하는 데 도움이 됩니다.

get(키):

• 키가 캐시에 존재하는 경우 메서드는 해당 값을 반환하고 먼저 키를 삭제한 다음 다시 삽입하여 키를 가장 최근 위치로 이동합니다.
• 키가 존재하지 않으면 -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(Least Recent Used) 캐시 데이터 구조의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!