LRU 캐시 (LRU Cache)

LRU 캐시 (LRU Cache)

가장 오래 사용되지 않은 항목을 제거하는(Least Recently Used) 캐시 교체 정책을 구현한 자료구조로, 해시맵과 이중 연결 리스트를 조합하여 O(1) 접근·갱신을 제공

목적: 캐시 관리, LRU 교체 정책, 빠른 접근·갱신, 메모리 제한

특징: LRU 정책, O(1) 연산, 해시+이중연결, 용량 제한

구성요소: ① 해시맵(key → 노드): O(1) 접근 ② 이중 연결 리스트(MRU(Most Recently Used)↔...↔LRU(Least Recently Used)): 사용 순서 관리 ③ 용량(capacity): 최대 저장 항목 수

구조: 리스트 head(MRU, Most Recently Used) ↔ ... ↔ tail(LRU) + 해시맵으로 O(1) 접근

연산

• •get(key): ① 해시맵에서 노드 찾기 → ② 노드를 head로 이동 → ③ 값 반환, O(1)
• •put(key, value): ① 키 존재 시 갱신+head 이동, ② 없으면 head 삽입 → ③ 용량 초과 시 tail 제거, O(1)

LRU 갱신: 노드 접근 시 리스트에서 제거 → head에 삽입 (MRU로)

시간 복잡도: get·put 모두 O(1)

공간 복잡도: O(capacity)

장점: O(1) 접근·갱신, 실용적 캐시 정책, 시간 지역성 활용

단점: 구현 복잡도(해시+이중연결), 추가 메모리(포인터), 빈도 고려 안함

적용사례: 브라우저 캐시, CPU 캐시, 데이터베이스 버퍼 풀, 웹 서버 캐시, Redis, Memcached

비교: LRU(시간지역성) vs LFU(빈도) vs FIFO(단순) vs Random(간단)

연관: 이중 연결 리스트, 해시맵, 캐시 교체 정책, 시간 지역성