[Algorithm] 자바스크립트 Map으로 구현하는 LRU Cache 알고리즘

LRU 캐시 특징

---

캐시(Cache)는 데이터나 연산 결과를 일시적으로 저장하는 것을 가리킨다. 자주 사용하는 데이터나 연산 결과를 메모리 영역에 보관해서 동일한 정보를 요청받았을 때 더 빠른 속도로 제공할 수 있다.

 

LRU 캐시는 대표적인 캐시 알고리즘 중 하나로 제한된 저장 공간을 관리하기 위해 가장 오래전에 사용한 데이터를 제거하는 알고리즘이다. LRU는 Least Recently Used의 약자로 사용한지 가장 오래된 정도로 해석할 수 있다.

 

LRU 캐시에선 조회/쓰기시 해당 값을 가장 최근에 사용한 것으로 처리하는게 핵심이다. 자바스크립트 Map 등을 이용해서 구현할 땐 값이 뒤에 위치할 수록 가장 최근에 사용한 것으로 표시한다.

 

1. 조회 : 캐시에 값이 존재하면 해당 값을 캐시 마지막(최신)으로 이동시킨다
2. 쓰기 :
   • 캐시에 값이 존재하면 기존 값을 삭제하고, 캐시 마지막에 기존 값을 추가한다
   • 캐시가 가득 찼다면 가장 오래된 앞쪽 값을 제거하고, 캐시 마지막에 새로운 값을 추가한다

 

 

LRU 캐시 구현

---

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 뒷부분으로 이동하여 최근 사용함으로 나타낸다.

 

Get

캐시에서 주어진 key에 해당하는 값을 가져오는 메서드. 조회할 key가 캐시에 존재하지 않으면 -1을 반환하고, 존재한다면 해당 key를 캐시 마지막에 위치시켜서 최근에 사용한 것으로 표시한다.

 

Set

새로운 key-value 쌍을 캐시에 추가하는 메서드. 캐시에 이미 key가 존재한다면 기존 key를 삭제하고 캐시 마지막에 새 항목으로 추가한다. 캐시가 가득 찼다면 사용한지 가장 오래된 앞쪽 key를 제거하고, 캐시 마지막에 새 항목을 추가한다.

 

이터레이터 ⭐

여기서 주목할 점은 가장 오래된 key를 가져올 때 사용한 next() 메서드다. this.cache.keys()를 호출하면 캐시 키들을 순회할 수 있는 이터레이터를 반환한다. 🔍 배열에선 Symbol.iterator 프로퍼티에 접근해서 호출하면 이터레이터 객체를 얻을 수 있다.

const cache = new Map();
cache.set('a', 1);
cache.set('b', 2);
cache.set('c', 3);
cache.keys(); // MapIterator {'a', 'b', 'c'}

 

Symbol.iterator 메서드가 구현되어 있는 객체를 이터러블 객체라고 부르는데, 배열 / 문자열 / Map / Set 등이 대표적인 이터러블이다. Symbol.iterator 메서드를 호출하면 이터레이터 객체를 반환하고, 이터레이터 객체 안에는 next() 메서드가 구현되어 있다.

 

next() 메서드를 호출하면 value, done 프로퍼티를 갖는 이터레이터 리절트 객체를 반환한다. value는 현재 순회중인 이터러블의 값이고, done은 반복 종료 여부를 나타낸다.

 

이러한 특성 때문에 next() 메서드를 호출할 때마다 value 프로퍼티를 통해 값을 순차적으로 가져올 수 있다. for of 문으로 값을 순회할 때도 내부적으로 next() 메서드를 호출해서 value 값을 가져오는 것.

const array = [1, 2, 3]; // 배열은 이터러블 프로토콜을 준수한 이터러블이다
const iterator = array[Symbol.iterator](); // next 메서드를 갖는 이터레이터 객체 반환

// next() 메서드가 반환하는 이터레이터 리절트 객체는 value와 done 프로퍼티를 갖는다
iterator.next(); // { value: 1, done: false }
iterator.next(); // { value: 2, done: false }
iterator.next(); // { value: 3, done: false }
iterator.next(); // { value: undefined, done: true }

 

this.cache.keys()가 반환하는 이터레이터의 프로토타입을 살펴보면 next() 메서드가 구현돼 있다. 위와 마찬가지로 next() 메서드를 호출하면 이터레이터 리절트 객체를 반환하고, 이 객체의 value 프로퍼티를 통해 순회중인 이터러블의 값을 가져올 수 있다.

 

 

const iterator = cache.keys();
iterator.next(); // {value: 'a', done: false}
iterator.next(); // {value: 'b', done: false}
iterator.next(); // {value: 'c', done: false}
iterator.next(); // {value: undefined, done: true}

 

위에서 구현한 LRU Cache 에선 put 메서드에 있는 this.cache.keys().next()를 1회 호출 했으므로 next().value는 가장 오래된 값을 가리키는, this.cache의 첫번째 요소를 가져온다.

 

---

글 수정사항은 노션 페이지에 가장 빠르게 반영됩니다. 링크를 참고해 주세요