🛠️ 처음부터 만드는 LRU Cache — 가장 오래된 데이터를 자동으로 버리기

문제

API 응답, 계산 결과, DB 쿼리 등을 캐싱하고 싶지만 메모리는 무한하지 않습니다. 가장 최근에 사용하지 않은(Least Recently Used) 항목부터 자동으로 제거하는 캐시가 필요합니다.

핵심 아이디어

`Map`은 삽입 순서를 기억합니다. `get`할 때마다 해당 항목을 삭제 후 다시 삽입하면, Map의 마지막 항목이 가장 최근에 사용된 것, 첫 번째 항목이 가장 오래된 것이 됩니다.

코드

```typescript
class LRUCache {
private cache = new Map();
constructor(private readonly capacity: number) {
if (capacity < 1) throw new Error('capacity must be >= 1');
}
get(key: K): V | undefined {
if (!this.cache.has(key)) return undefined;
// 꺼냈다가 다시 넣어서 "최근 사용" 위치로 이동
const value = this.cache.get(key)!;
this.cache.delete(key);
this.cache.set(key, value);
return value;
}
set(key: K, value: V): void {
// 이미 있으면 삭제 (순서 갱신을 위해)
if (this.cache.has(key)) {
this.cache.delete(key);
}
this.cache.set(key, value);
// 용량 초과 시 가장 오래된 항목(첫 번째) 제거
if (this.cache.size > this.capacity) {
const oldestKey = this.cache.keys().next().value!;
this.cache.delete(oldestKey);
}
}
get size(): number {
return this.cache.size;
}
}
```

사용 예시

```typescript
const cache = new LRUCache(3);
cache.set('user:1', { name: 'Alice' });
cache.set('user:2', { name: 'Bob' });
cache.set('user:3', { name: 'Charlie' });
cache.get('user:1'); // Alice를 "최근 사용"으로 갱신
cache.set('user:4', { name: 'Dave' }); // 용량 초과 → user:2 제거 (가장 오래됨)
console.log(cache.get('user:2')); // undefined (퇴거됨)
console.log(cache.get('user:1')); // { name: 'Alice' } (살아있음!)
```

실전 활용: API 응답 캐싱

```typescript
const apiCache = new LRUCache(100);
const TTL = 60_000; // 1분
async function cachedFetch(url: string): Promise {
const cached = apiCache.get(url);
if (cached && Date.now() - cached.ts < TTL) {
return cached.data; // 캐시 히트
}
const res = await fetch(url);
const data = await res.json();
apiCache.set(url, { data, ts: Date.now() });
return data;
}
```

왜 Map인가?

| 방법 | get | set | 삭제 |
|------|-----|-----|------|
| 배열 + 선형 탐색 | O(n) | O(n) | O(n) |
| Map | O(1) | O(1) | O(1) |
| 연결 리스트 + 해시맵 | O(1) | O(1) | O(1) |
JS의 `Map`은 삽입 순서를 보장하므로, 연결 리스트를 직접 구현할 필요 없이 삭제 후 재삽입만으로 O(1) LRU를 구현할 수 있습니다.

한 줄 요약

> `Map`의 삽입 순서를 활용하면, 삭제 후 재삽입으로 "최근 사용" 순서를 O(1)에 유지할 수 있다.

참고

[MDN — Map](https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Map)

[Wikipedia — Cache replacement policies (LRU)](https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU))