LRU Cache: vì sao eviction O(1) đòi hỏi hai cấu trúc dữ liệu cùng lúc

Constraint làm cho bài toán này thú vị không phải là capacity. Đó là dòng cuối cùng: get và put phải chạy trong O(1) trung bình. Yêu cầu duy nhất đó loại bỏ mọi giải pháp đơn giản và buộc bạn phải dùng một cặp cấu trúc dữ liệu phối hợp với nhau.

Hầu hết các bài cache đều giải được bằng một map. Map xử lý fast lookup trong O(1). Điều map không thể làm là cho bạn biết, trong O(1), key nào được đụng đến ít gần đây nhất. Thông tin thứ tự không phải thứ hash map duy trì. Vì vậy bạn cần một cấu trúc thứ hai duy trì thứ tự — cấu trúc mà việc di chuyển một phần tử lên "most recently used" là O(1), và đọc từ đầu "least recently used" cũng là O(1). Một doubly linked list với direct node reference thỏa mãn cả hai. Hash map lưu key -> node pointer, và linked list lưu thứ tự recency. Kết hợp lại, chúng cho bạn tất cả.

Insight đó là toàn bộ bài toán. Phần còn lại là pointer manipulation cẩn thận.

Đề bài

Thiết kế một cấu trúc dữ liệu triển khai LRU Cache (Least Recently Used): thao tác get(key) trả về giá trị được cache hoặc -1 nếu không tìm thấy, và thao tác put(key, value) chèn hoặc cập nhật một entry rồi evict key ít được dùng gần đây nhất khi cache vượt quá capacity — cả hai thao tác đều yêu cầu chạy trong O(1) trung bình. Đề gốc: LeetCode 146.

Ràng buộc:
- 1 <= capacity <= 3000
- 0 <= key <= 10^4
- 0 <= value <= 10^5
- Tối đa 2 * 10^5 lần gọi get và put.

Constraints thực sự buộc gì

1 <= capacity <= 3000. Đủ nhỏ để approach O(n) hoạt động trong các test nếu bạn không cẩn thận — nhưng bài toán yêu cầu rõ ràng O(1), nên kích thước capacity không phải lối thoát.

0 <= key <= 10^4, 0 <= value <= 10^5. Tất cả đều là số nguyên không âm. Không có sentinel âm nào ẩn trong dải giá trị, và 0 là giá trị hợp lệ. Một get trả về -1 thực sự có nghĩa là key vắng mặt — đừng nhầm với giá trị được lưu, vì value bị giới hạn ở 10^5.

Tối đa 2 * 10^5 lần gọi get và put. Đây mới là áp lực thực sự. Với O(n) mỗi thao tác và capacity lên đến 3000, bạn đang nhìn vào 6 * 10^8 đơn vị công việc trong trường hợp xấu nhất. Quá chậm. Yêu cầu O(1) không phải nguyện vọng — nó là điều kiện cần.

Approach 1: Array với linear search

Đọc spec một cách đơn giản nhất: giữ một danh sách các tuple (key, value, timestamp). Mỗi lần truy cập tăng global timestamp và đóng dấu mục được truy cập. Khi cần evict, quét danh sách để tìm timestamp nhỏ nhất.

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = []  # list of [key, value, timestamp]
        self.timestamp = 0
 
    def get(self, key: int) -> int:
        for i in range(len(self.cache)):
            if self.cache[i][0] == key:
                self.timestamp += 1
                self.cache[i][2] = self.timestamp
                return self.cache[i][1]
        return -1
 
    def put(self, key: int, value: int) -> None:
        self.timestamp += 1
        for i in range(len(self.cache)):
            if self.cache[i][0] == key:
                self.cache[i][1] = value
                self.cache[i][2] = self.timestamp
                return
        if len(self.cache) < self.capacity:
            self.cache.append([key, value, self.timestamp])
        else:
            lru_idx = min(range(len(self.cache)), key=lambda i: self.cache[i][2])
            self.cache[lru_idx] = [key, value, self.timestamp]

