Phỏng vấn

Thiết kế bộ nhớ đệm LRU Cache trong O(1) với Bảng băm và Danh sách liên kết đôi

Trong các vòng phỏng vấn thiết kế cấu trúc dữ liệu tại các tập đoàn công nghệ lớn, bài toán thiết kế bộ nhớ đệm ít được dùng gần đây nhất (LRU Cache - Least Recently Used Cache) xuất hiện thường xuyên vì nó kiểm tra khả năng kết hợp hai cấu trúc dữ liệu cơ bản để vượt qua giới hạn của từng cấu trúc đơn lẻ. Bảng băm cho phép tra cứu khóa trong thời gian hằng số nhưng không biết phần tử nào vừa mới được truy cập; ngược lại, danh sách liên kết duy trì được thứ tự thời gian nhưng mất chi phí tuyến tính để tìm kiếm. Bài viết này phân tích trọn vẹn cơ chế ghép nối bảng băm với danh sách liên kết đôi có hai nút đầu cuối giả (sentinel nodes) để thực hiện cả hai thao tác `get` và `put` trong thời gian $O(1)$ chặt chẽ.

Ý chính
  • Yêu cầu cốt lõi của LRU Cache: Với sức chứa tối đa \(C\) phần tử, cả hai thao tác đọc giá trị get(key) và ghi/cập nhật giá trị put(key, value) đều phải chạy trong thời gian \(O(1)\) trường hợp trung bình. Khi bộ nhớ đầy và cần chèn khóa mới, phần tử lâu nhất chưa được chạm tới (Least Recently Used) phải bị trục xuất ngay lập tức.
  • Tổ hợp cấu trúc dữ liệu: Sử dụng một danh sách liên kết đôi (Doubly Linked List) để xếp các phần tử theo thứ tự thời gian truy cập giảm dần từ đầu (head) về cuối (tail), kết hợp với một bảng băm (Hash Map) ánh xạ trực tiếp từ key sang địa chỉ con trỏ của nút tương ứng trên danh sách liên kết đôi.
  • Kỹ thuật hai nút lính canh (Sentinel Nodes): Khởi tạo sẵn hai nút giả head và tail nối với nhau ngay từ đầu giúp loại bỏ toàn bộ các nhánh điều kiện kiểm tra con trỏ null khi tháo nút hoặc chèn nút vào danh sách rỗng hay danh sách chỉ có một phần tử.
  • Lưu lại key ngay trong nút của danh sách: Mỗi nút trên danh sách liên kết đôi bắt buộc phải lưu cả cặp (key, value). Khi bộ nhớ đầy và ta cắt nút nằm sát trước tail, ta cần biết key của nút đó để xóa mục tương ứng khỏi bảng băm trong thời gian \(O(1)\).

Bài toán thiết kế bộ nhớ đệm LRU và rào cản độ phức tạp O(1)

Bộ nhớ đệm (cache) là vùng lưu trữ tốc độ cao có dung lượng giới hạn \(C\) (\(C \ge 1\)). Khi ứng dụng cần đọc dữ liệu theo khóa key, nó kiểm tra trong bộ nhớ đệm trước:

  1. Thao tác get(key): Nếu key đang tồn tại trong bộ nhớ đệm (trúng bộ nhớ đệm), trả về giá trị tương ứng và đánh dấu khóa này là vừa mới được sử dụng gần đây nhất. Nếu key không tồn tại (trượt bộ nhớ đệm), trả về \(-1\).
  2. Thao tác put(key, value): Nếu key đã có mặt, cập nhật giá trị mới và đánh dấu khóa này là vừa mới được sử dụng gần đây nhất. Nếu key chưa có mặt, chèn cặp (key, value) mới vào vị trí mới sử dụng nhất; trong trường hợp số lượng phần tử vượt quá sức chứa \(C\), hệ thống phải xóa bỏ phần tử ít được sử dụng gần đây nhất (tức phần tử nằm ở đáy lịch sử truy cập) trước hoặc ngay khi chèn.

