🛠️ 처음부터 만드는 LRU Cache — Map의 삽입 순서를 활용한 O(1) 캐시 20줄 구현

왜 LRU Cache인가?

API 응답 캐싱, 이미지 메모리 관리, DB 쿼리 재사용 — "가장 오래 안 쓴 걸 버려라"는 전략이 어디서든 필요합니다. Redis의 `maxmemory-policy`, React Query의 `gcTime`, 브라우저 HTTP 캐시 모두 LRU 기반입니다.

핵심 트릭

JS의 `Map`은 삽입 순서를 보장합니다. LinkedList 없이 O(1) LRU가 가능한 이유:

`get()` → 삭제 후 재삽입 (맨 뒤 = 최근 사용)

`set()` → 용량 초과 시 `keys().next().value`로 맨 앞(가장 오래된) 제거

```typescript
class LRUCache {
private cache = new Map();
constructor(private capacity: number) {}
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);
else if (this.cache.size >= this.capacity) {
this.cache.delete(this.cache.keys().next().value!);
}
this.cache.set(key, value);
}
}
```

동작 확인

```typescript
const cache = new LRUCache(3);
cache.set("a", 1);
cache.set("b", 2);
cache.set("c", 3);
cache.get("a"); // 1 — "a"가 최근으로 이동
cache.set("d", 4); // 용량 초과 → "b" 퇴거 (가장 오래 안 쓴 것)
cache.get("b"); // undefined
```

확장 아이디어

TTL: `Map`로 만료 시간 지원

onEvict 콜백: 퇴거 시 정리 로직 (커넥션 반납 등)

히트율 추적: hit/miss 카운터로 캐시 효율 모니터링

면접 단골 질문이기도 하죠. "LinkedList + HashMap"이 교과서 답이지만, JS에선 Map 하나로 끝납니다. `lru-cache` npm 패키지(주간 다운로드 2억+)의 핵심이 바로 이 패턴입니다.