캐시(Cache)는 데이터나 연산 결과를 일시적으로 저장하는 것을 가리킨다. 자주 사용하는 데이터나 연산 결과를 메모리 영역에 보관해서 동일한 정보를 요청받았을 때 더 빠른 속도로 제공할 수 있다.
LRU 캐시는 대표적인 캐시 알고리즘 중 하나로 제한된 저장 공간을 관리하기 위해 가장 오래전에 사용한 데이터를 제거하는 알고리즘이다. LRU는 Least Recently Used의 약자로 사용한지 가장 오래된 정도로 해석할 수 있다.
LRU 캐시에선 조회/쓰기시 해당 값을 가장 최근에 사용한 것으로 처리하는게 핵심이다. 자바스크립트 Map 등을 이용해서 구현할 땐 값이 뒤에 위치할 수록 가장 최근에 사용한 것으로 표시한다.
class LRUCache {
constructor(capacity) {
/** 캐시 최대 용량 설정 */
this.capacity = capacity;
/** 삽입 순서를 기억하는 Map으로 캐시 관리, 가장 최근에 사용한 key가 뒤에 위치 */
this.cache = new Map();
}
/**
* 주어진 key에 해당하는 값을 캐시에서 가져오는 메서드
* 값이 존재하면 key를 캐시의 끝으로 위치시켜서 가장 최근에 사용한 것으로 표시 (LRU 캐시 특징)
*/
get(key) {
if (!this.cache.has(key)) return -1;
const value = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, value); // 조회한 key를 캐시 가장 마지막에 위치 시킴
return value;
}
/**
* 새로운 key-value 쌍을 캐시에 추가하는 메서드
* key가 존재하면 해당 key를 삭제하고 캐시 마지막에 새 항목으로 추가
* 캐시가 가득 찼다면, 가장 오래된 앞쪽 key를 제거하고, 캐시 마지막에 새 항목 추가
*/
put(key, value) {
if (this.cache.has(key)) {
this.cache.delete(key); // key가 이미 존재하면 삭제
} else if (this.cache.size === this.capacity) {
const oldestKey = this.cache.keys().next().value; // this.cache의 첫번째 값(사용한지 가장 오래된 key)
this.cache.delete(oldestKey);
}
this.cache.set(key, value); // 새 항목을 캐시 마지막에 추가
}
}
this.capacity 프로퍼티를 통해 캐시가 보관할 수 있는 항목의 수를 제한한다. 이 값을 초과할 경우 캐시의 가장 오래된 항목을 제거하여 새 항목을 저장할 공간을 만든다.
캐시 데이터 this.cache는 삽입 순서를 기억하는 Map으로 관리한다. LRU 캐시에서 가장 최근에 사용한 키는 Map 뒷부분에 위치시킨다. 새 항목을 캐시에 추가하거나 기존 항목을 다시 사용할 땐, 해당 항목을 Map 뒷부분으로 이동하여 최근 사용함으로 나타낸다.
캐시에서 주어진 key에 해당하는 값을 가져오는 메서드. 조회할 key가 캐시에 존재하지 않으면 -1을 반환하고, 존재한다면 해당 key를 캐시 마지막에 위치시켜서 최근에 사용한 것으로 표시한다.
새로운 key-value 쌍을 캐시에 추가하는 메서드. 캐시에 이미 key가 존재한다면 기존 key를 삭제하고 캐시 마지막에 새 항목으로 추가한다. 캐시가 가득 찼다면 사용한지 가장 오래된 앞쪽 key를 제거하고, 캐시 마지막에 새 항목을 추가한다.
여기서 주목할 점은 가장 오래된 key를 가져올 때 사용한 next() 메서드다. this.cache.keys()를 호출하면 캐시 키들을 순회할 수 있는 이터레이터를 반환한다. 🔍 배열에선 Symbol.iterator 프로퍼티에 접근해서 호출하면 이터레이터 객체를 얻을 수 있다.