Ràng buộc quan trọng nhất trong phỏng vấn là cả get lẫn put đều phải chạy trong thời gian hằng số \(O(1)\). Nếu ta chỉ dùng một mảng động hoặc danh sách đơn để lưu thứ tự truy cập, việc tìm kiếm một khóa bất kỳ hoặc dồn dịch các phần tử khi đưa một khóa lên đầu sẽ tốn \(O(C)\). Ngược lại, nếu chỉ dùng một bảng băm thông thường kèm nhãn thời gian (timestamp) cho mỗi khóa, thao tác tìm khóa có nhãn thời gian nhỏ nhất để trục xuất khi đầy bộ nhớ vẫn mất \(O(C)\), hoặc mất \(O(\log C)\) nếu duy trì thêm một hàng đợi ưu tiên (heap) hay cây cân bằng.

Để phá vỡ nút thắt này, ta cần một cấu trúc vừa cho phép nhảy trực tiếp tới bất kỳ phần tử nào theo khóa trong \(O(1)\), vừa cho phép bứt phần tử đó ra khỏi vị trí hiện tại và gắn lên đầu hàng đợi thời gian trong \(O(1)\).

Minh họa LRU Cache (Sức chứa C = 2): Hash Map + Danh sách liên kết đôi Chuỗi thao tác: put(1, 10) -> put(2, 20) -> get(1) = 10 -> put(3, 30) trục xuất khóa 2 Bảng băm pos (O(1) tra cứu) key = 3 -> Node(3, 30) key = 1 -> Node(1, 10) key = 2 (đã xóa) Danh sách liên kết đôi (Trái: mới dùng nhất MRU — Phải: lâu nhất LRU) HEAD <-> key: 3 val: 30 (MRU) <-> key: 1 val: 10 (LRU) <-> TAIL Vì sao khóa 2 bị trục xuất khi gọi put(3, 30)? 1. Lệnh get(1) trước đó đã gỡ Node(1, 10) và đưa lên sát sau HEAD. 2. Node(2, 20) trôi về sát trước TAIL (LRU) nên bị cắt bỏ trong O(1).
LRU Cache (Sức chứa C = 2) Sau put(1,10), put(2,20), get(1), put(3,30) 1. Bảng băm pos (tra cứu O(1)) key = 3 -> Node(3, 30) [mới nhất] key = 1 -> Node(1, 10) [giữ lại] key = 2 đã bị xóa khi đầy bộ nhớ đệm 2. Thứ tự trên danh sách liên kết đôi HEAD (3, 30) MRU (1, 10) LRU TAIL • get(1) đưa nút (1,10) lên đầu danh sách. • put(3,30) xóa nút sát TAIL là (2,20) trong O(1).
Hình 1: Kiến trúc ghép nối bảng băm pos với danh sách liên kết đôi có hai nút giả HEAD và TAIL trên bộ nhớ đệm sức chứa \(C = 2\). Sau chuỗi lệnh put(1, 10), put(2, 20), get(1) và put(3, 30), nút (1, 10) được giữ lại nhờ vừa được đọc bởi get(1), còn nút (2, 20) trôi về sát trước TAIL nên bị trục xuất.

Sự kết hợp giữa Bảng băm và Danh sách liên kết đôi

Trong danh sách liên kết đôi, mỗi nút Node nắm giữ hai con trỏ prev (trỏ về nút đứng liền trước) và next (trỏ về nút đứng liền sau). Đặc tính quý giá nhất của danh sách liên kết đôi là: nếu ta đã cầm sẵn con trỏ trỏ trực tiếp tới một nút u, ta có thể tháo u ra khỏi chuỗi chỉ bằng hai phép gán con trỏ trong thời gian \(O(1)\) mà không cần duyệt từ đầu danh sách để tìm nút đứng trước nó:

\[\text{u.prev.next} = \text{u.next}, \qquad \text{u.next.prev} = \text{u.prev}\]

