자바 LinkedHashMap으로 LRU 캐시 구현하기

코딩테스트나 실무에서 LRU 캐시를 만들 일이 종종 생긴다. 면접 단골 문제이기도 하고, 실제로 조회가 잦은 데이터를 메모리에 잠깐 얹어둘 때도 쓴다. 그때마다 이중 연결 리스트를 처음부터 짜야 하나 고민하게 되는데, 자바에서는 LinkedHashMap 하나로 몇 줄이면 끝난다. 제가 직접 해보면 수동 구현은 로직 검증용이고, 실전 코드는 거의 LinkedHashMap으로 수렴한다.

결론부터 말하자면, 단일 스레드에서 LRU가 필요하면 LinkedHashMap(capacity, 0.75f, true)를 상속해 removeEldestEntry만 재정의하면 O(1) LRU 캐시가 완성된다. 원리를 이해하거나 면접에서 자료구조를 설명해야 하면 HashMap과 이중 연결 리스트로 수동 구현하면 된다. 멀티 스레드 환경이면 두 방식 모두 그대로는 안전하지 않으므로 별도 동기화가 필요하다.

1. LRU 캐시와 LinkedHashMap

LRU(Least Recently Used)는 캐시가 가득 찼을 때 가장 오래 안 쓴 항목부터 버리는 교체 정책이다. 용량 3짜리 캐시에 A, B, C를 넣고 A를 다시 조회한 뒤 D를 넣으면, 가장 오래 안 쓴 B가 빠진다.

LinkedHashMap은 HashMap에 이중 연결 리스트를 얹어 항목의 순서를 기억하는 맵이다. 기본은 삽입 순서를 유지한다. 생성자의 세 번째 인자인 accessOrder를 true로 주면 접근 순서로 바뀐다. 즉 가장 최근에 접근한 항목이 리스트 끝으로, 오래된 항목이 앞으로 정렬된다. 공식 문서도 "이 방식의 맵은 LRU 캐시를 만들기에 알맞다"고 명시한다.

여기에 removeEldestEntry(Map.Entry eldest) 메서드가 붙는다. 이 메서드는 put과 putAll로 새 항목을 넣은 직후 호출되고, true를 반환하면 가장 오래된 항목(eldest)을 자동으로 제거한다. 기본 구현은 항상 false를 반환해 아무것도 지우지 않는다. 이 두 가지를 조합하면 LRU 캐시가 된다.

2. LinkedHashMap으로 O(1) LRU 캐시 구현

LinkedHashMap을 상속하고 removeEldestEntry만 재정의한다. 접근 순서 정렬을 켜야 하므로 생성자에서 accessOrder를 true로 넘긴다.

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        // initialCapacity, loadFactor, accessOrder=true
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

동작을 확인하는 코드다.

public class Main {
    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);
        cache.put(1, "A");
        cache.put(2, "B");
        cache.put(3, "C");
        cache.get(1);          // 1을 최근 사용으로 갱신
        cache.put(4, "D");     // 가장 오래된 2가 제거됨
        System.out.println(cache);
        System.out.println(cache.containsKey(2));
    }
}

{3=C, 1=A, 4=D}
false

출력 순서를 보면 접근 순서대로 정렬돼 있다. get(1) 덕분에 1이 살아남고, 손대지 않은 2가 밀려났다. get과 put은 해시 조회와 리스트 포인터 조정만 하므로 평균 O(1)이다.

처음 이걸 짤 때 accessOrder를 빼먹고 기본 생성자로 만들었다가 한 번 걸렸다. 그러면 삽입 순서만 유지돼서 get(1)을 아무리 호출해도 1이 오래된 항목으로 남고, 결국 LRU가 아니라 FIFO 캐시가 된다. 생성자에서 세 번째 인자를 true로 주는 것이 이 구현의 핵심이다.

3. HashMap과 이중 연결 리스트 수동 구현

면접에서 "LinkedHashMap 없이 짜보라"는 요구를 받으면 HashMap과 이중 연결 리스트를 직접 엮어야 한다. HashMap은 키로 노드를 O(1)에 찾고, 이중 연결 리스트는 사용 순서를 관리하며 양 끝 삽입과 삭제를 O(1)에 처리한다.

import java.util.HashMap;
import java.util.Map;

public class ManualLRUCache {
    private static class Node {
        int key, value;
        Node prev, next;
        Node(int key, int value) { this.key = key; this.value = value; }
    }

    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head, tail; // 더미 노드