public class LRUCache {
    private int capacity;
    private List<(int key, int value, long ts)> cache;
    private long timestamp;
 
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new List<(int, int, long)>();
        this.timestamp = 0;
    }
 
    public int Get(int key) {
        for (int i = 0; i < cache.Count; i++) {
            if (cache[i].key == key) {
                timestamp++;
                cache[i] = (key, cache[i].value, timestamp);
                return cache[i].value;
            }
        }
        return -1;
    }
 
    public void Put(int key, int value) {
        timestamp++;
        for (int i = 0; i < cache.Count; i++) {
            if (cache[i].key == key) {
                cache[i] = (key, value, timestamp);
                return;
            }
        }
        if (cache.Count < capacity) {
            cache.Add((key, value, timestamp));
        } else {
            int lruIdx = 0;
            long minTs = cache[0].ts;
            for (int i = 1; i < cache.Count; i++) {
                if (cache[i].ts < minTs) { minTs = cache[i].ts; lruIdx = i; }
            }
            cache[lruIdx] = (key, value, timestamp);
        }
    }
}

Độ phức tạp: Cả get lẫn put đều là O(capacity) — bạn quét toàn bộ list mỗi lần gọi. Space là O(capacity) cho chính list đó.

Cách này đúng về logic. Nó thất bại về hiệu năng. Với capacity 3000 và 2 * 10^5 lần gọi, bạn có thể chạm 6 * 10^8 so sánh — vượt xa bất kỳ time limit hợp lý nào. Cấu trúc này còn có một vấn đề tinh tế hơn: mỗi thao tác quét mọi slot ngay cả khi cache mới đầy một nửa. Approach timestamp thanh lịch nhưng scan là không thể tránh.

Approach 2: Hash map + doubly linked list

Insight cốt lõi: để đạt O(1) trên cả access lẫn eviction, bạn cần đồng thời hai thứ — (1) tìm bất kỳ node nào trong O(1) theo key, và (2) xóa node ít được dùng gần nhất trong O(1). Hash map cho bạn (1). Doubly linked list với sentinel head và tail cho bạn (2). Không cấu trúc nào một mình giải quyết được cả hai.

List duy trì thứ tự recency. Node được dùng gần nhất nhất ngồi ngay sau head sentinel. Node ít được dùng nhất ngồi ngay trước tail sentinel. Mỗi lần truy cập — đọc hay ghi — di chuyển node được đụng đến lên đầu. Eviction luôn xóa node ngay trước tail.

Trick sentinel là thứ làm cho điều này gọn gàng. Không có sentinel node, mọi thao tác phải kiểm tra xem node bị xóa có ở đầu hay cuối không. Với sentinel, head và tail luôn là các node hợp lệ trỏ vào list, và "thêm vào đầu" cùng "xóa từ cuối" là cùng bốn thao tác pointer mỗi lần.

class Node:
    def __init__(self, key: int = 0, value: int = 0):
        self.key = key
        self.value = value
        self.prev: "Node | None" = None
        self.next: "Node | None" = None
 
 
class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache: dict[int, Node] = {}
 
        # Sentinel node — không bao giờ lưu dữ liệu thực
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
 
    def _remove(self, node: Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev
 
    def _add_to_front(self, node: Node) -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
 
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._add_to_front(node)
        return node.value
 
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self._remove(node)
            self._add_to_front(node)
        else:
            node = Node(key, value)
            self.cache[key] = node
            self._add_to_front(node)
            if len(self.cache) > self.capacity:
                # Evict node ngay trước tail sentinel
                lru = self.tail.prev
                self._remove(lru)
                del self.cache[lru.key]

public class Node {
    public int Key, Value;
    public Node Prev, Next;
    public Node(int key = 0, int value = 0) { Key = key; Value = value; }
}
 
public class LRUCache {
    private int capacity;
    private Dictionary<int, Node> cache;
    private Node head, tail;
 
    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new Dictionary<int, Node>();
        head = new Node();
        tail = new Node();
        head.Next = tail;
        tail.Prev = head;
    }
 
    private void Remove(Node node) {
        node.Prev.Next = node.Next;
        node.Next.Prev = node.Prev;
    }
 
    private void AddToFront(Node node) {
        node.Prev = head;
        node.Next = head.Next;
        head.Next.Prev = node;
        head.Next = node;
    }
 
    public int Get(int key) {
        if (!cache.ContainsKey(key)) return -1;
        Node node = cache[key];
        Remove(node);
        AddToFront(node);
        return node.Value;
    }
 
    public void Put(int key, int value) {
        if (cache.ContainsKey(key)) {
            Node node = cache[key];
            node.Value = value;
            Remove(node);
            AddToFront(node);
        } else {
            Node node = new Node(key, value);
            cache[key] = node;
            AddToFront(node);
            if (cache.Count > capacity) {
                Node lru = tail.Prev;
                Remove(lru);
                cache.Remove(lru.Key);
            }
        }
    }
}

