- 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ừkeysang đị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ả
headvàtailnố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ỏnullkhi 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
keyngay 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ướctail, ta cần biếtkeycủ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:
- Thao tác
get(key): Nếukeyđ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ếukeykhông tồn tại (trượt bộ nhớ đệm), trả về \(-1\). - Thao tác
put(key, value): Nếukeyđã 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ếukeychư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)\).
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ó (
getthành công hoặcputtrùng khóa): tra bảng bămpos[key]để lấy con trỏ nútutrong \(O(1)\), gọi hàmdetach(u)để gỡ nút khỏi vị trí cũ trong \(O(1)\), rồi gọi hàmattach_front(u)để gắn nút vào ngay sauheadtrong \(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;
}
import sys
class Node:
__slots__ = ("key", "val", "prev", "next")
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.pos = {}
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node: Node) -> None:
p, n = node.prev, node.next
p.next = n
n.prev = p
def _add_front(self, node: Node) -> None:
nxt = self.head.next
node.next = nxt
node.prev = self.head
self.head.next = node
nxt.prev = node
def get(self, key: int) -> int:
if key not in self.pos:
return -1
node = self.pos[key]
self._remove(node)
self._add_front(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.pos:
node = self.pos[key]
node.val = value
self._remove(node)
self._add_front(node)
return
if len(self.pos) == self.cap:
lru = self.tail.prev
self._remove(lru)
del self.pos[lru.key]
node = Node(key, value)
self._add_front(node)
self.pos[key] = node
def main():
tokens = sys.stdin.read().split()
if not tokens:
c = LRUCache(2)
c.put(1, 1)
c.put(2, 2)
a = c.get(1)
c.put(3, 3)
b = c.get(2)
c.put(4, 4)
print(f"{a} {b} {c.get(1)} {c.get(3)} {c.get(4)}")
return
cap = int(tokens[0])
q = int(tokens[1])
c = LRUCache(cap)
idx = 2
outs = []
for _ in range(q):
op = tokens[idx]
if op == "PUT":
k = int(tokens[idx + 1])
v = int(tokens[idx + 2])
c.put(k, v)
idx += 3
else:
k = int(tokens[idx + 1])
outs.append(str(c.get(k)))
idx += 2
print(" ".join(outs))
if __name__ == "__main__":
main()
import java.util.*;
public class Main {
static class Node {
int key, val;
Node prev, next;
Node(int k, int v) { key = k; val = v; }
}
static class LRUCache {
private final int cap;
private final Map<Integer, Node> pos = new HashMap<>();
private final Node head = new Node(0, 0);
private final Node tail = new Node(0, 0);
LRUCache(int capacity) {
this.cap = capacity;
head.next = tail;
tail.prev = head;
}
private void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void addFront(Node node) {
Node nxt = head.next;
node.next = nxt;
node.prev = head;
head.next = node;
nxt.prev = node;
}
public int get(int key) {
Node node = pos.get(key);
if (node == null) return -1;
remove(node);
addFront(node);
return node.val;
}
public void put(int key, int value) {
Node node = pos.get(key);
if (node != null) {
node.val = value;
remove(node);
addFront(node);
return;
}
if (pos.size() == cap) {
Node lru = tail.prev;
remove(lru);
pos.remove(lru.key);
}
Node fresh = new Node(key, value);
addFront(fresh);
pos.put(key, fresh);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
if (!sc.hasNextInt()) {
LRUCache c = new LRUCache(2);
c.put(1, 1);
c.put(2, 2);
int a = c.get(1);
c.put(3, 3);
int b = c.get(2);
c.put(4, 4);
System.out.println(a + " " + b + " " + c.get(1) + " " + c.get(3) + " " + c.get(4));
return;
}
int cap = sc.nextInt();
int q = sc.nextInt();
LRUCache c = new LRUCache(cap);
List<String> outs = new ArrayList<>();
for (int i = 0; i < q; i++) {
String op = sc.next();
if (op.equals("PUT")) {
int k = sc.nextInt();
int v = sc.nextInt();
c.put(k, v);
} else {
int k = sc.nextInt();
outs.add(String.valueOf(c.get(k)));
}
}
System.out.println(String.join(" ", outs));
}
}
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ớistd::unordered_map<int, list<pair<int, int>>::iterator>và dùng phương thứccache_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.OrderedDictcà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ứcmove_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ềnaccessOrder = truevào hàm khởi tạo và ghi đè phương thứcremoveEldestEntry.
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ămpos(\(O(1)\) trung bình) và tối đa \(1\) cặp lệnhdetach+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.prevvà \(1\) lần thêm khóa mới vàoposkèm nối con trỏ, tổng cộng \(O(1)\) trung bình.
- Hàm
- 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ămpos. 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
- Quên lưu thuộc tính
keybên trong cấu trúcNode: Nhiều ứng viên chỉ khai báostruct Node { int val; Node *prev, *next; }. Khi bộ nhớ đầy và lấy được nútlru = tail->prev, bạn chỉ nhìn thấylru->valchứ không biết khóa của nó là gì để gọipos.erase(lru->key). Lúc đó bảng bămposvẫn giữ con trỏ rác trỏ tới vùng nhớ đã bị thu hồi và kích thướcpos.size()tăng mãi không giảm. - Quên đưa nút lên đầu khi
put(key, value)gặp khóa đã tồn tại: Khi gọiputvới một khóa đã nằm trong bộ nhớ đệm, ngoài việc gánu->val = value, đây cũng là một lần truy cập mới nên bắt buộc phải gọidetach(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. - Không dùng nút giả
headvà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ánhif (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. - 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_backvà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ácgetvàputvớ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ó.
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.