Tương tự, việc chèn nút u vào ngay phía sau nút giả head (vị trí đại diện cho phần tử mới được sử dụng gần đây nhất — Most Recently Used, viết tắt là MRU) cũng chỉ tốn bốn phép nối con trỏ trong thời gian \(O(1)\).

Phần còn thiếu duy nhất của danh sách liên kết đôi là làm sao lấy được con trỏ u từ một mã khóa key bất kỳ mà không phải duyệt tuần tự. Đó chính là vai trò của bảng băm pos: bảng băm lưu ánh xạ key -> Node*. Khi kết hợp hai cấu trúc này:

  • Vị trí ngay sau head (head.next): luôn là phần tử vừa mới được chạm tới gần đây nhất (MRU).
  • Vị trí ngay trước tail (tail.prev): luôn là phần tử lâu nhất chưa được chạm tới (LRU) — ứng viên đầu tiên bị trục xuất khi bộ nhớ vượt quá sức chứa \(C\).
  • Mọi thao tác chạm vào khóa hiện có (get thành công hoặc put trùng khóa): tra bảng băm pos[key] để lấy con trỏ nút u trong \(O(1)\), gọi hàm detach(u) để gỡ nút khỏi vị trí cũ trong \(O(1)\), rồi gọi hàm attach_front(u) để gắn nút vào ngay sau head trong \(O(1)\).
Tiêu chí so sánh Mảng động (vector / ArrayList) Bảng băm + Hàng đợi ưu tiên (Heap) Bảng băm + Danh sách liên kết đôi (Chuẩn LRU)
Thời gian tra cứu get(key) \(O(C)\) (phải duyệt tìm khóa) \(O(\log C)\) (đẩy bản ghi thời gian mới vào heap) \(O(1)\) trung bình
Thời gian cập nhật put(key, value) \(O(C)\) (dồn mảng khi trục xuất) \(O(\log C)\) (rút đỉnh heap cũ và chèn mới) \(O(1)\) trung bình
Tìm phần tử LRU để trục xuất \(O(1)\) (nằm ở đầu hoặc cuối mảng) \(O(\log C)\) (lược bỏ các bản ghi lỗi thời trên đỉnh heap) \(O(1)\) chặt chẽ (lấy trực tiếp tail.prev)
Chi phí bộ nhớ cho \(C\) phần tử \(O(C)\) \(O(C + \text{số lần truy cập})\) nếu xóa lười \(O(C)\) chặt chẽ (tối đa \(C\) nút và \(C\) mục băm)

Ví dụ chạy tay từng bước với sức chứa C = 2

Để quan sát rõ cách hai con trỏ prev và next phối hợp với bảng băm pos, ta lần theo kịch bản kinh điển với sức chứa \(C = 2\) và 6 thao tác liên tiếp: put(1, 10), put(2, 20), get(1), put(3, 30), get(2), put(4, 40). Ban đầu, danh sách chỉ gồm hai nút lính canh nối trực tiếp với nhau: HEAD <-> TAIL, và bảng băm pos rỗng {}.