Độ phức tạp: Cả get lẫn put đều là O(1). Mọi thao tác hash map là O(1) trung bình. Mỗi thao tác linked list (_remove, _add_to_front) đụng đúng bốn pointer — độc lập với kích thước list. Eviction đọc tail.prev trong O(1) và xóa nó trong O(1). Space là O(capacity) cho map cộng O(capacity) cho các node trong list.

Trace từng bước: capacity = 2

Đây là ví dụ của chính bài toán. Tôi muốn làm trạng thái list hiện ra rõ ràng ở mỗi thao tác.

Trạng thái ban đầu:
  cache = {}
  HEAD <-> TAIL

put(1, 1):
  Node mới. Thêm vào đầu.
  HEAD <-> [1:1] <-> TAIL
  cache = {1: node[1:1]}

put(2, 2):
  Node mới. Thêm vào đầu.
  HEAD <-> [2:2] <-> [1:1] <-> TAIL
  cache = {1: node[1:1], 2: node[2:2]}

get(1):
  Hit. Xóa [1:1], thêm lại vào đầu.
  HEAD <-> [1:1] <-> [2:2] <-> TAIL
  return 1

put(3, 3):
  Node mới. len(cache) sẽ thành 3 > capacity=2.
  Evict tail.prev = [2:2]. Xóa khỏi list và map.
  Thêm [3:3] vào đầu.
  HEAD <-> [3:3] <-> [1:1] <-> TAIL
  cache = {1: node[1:1], 3: node[3:3]}

get(2):
  Miss (đã bị evict). return -1

put(4, 4):
  Node mới. len(cache) sẽ thành 3 > capacity=2.
  Evict tail.prev = [1:1]. Xóa khỏi list và map.
  Thêm [4:4] vào đầu.
  HEAD <-> [4:4] <-> [3:3] <-> TAIL
  cache = {3: node[3:3], 4: node[4:4]}

get(1): Miss. return -1
get(3): Hit. Di chuyển [3:3] lên đầu. return 3
get(4): Hit. Di chuyển [4:4] lên đầu. return 4

Trace khớp với output mong đợi [null, null, null, 1, null, -1, null, -1, 3, 4] chính xác.

Một chi tiết đáng chú ý: eviction sau put(3, 3) xóa key 2, không phải key 1. Sau khi get(1) di chuyển node 1 lên đầu, node 2 trượt xuống vị trí kề tail. Thứ tự list là ground truth cho recency — và get cập nhật nó, đó là lý do tại sao get phải gọi _remove + _add_to_front ngay cả khi chỉ đọc.

Các edge case cần suy nghĩ kỹ

capacity = 1. Mỗi put một key mới đều evict key hiện tại. get trên key tồn tại vẫn ổn; nó đặt lại node về đầu (vốn là vị trí nó đang ở, với sentinel hấp thụ công việc pointer). Design sentinel làm điều này không khác gì các trường hợp khác — không cần xử lý đặc biệt.

put trên key đã tồn tại. Phải cập nhật value và làm mới recency, nhưng không tăng kích thước cache. Nếu bạn quên di chuyển node lên đầu khi update, vị trí recency của node bị sai — một eviction sau đó có thể xóa key vừa được "ghi." Trong code trên, cả hai nhánh của put đều gọi _remove và _add_to_front, nên điều này không thể vô tình bị bỏ qua.

get trên key vừa bị evict. Trả về -1 và không đụng đến cache. Hash map lookup thất bại ngay — không có list access nào xảy ra. Đúng và nhanh.

Tất cả lời gọi đều là get trên key không tồn tại. Cache vẫn trống. _remove và _add_to_front không bao giờ được gọi. Không có vấn đề gì.

Thứ tự pointer trong _add_to_front. Đây là chỗ logic pointer sai thứ tự sẽ phá vỡ mọi thứ. Node được chèn phải cập nhật head.next.prev trước khi head.next được gán lại — nếu không head.next đã trỏ vào node mới và bạn mất reference đến node thực đầu tiên cũ. Thứ tự trong code là: đặt node.prev = head, đặt node.next = head.next, rồi head.next.prev = node, rồi head.next = node. Tuân thủ thứ tự này chính xác.

Bảng so sánh

