LRU 캐시 구현

이 장에서는 해시 맵과 이중 연결 리스트를 묶은 설계를 Python으로 만들고 각 부분을 설명한 다음, 같은 루틴을 C++, Java, TypeScript로 옮깁니다. 모든 버전이 get과 put을 평균 O(1)에 처리합니다.

Python: 딕셔너리와 이중 연결 리스트

class Node:
    __slots__ = ("key", "value", "prev", "next")
    def __init__(self, key=None, value=None):
        self.key, self.value = key, value
        self.prev = self.next = None


class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}                       # 키 -> Node
        self.head, self.tail = Node(), Node()  # 보초 노드
        self.head.next, self.tail.prev = self.tail, self.head

    def _unlink(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _push_front(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key, default=None):
        node = self.map.get(key)
        if node is None:
            return default
        self._unlink(node)
        self._push_front(node)
        return node.value

    def put(self, key, value):
        if self.capacity <= 0:
            return
        node = self.map.get(key)
        if node is not None:                # 갱신: 앞으로 옮기고 제거는 하지 않음
            node.value = value
            self._unlink(node)
            self._push_front(node)
            return
        if len(self.map) >= self.capacity:  # 가득 참: 가장 오래전 항목 제거
            lru = self.tail.prev
            self._unlink(lru)
            del self.map[lru.key]
        node = Node(key, value)
        self.map[key] = node
        self._push_front(node)


cache = LRUCache(2)
cache.put("a", 1); cache.put("b", 2)
cache.get("a")
cache.put("c", 3)                           # "b" 제거
print(cache.get("b"), cache.get("a"), cache.get("c"))   # None 1 3

한 줄씩 살펴봅니다.

• __slots__는 노드마다 인스턴스 딕셔너리를 두지 않고 작은 고정 레코드로 만들어 줍니다. 항목이 수백만 개일 때 차이가 큽니다.
• 생성자는 두 보초 노드를 서로 연결합니다. 빈 캐시는 head <-> tail이므로 도우미 함수가 None을 만날 일이 없습니다.
• _unlink와 _push_front는 정해진 개수의 포인터만 바꿉니다. 노드를 옮기는 일은 두 함수를 한 번씩 부르는 것입니다.
• get은 -1 대신 default를 돌려주므로 음수를 포함한 어떤 값이든 캐시할 수 있습니다. 적중하면 노드를 앞으로 옮기는데, 바로 이 동작이 정책을 FIFO가 아닌 LRU로 만듭니다.
• put은 용량 0, 이미 있는 키, 새 키의 세 경우를 차례로 처리합니다. del self.map[lru.key] 때문에 노드가 키를 저장해야 합니다.

애플리케이션 코드에서는 collections.OrderedDict의 move_to_end와 popitem(last=False)로 같은 동작을 몇 줄 만에 얻을 수 있습니다. 앞 장의 추적 코드가 그 예입니다.

C++: std::list와 unordered_map

std::list는 이중 연결 리스트이고, splice는 노드를 복사하지 않고 반복자도 무효화하지 않은 채 맨 앞으로 옮깁니다. 맵에는 리스트 반복자를 저장합니다.

#include <list>
#include <optional>
#include <unordered_map>
#include <utility>

class LRUCache {
public:
    explicit LRUCache(std::size_t capacity) : capacity_(capacity) {}

    std::optional<int> get(int key) {
        auto it = index_.find(key);
        if (it == index_.end()) return std::nullopt;
        order_.splice(order_.begin(), order_, it->second);  // 맨 앞으로
        return it->second->second;
    }

    void put(int key, int value) {
        if (capacity_ == 0) return;
        if (auto it = index_.find(key); it != index_.end()) {
            it->second->second = value;
            order_.splice(order_.begin(), order_, it->second);
            return;
        }
        if (index_.size() == capacity_) {
            index_.erase(order_.back().first);  // 맨 뒤 = 가장 오래전
            order_.pop_back();
        }
        order_.emplace_front(key, value);
        index_[key] = order_.begin();
    }

private:
    std::size_t capacity_;
    std::list<std::pair<int, int>> order_;  // 맨 앞 = 가장 최근
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> index_;
};

Java: HashMap과 직접 만든 노드

같은 구조를 int 키와 값으로 옮겼고, get은 실패하면 -1을 돌려줍니다. 접근 순서 모드의 LinkedHashMap도 같은 일을 하며 실무 장에서 다룹니다.

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

public class LRUCache {
    private static final 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 = new Node(0, 0), tail = new Node(0, 0);

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        unlink(node);
        pushFront(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (capacity <= 0) return;
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            unlink(node);
            pushFront(node);
            return;
        }
        if (map.size() >= capacity) {
            Node lru = tail.prev;
            unlink(lru);
            map.remove(lru.key);
        }
        node = new Node(key, value);
        map.put(key, node);
        pushFront(node);
    }

    private void unlink(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }

    private void pushFront(Node n) {
        n.prev = head; n.next = head.next;
        head.next.prev = n; head.next = n;
    }
}

TypeScript: Map의 삽입 순서

JavaScript의 Map은 언어 명세에 따라 키를 삽입 순서대로 순회합니다. 이미 있는 키에 값을 다시 넣으면 원래 자리를 유지하지만, 지웠다가 다시 넣으면 맨 뒤로 갑니다. 그래서 맵의 끝이 가장 최근 항목이고 keys().next()가 가장 오래전 항목을 돌려줍니다. 엔진은 Map을 순서 있는 항목 목록을 가진 해시 테이블로 구현하므로 이 과정이 평균 O(1)이고, 연결 리스트를 따로 만들 필요가 없습니다.

class LRUCache<K, V> {
  private readonly map = new Map<K, V>();

  constructor(private readonly capacity: number) {}

  get(key: K): V | undefined {
    if (!this.map.has(key)) return undefined;
    const value = this.map.get(key) as V;
    this.map.delete(key);           // 다시 넣으면 키가 맨 뒤로 갑니다
    this.map.set(key, value);
    return value;
  }

  put(key: K, value: V): void {
    if (this.capacity <= 0) return;
    if (this.map.has(key)) this.map.delete(key);
    else if (this.map.size >= this.capacity) {
      this.map.delete(this.map.keys().next().value as K);  // 첫 키 = 가장 오래전
    }
    this.map.set(key, value);
  }
}

정리

• 모든 버전의 핵심은 같습니다. 키에서 위치로 가는 맵, 순서 있는 리스트, 사용할 때마다 앞으로 옮기기, 가장 오래전 쪽 끝에서 제거하기입니다.
• C++는 std::list::splice를, TypeScript는 Map의 삽입 순서를 쓰며, Python은 OrderedDict로도 만들 수 있습니다.
• 용량 0과 기존 키 갱신을 명시적으로 처리합니다. 버그가 가장 자주 나는 곳입니다.