Bước Lệnh gọi Biến đổi nội bộ trong pos và danh sách liên kết đôi Thứ tự danh sách (HEAD -> ... -> TAIL) Giá trị trả về
1 put(1, 10) Khóa 1 chưa có. Tạo Node(1, 10), gắn ngay sau HEAD, thêm 1 -> Node(1, 10) vào pos. HEAD <-> (1, 10) <-> TAIL Không trả về
2 put(2, 20) Khóa 2 chưa có. Tạo Node(2, 20), gắn ngay sau HEAD, thêm 2 -> Node(2, 20) vào pos. Đủ \(2 / 2\) phần tử. HEAD <-> (2, 20) <-> (1, 10) <-> TAIL Không trả về
3 get(1) Tìm thấy khóa 1 trong pos. Gỡ Node(1, 10) khỏi vị trí cuối và gắn lại ngay sau HEAD. Lúc này (2, 20) bị đẩy xuống làm LRU. HEAD <-> (1, 10) <-> (2, 20) <-> TAIL 10
4 put(3, 30) Khóa 3 chưa có, bộ nhớ đã đầy (\(2 = C\)). Lấy nút sát trước TAIL là lru = (2, 20), tháo lru khỏi danh sách và xóa lru.key = 2 khỏi pos. Sau đó chèn Node(3, 30) vào ngay sau HEAD. HEAD <-> (3, 30) <-> (1, 10) <-> TAIL Không trả về
5 get(2) Tra pos không còn khóa 2 (đã bị trục xuất ở bước 4). Không làm thay đổi danh sách. HEAD <-> (3, 30) <-> (1, 10) <-> TAIL -1
6 put(4, 40) Khóa 4 chưa có, bộ nhớ đầy. Nút sát trước TAIL hiện tại là (1, 10) bị tháo bỏ và xóa khóa 1 khỏi pos. Chèn Node(4, 40) vào ngay sau HEAD. HEAD <-> (4, 40) <-> (3, 30) <-> TAIL Không trả về

Điểm mấu chốt nằm ở Bước 3 và Bước 4: dù khóa 1 được chèn vào từ đầu tiên (Bước 1), lệnh đọc get(1) ở Bước 3 đã làm mới lịch sử của nó và đưa (1, 10) lên sát sau HEAD. Nhờ vậy, khi khóa 3 xuất hiện ở Bước 4, phần tử nằm sát trước TAIL phải nhường chỗ lại chính là (2, 20).

Cài đặt đầy đủ bằng C++17, Python và Java 21

Trong khi phỏng vấn trực tiếp, người phỏng vấn thường yêu cầu ứng viên tự cài đặt cấu trúc nút liên kết đôi Node kèm hai hàm trợ giúp detach(u) và attach_front(u) thay vì gọi sẵn OrderedDict (Python) hay LinkedHashMap (Java), nhằm kiểm tra kỹ năng thao tác con trỏ không sinh lỗi. Bản Python và Java dưới đây cài đặt lớp LRUCache từ các con trỏ cơ sở với hai nút giả (hai hàm trợ giúp mang tên _remove/_add_front trong Python, remove/addFront trong Java); bản C++17 dùng cách std::list + splice nêu ở cuối mục này. Chương trình đọc kịch bản kiểm thử từ luồng vào chuẩn (hoặc tự chạy kịch bản mẫu nếu không có đầu vào) và in ra dãy kết quả của các lệnh get.

#include <iostream>
#include <list>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

class LRUCache {
    int cap;
    list<pair<int, int>> dll; // front = MRU, back = LRU
    unordered_map<int, list<pair<int, int>>::iterator> pos;

public:
    explicit LRUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        auto it = pos.find(key);
        if (it == pos.end()) return -1;
        dll.splice(dll.begin(), dll, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = pos.find(key);
        if (it != pos.end()) {
            it->second->second = value;
            dll.splice(dll.begin(), dll, it->second);
            return;
        }
        if ((int)dll.size() == cap) {
            int lru_key = dll.back().first;
            pos.erase(lru_key);
            dll.pop_back();
        }
        dll.emplace_front(key, value);
        pos[key] = dll.begin();
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int cap, q;
    if (!(cin >> cap >> q)) {
        LRUCache cache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        cout << cache.get(1) << " ";
        cache.put(3, 3);
        cout << cache.get(2) << " ";
        cache.put(4, 4);
        cout << cache.get(1) << " " << cache.get(3) << " " << cache.get(4) << "\n";
        return 0;
    }
    LRUCache cache(cap);
    vector<int> outs;
    for (int i = 0; i < q; i++) {
        string op;
        cin >> op;
        if (op == "PUT") {
            int k, v;
            cin >> k >> v;
            cache.put(k, v);
        } else {
            int k;
            cin >> k;
            outs.push_back(cache.get(k));
        }
    }
    for (size_t i = 0; i < outs.size(); i++) {
        if (i) cout << " ";
        cout << outs[i];
    }
    cout << "\n";
    return 0;
}

Nếu người phỏng vấn hỏi thêm về công cụ có sẵn trong thư viện chuẩn sau khi bạn đã hoàn tất cài đặt con trỏ:

