LRU 캐시 (Least Recently Used Cache)

캐시 용량은 항상 유한하다. 꽉 찼을 때 "가장 오래 안 쓴 항목"부터 내보내는 전략이 LRU다. 이걸 get·put 둘 다 O(1)에 해내려면 자료구조 하나로는 부족하다 — 해시맵과 이중 연결 리스트가 서로의 약점을 메워주는 합작품이 필요하다.

1. 문제 상황 — 캐시는 무한하지 않다

웹 서버가 DB 조회 결과를 메모리에 캐싱한다고 하자. 캐시 용량이 3개뿐인데 계속 새 키가 들어온다면? 가장 최근에 쓴 것들만 남기고, 가장 오래 안 쓴 것부터 버리는 게 합리적이다 — 최근 쓴 데이터가 곧 다시 쓰일 확률이 높다는 경험칙(시간 지역성, temporal locality) 때문이다. 조건은 두 가지: get(key)로 값을 꺼내면서 "방금 썼다"고 갱신하고, put(key, value)로 새로 넣거나 갱신하고, 용량 초과 시 가장 오래 안 쓴 항목을 자동으로 내쫓는다. 그리고 이 모든 게 데이터 개수와 무관하게 빨라야(O(1)) 실용적이다.

2. 왜 하나만으로는 안 될까

후보 자료구조를 하나씩만 써 보면 바로 벽에 부딪힌다.

3. 해결책 — 해시맵 + 이중 연결 리스트

둘을 같이 쓰면 서로의 구멍이 정확히 메워진다.

4. 직접 만져 보기 — LRU 캐시 시뮬레이터

용량을 정하고 put(key, value)·get(key)를 실행해 보자. 위쪽은 이중 연결 리스트(맨 왼쪽 = MRU, 맨 오른쪽 = LRU), 아래쪽은 해시맵이다. 점선 화살표가 "이 키는 지금 이 노드를 가리킨다"를 보여준다.

5. 코드로 보기

파이썬에서는 collections.OrderedDict가 "삽입 순서를 기억하는 딕셔너리"라 move_to_end와 popitem(last=False)만으로 LRU를 몇 줄에 구현할 수 있다.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()      # 삽입/접근 순서를 기억하는 dict

    def get(self, key) -> int:
        if key not in self.cache:
            return -1                    # 미스
        self.cache.move_to_end(key)     # 방금 썼으니 맨 뒤(=MRU)로
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key) # 기존 키도 접근 취급
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # 맨 앞 = LRU 축출

6. 관련 페이지