Pattern có thể chuyển giao: khi một cấu trúc dữ liệu không đủ

Design pattern ở đây đáng được đặt tên rõ ràng. Đôi khi bạn gặp yêu cầu hiệu năng mà một cấu trúc dữ liệu đáp ứng được theo một chiều nhưng không theo chiều khác. Ở đây: fast lookup (hash map) cộng fast ordered removal (doubly linked list). Liên kết giữa hai cấu trúc thông qua node pointer — hash map không lưu value, nó lưu pointer đến node trong list lưu value. List có thể được tái cấu trúc trong O(1) vì bạn có direct node reference.

Pattern "pointer coupling" này xuất hiện ở nhiều nơi khác. Bạn thấy nó trong skip list (random access gặp ordered iteration), trong adjacency list cho graph, và bất cứ khi nào thuật toán page replacement của hệ điều hành cần hoạt động trong O(1). Một khi bạn nhận ra rằng bài toán LRU phân rã thành thao tác "tìm" và "sắp xếp", và rằng cả hash map lẫn linked list một mình đều không xử lý được cả hai, thiết kế kết hợp trở nên hiển nhiên.

Điều tôi thấy đáng nhấn mạnh: sentinel node không phải micro-optimisation. Chúng là simplification về tính đúng đắn. Không có chúng, _remove cần kiểm tra node có phải head hay tail không, và _add_to_front cần kiểm tra list có trống không. Với sentinel, những kiểm tra đó biến mất. List không bao giờ thực sự trống (head và tail luôn ở đó), và mọi remove và insert đều thao tác trên interior node theo thiết kế. Giữ lại sentinel.

Cái tôi sẽ ship, và lý do

Với bất kỳ context interview hay production thực tế nào, tôi viết thẳng solution hash map + doubly linked list. Phiên bản array O(n) hữu ích như giải thích miệng về bài toán đang hỏi gì — nhưng tôi sẽ không tốn thời gian code nó trừ khi interviewer đặc biệt yêu cầu thấy naive approach trước.

Trong production C#, tôi dùng LinkedList<T> và Dictionary<K, LinkedListNode<V>> thay vì tự xây dựng node class. Standard library LinkedList expose AddFirst, Remove, và Last — tất cả O(1) — map trực tiếp lên các thao tác ở đây. Trong Python, collections.OrderedDict (duy trì insertion order và hỗ trợ move_to_end) cho bạn LRU trong khoảng tám dòng, dù để hiểu tại sao nó hoạt động cần biết nó được xây dựng trên cùng internals hash map + doubly linked list.

Vị trí trong series linked-list

Series này đã xây dựng từ thao tác single-linked (Reverse Linked List, Merge Two Sorted Lists) qua các bài multi-pointer (Reorder List, Remove Nth Node) đến cycle detection (Linked List Cycle). LRU Cache là bài design đầu tiên trong series. Sự chuyển dịch là từ "thao tác trên list được cho" sang "thiết kế một cấu trúc sử dụng list bên trong." Kiến thức linked-list là như nhau; framing bị đảo ngược.

LFU Cache (460) là bước tiếp theo tự nhiên. Least Frequently Used theo dõi số lần truy cập thay vì recency. Bạn cần một map từ frequency -> doubly linked list, cộng một map từ key -> (value, frequency). Các thao tác cấu trúc giống LRU; nhưng eviction chọn từ bucket frequency nhỏ nhất thay vì từ tail.

All O(one) Data Structure (432) tổng quát hóa ý tưởng thêm: increment và decrement count cho string key, trả về key có count nhỏ nhất hoặc lớn nhất, tất cả trong O(1). Solution dùng doubly linked list các frequency bucket — cùng cặp đôi "linked list lưu thứ tự, hash map lưu vị trí", phức tạp hơn.

Insert Delete GetRandom O(1) (380) thêm random uniform sampling vào một set với O(1) insert và delete. Trick là một array cho random access cộng một hash map cho O(1) lookup/delete. Cùng design idiom: hai cấu trúc bù đắp điểm yếu cho nhau, liên kết qua index thay vì pointer.

Design Twitter (355) đẩy sâu hơn vào design territory: một newsfeed trả về 10 tweet gần nhất từ những người mà user đang follow. Linked list trở thành heap-merge trên per-user tweet list. Đây là những building block giống nhau được dùng khác đi — kỹ năng chuyển giao ngay cả khi cấu trúc cụ thể thay đổi.