  • Trong C++17, ta có thể kết hợp std::list<pair<int, int>> với std::unordered_map<int, list<pair<int, int>>::iterator> và dùng phương thức cache_list.splice(cache_list.begin(), cache_list, it) để chuyển nút về đầu danh sách trong \(O(1)\).
  • Trong Python, lớp collections.OrderedDict cài đặt sẵn đúng cấu trúc bảng băm kèm danh sách liên kết đôi nội bộ với hai phương thức move_to_end(key, last=False) và popitem(last=True).
  • Trong Java, lớp java.util.LinkedHashMap<K, V> hỗ trợ chế độ thứ tự truy cập khi truyền accessOrder = true vào hàm khởi tạo và ghi đè phương thức removeEldestEntry.

Phân tích độ phức tạp và các lỗi sai thường gặp

Độ phức tạp thời gian và không gian

  • Thời gian thực thi:
    • Hàm detach(u) và attach_front(u) chỉ thực hiện cố định từ \(2\) đến \(4\) phép gán tham chiếu con trỏ, tức \(O(1)\) chặt chẽ.
    • Hàm get(key) thực hiện \(1\) lần tra bảng băm pos (\(O(1)\) trung bình) và tối đa \(1\) cặp lệnh detach + attach_front (\(O(1)\)).
    • Hàm put(key, value) thực hiện \(1\) lần tra bảng băm, tối đa \(1\) lần xóa khóa cũ ở tail.prev và \(1\) lần thêm khóa mới vào pos kèm nối con trỏ, tổng cộng \(O(1)\) trung bình.
  • Không gian bộ nhớ: Bộ nhớ đệm chỉ giữ tối đa \(C\) nút thực tế trên danh sách liên kết đôi (cộng \(2\) nút lính canh head, tail) và tối đa \(C\) cặp khóa - con trỏ trong bảng băm pos. Do đó chi phí bộ nhớ phụ là \(O(C)\).

Bốn lỗi phổ biến khiến ứng viên mất điểm khi viết code