    public ManualLRUCache(int capacity) {
        this.capacity = capacity;
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addFirst(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        remove(node);
        addFirst(node);   // 최근 사용으로 이동
        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            remove(node);
            addFirst(node);
            return;
        }
        if (map.size() >= capacity) {
            Node eldest = tail.prev;   // 가장 오래된 노드
            remove(eldest);
            map.remove(eldest.key);
        }
        Node fresh = new Node(key, value);
        addFirst(fresh);
        map.put(key, fresh);
    }
}

머리(head) 쪽이 최근 사용, 꼬리(tail) 쪽이 오래된 항목이다. 더미 노드 두 개를 양 끝에 두면 null 검사 없이 삽입과 삭제 코드를 단순하게 유지할 수 있다. 이 더미 노드 처리를 빼먹으면 첫 삽입이나 마지막 삭제에서 NullPointerException이 자주 난다.

4. 두 방식 중 무엇을 쓰나

실전 코드나 시간 제한이 빠듯한 코딩테스트에서는 LinkedHashMap 방식을 쓴다. 코드가 10줄 남짓이라 실수할 여지가 적고, 검증된 표준 라이브러리라 경계 조건 버그가 없다.

수동 구현은 자료구조 이해를 보여줘야 하거나, 노드에 추가 필드를 넣는 등 캐시 내부를 세밀하게 제어해야 할 때 쓴다. 다만 포인터 조정 실수가 나기 쉬우므로 remove와 addFirst를 별도 메서드로 분리해 검증하는 편이 낫다.

5. 스레드 안전성 함정

두 구현 모두 단일 스레드 기준이다. LinkedHashMap과 HashMap은 동기화되지 않는다. 여러 스레드가 동시에 접근하고 그중 하나라도 구조를 바꾸면 외부에서 동기화해야 한다.

특히 accessOrder=true인 경우 함정이 하나 있다. 공식 문서 표현으로 "접근 순서 LinkedHashMap에서는 단순히 get으로 조회하는 것도 구조적 변경"이다. 조회만 해도 리스트 순서가 바뀌기 때문이다. 그래서 읽기 전용처럼 보이는 get조차 동기화 대상이 된다.

간단한 대응은 Collections.synchronizedMap으로 감싸는 것이다.

Map<Integer, String> cache = Collections.synchronizedMap(
        new LRUCache<>(3));

다만 이렇게 감싸도 컬렉션 뷰를 순회할 때는 별도로 맵 객체에 직접 동기화해야 한다. keySet이나 entrySet을 Iterator, Stream으로 돌 때 이 규칙을 어기면 비결정적 동작이 생긴다.

synchronized (cache) {            // 뷰(s)가 아니라 맵(cache)에 동기화
    for (Integer key : cache.keySet()) {
        System.out.println(key);
    }
}

동시성 요구가 높으면 synchronizedMap은 맵 전체를 한 락으로 묶어 병목이 된다. 이때는 ConcurrentHashMap 기반의 캐시나 Caffeine 같은 검증된 캐시 라이브러리를 쓴다. ConcurrentHashMap 자체에는 LRU 교체 기능이 없으므로, 순수하게 LRU가 필요하면서 동시성도 필요하면 직접 조합하기보다 캐시 라이브러리를 도입하는 것이 안전하다.

6. 코딩테스트에서 자주 걸리는 지점

첫째, accessOrder를 빼먹는 실수다. 3절에서 짚었듯 이 값이 false면 LRU가 아니라 FIFO가 된다. 문제에서 요구하는 게 LRU인지 FIFO인지 먼저 확인한다.

둘째, removeEldestEntry의 부등호다. size() > capacity여야 한다. >=로 쓰면 용량에 도달하자마자 항목을 지워 실제 저장 개수가 capacity - 1이 된다.

셋째, 값 갱신 시 순서 재정렬 여부다. LinkedHashMap은 put도 접근으로 취급해 기존 키를 다시 넣으면 최근 사용으로 이동한다. 수동 구현에서는 put에서 기존 노드를 remove 후 addFirst하는 처리를 잊으면 순서가 어긋난다.

넷째, 조회 실패 반환값이다. LeetCode 146번 같은 문제는 없는 키 조회 시 -1을 요구한다. LinkedHashMap의 get은 없는 키에 null을 반환하므로, 문제 규격에 맞게 getOrDefault(key, -1) 또는 별도 래퍼로 변환한다.