  1. Quên lưu thuộc tính key bên trong cấu trúc Node: Nhiều ứng viên chỉ khai báo struct Node { int val; Node *prev, *next; }. Khi bộ nhớ đầy và lấy được nút lru = tail->prev, bạn chỉ nhìn thấy lru->val chứ không biết khóa của nó là gì để gọi pos.erase(lru->key). Lúc đó bảng băm pos vẫn giữ con trỏ rác trỏ tới vùng nhớ đã bị thu hồi và kích thước pos.size() tăng mãi không giảm.
  2. Quên đưa nút lên đầu khi put(key, value) gặp khóa đã tồn tại: Khi gọi put với một khóa đã nằm trong bộ nhớ đệm, ngoài việc gán u->val = value, đây cũng là một lần truy cập mới nên bắt buộc phải gọi detach(u) và attach_front(u). Nếu chỉ đổi giá trị mà giữ nguyên vị trí cũ, thứ tự LRU sẽ bị sai lệch.
  3. Không dùng nút giả head và tail: Tự quản lý hai con trỏ trỏ trực tiếp vào phần tử thật đầu tiên và cuối cùng khiến bạn phải viết hàng loạt nhánh if (u == head), if (u == tail), if (head == tail) rất dễ sót trường hợp sức chứa \(C = 1\). Hai nút lính canh triệt tiêu hoàn toàn các nhánh rẽ này vì mọi nút dữ liệu thật luôn nằm kẹp giữa hai nút không bao giờ null.
  4. Cách tự kiểm chứng tại nhà: Khi tự luyện tập, bạn có thể viết thêm một lớp mô phỏng chậm bằng mảng các cặp (key, value) (mỗi lần chạm tới một khóa thì xóa cặp đó khỏi mảng và push_back vào cuối mảng; khi mảng dài quá \(C\) thì xóa phần tử đầu tiên ở chỉ số \(0\)). Hãy sinh ngẫu nhiên vài trăm thao tác get và put với miền khóa nhỏ từ \(1\) đến \(5\) trên sức chứa \(C = 1\) và \(C = 2\) rồi so kết quả giữa hai cách cài đặt: miền khóa hẹp sẽ ép chương trình liên tục rơi vào các ca ghi đè khóa cũ và trục xuất phần tử vừa chèn.

Luyện ngay trên Big-O Coding

Để rèn kỹ năng thao tác con trỏ hai chiều và làm chủ mẫu thiết kế bộ nhớ đệm trong phỏng vấn, bạn hãy thực hành trực tiếp bài toán thiết kế LRU Cache cùng các bài toán biến đổi con trỏ danh sách liên kết liên quan trong lộ trình Coding Interview 150:

Tại sao không dùng danh sách liên kết đơn (Singly Linked List) kết hợp với bảng băm cho LRU Cache?

Trong danh sách liên kết đơn, để xóa một nút u nằm ở giữa danh sách, bạn bắt buộc phải sửa con trỏ next của nút đứng liền trước u (prev_node.next = u.next). Dù bảng băm cho bạn địa chỉ của u trong \(O(1)\), danh sách đơn không có con trỏ ngược u.prev nên bạn không biết nút nào đứng trước u nếu không duyệt lại từ đầu danh sách trong \(O(C)\). Danh sách liên kết đôi giải quyết triệt để vấn đề này nhờ lưu cả hai chiều prev và next.

Làm thế nào để nâng cấp LRU Cache thành cấu trúc an toàn đa luồng (Thread-safe) trong hệ thống thực tế?

Vì mỗi thao tác đọc get(key) trong LRU Cache đều làm thay đổi cấu trúc liên kết nội bộ (tháo nút khỏi vị trí hiện tại và đưa lên đầu danh sách), ta không thể dùng khóa đọc - ghi thông thường (ReadWriteLock cho phép nhiều luồng đọc song song) nếu vẫn cập nhật danh sách ngay lập tức. Giải pháp thực tế trong phỏng vấn thiết kế hệ thống gồm: (1) dùng khóa loại trừ lẫn nhau (Mutex) bảo vệ toàn bộ thao tác get/put, (2) phân mảnh bộ nhớ đệm (Sharded LRU Cache) thành \(K\) phân vùng độc lập theo hash(key) % K để giảm tranh chấp khóa xuống \(K\) lần, hoặc (3) gom các sự kiện đọc vào bộ đệm vòng (ring buffer) để cập nhật thứ tự LRU theo lô bất đồng bộ như cách thư viện Caffeine trong Java thực hiện.

Sự khác biệt chính giữa LRU Cache và LFU Cache (Least Frequently Used) là gì?

LRU Cache trục xuất phần tử dựa thuần túy vào thời điểm truy cập gần nhất, còn LFU Cache trục xuất phần tử có tổng số lần truy cập (tần suất) thấp nhất (nếu nhiều phần tử có cùng tần suất thấp nhất thì mới xét đến phần tử lâu nhất chưa dùng theo quy tắc LRU). Để cài đặt LFU Cache trong \(O(1)\), ngoài bảng băm key -> Node*, ta cần thêm bảng băm thứ hai ánh xạ mỗi mức tần suất freq sang một danh sách liên kết đôi riêng và duy trì biến min_freq theo dõi mức tần suất nhỏ nhất hiện có.

Muốn học bài bản cùng giảng viên?

Luyện LeetCode thực chiến theo pattern, giải bài trong 45 phút và mock interview cùng AI. 16 buổi online, lớp 7–12 học viên, chọn C++, Java hoặc Python.

Xem Khóa LeetCode

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483