LRU (Least Recently Used) cache sẽ loại bỏ phần tử lâu không được dùng tới nhất khi cache đầy. Đây là câu hỏi phỏng vấn kinh điển, nhưng cũng chính là cơ chế đứng sau nhiều hệ thống thực tế: cache truy vấn database, cache CDN, quản lý bộ nhớ tab trình duyệt, connection pool.
Cách làm ngây thơ — dùng một mảng rồi quét tìm phần tử cũ nhất — tốn O(n) cho mỗi thao tác. Bí quyết để đạt O(1) là kết hợp hai cấu trúc dữ liệu: hash map để tra cứu O(1), và doubly linked list để sắp xếp lại thứ tự với O(1).
Cấu Trúc Dữ Liệu
Mỗi node vừa nằm trong linked list, vừa có một con trỏ được lưu trong hash map. head là node lính canh (sentinel) trỏ tới node được dùng gần đây nhất; tail là sentinel trỏ tới node lâu không dùng nhất — đây chính là ứng viên bị loại bỏ khi cache đầy.
Hai Thao Tác Chính
get(key): tra cứu trong hash map để tìm node với độ phức tạp O(1). Nếu tìm thấy, gỡ node đó khỏi vị trí hiện tại và gắn lại ngay sau head (vì nó vừa được dùng gần đây nhất), rồi trả về giá trị. Nếu không tìm thấy, trả về null/miss.
put(key, value): nếu key đã tồn tại, cập nhật giá trị và đưa node lên đầu, giống như get. Nếu là key mới và cache đã đầy, gỡ node ngay trước tail (node lâu không dùng nhất) khỏi cả linked list lẫn hash map, sau đó chèn node mới vào đầu danh sách.
Cả hai thao tác đều chỉ đụng tới một số lượng con trỏ cố định — không cần quét qua danh sách.
Cài Đặt Bằng PHP
class Node
{
public function __construct(
public string $key,
public mixed $value,
public ?Node $prev = null,
public ?Node $next = null,
) {}
}
class LRUCache
{
private array $map = [];
private Node $head;
private Node $tail;
private int $capacity;
public function __construct(int $capacity)
{
$this->capacity = $capacity;
$this->head = new Node('', null);
$this->tail = new Node('', null);
$this->head->next = $this->tail;
$this->tail->prev = $this->head;
}
public function get(string $key): mixed
{
if (!isset($this->map[$key])) {
return null;
}
$node = $this->map[$key];
$this->detach($node);
$this->attachToFront($node);
return $node->value;
}
public function put(string $key, mixed $value): void
{
if (isset($this->map[$key])) {
$node = $this->map[$key];
$node->value = $value;
$this->detach($node);
$this->attachToFront($node);
return;
}
if (count($this->map) >= $this->capacity) {
$lru = $this->tail->prev;
$this->detach($lru);
unset($this->map[$lru->key]);
}
$node = new Node($key, $value);
$this->map[$key] = $node;
$this->attachToFront($node);
}
private function detach(Node $node): void
{
$node->prev->next = $node->next;
$node->next->prev = $node->prev;
}
private function attachToFront(Node $node): void
{
$node->next = $this->head->next;
$node->prev = $this->head;
$this->head->next->prev = $node;
$this->head->next = $node;
}
}
Hai sentinel node (head và tail) tồn tại chỉ để tránh phải kiểm tra null ở các trường hợp biên — mọi node thật sự luôn có prev và next hợp lệ để thao tác.
Những Lỗi Hay Gặp
Quên cập nhật hash map khi evict. Nếu bạn gỡ một node khỏi linked list nhưng vẫn để entry của nó trong $map, lần get() tiếp theo cho key đó sẽ trả về một node đã lỗi thay vì một cache miss.
Sai lệch một đơn vị (off-by-one) khi kiểm tra capacity. Kiểm tra count($this->map) >= $this->capacity trước khi chèn node mới, chứ không phải sau — nếu không cache sẽ tạm thời chứa capacity + 1 phần tử.
Coi get() là thao tác chỉ đọc. Một cache hit vẫn làm thay đổi trạng thái — nó di chuyển node lên đầu danh sách. Bỏ qua bước này sẽ biến LRU cache của bạn thành một cache FIFO thông thường.
Dùng mảng và array_shift() làm "queue". array_shift() có độ phức tạp O(n) vì PHP phải đánh lại chỉ số cho mảng. Điều này phá vỡ hoàn toàn mục đích của bài tập — doubly linked list mới là thứ giúp việc evict đạt O(1).
Khi Nào Nên Dùng Giải Pháp Có Sẵn
Đừng tự viết cache này cho production trừ khi bạn có lý do cụ thể (ví dụ: nhúng cache ngay trong một tiến trình PHP duy nhất, không phụ thuộc bên ngoài). Với bất kỳ trường hợp nào cần chia sẻ giữa nhiều request hoặc nhiều process, các chính sách evict có sẵn của Redis (allkeys-lru, volatile-lru) hoặc thư viện như symfony/cache đã giải quyết bài toán này một cách đúng đắn và bền vững. Giá trị của việc tự tay code lại là để hiểu rõ vì sao O(1) cần cả hai cấu trúc dữ liệu cùng lúc — chỉ một mình cấu trúc nào cũng không đủ.
Thử thách
Luyện tập ngay điều vừa học. Viết lời giải, mở gợi ý nếu bí.
Đề bài
Implement the LRUCache class below. It must support get(key) and put(key, value), each running in O(1) time, using a fixed capacity passed to the constructor. When put() is called on a full cache with a new key, evict the least recently used entry before inserting. Both get() and put() on an existing key should mark that key as most recently used. Fill in the TODOs in the Node and LRUCache classes.
Code khởi tạo
class Node
{
public int $key;
public int $value;
public ?Node $prev = null;
public ?Node $next = null;
public function __construct(int $key, int $value)
{
$this->key = $key;
$this->value = $value;
}
}
class LRUCache
{
private int $capacity;
private array $map = [];
private Node $head;
private Node $tail;
public function __construct(int $capacity)
{
$this->capacity = $capacity;
// TODO: create sentinel head/tail nodes and link them together
}
public function get(int $key): int
{
// TODO: return -1 if key not found
// TODO: otherwise move the node to the front (most recently used) and return its value
}
public function put(int $key, int $value): void
{
// TODO: if key exists, update value and move node to front
// TODO: if key doesn't exist, create a new node and add it to front
// TODO: if capacity exceeded, remove the least recently used node (just before tail)
}
private function remove(Node $node): void
{
// TODO: unlink $node from its neighbors
}
private function addToFront(Node $node): void
{
// TODO: insert $node right after head
}
}Lời giải của bạn
Gợi ý
Đã mở hết gợi ýUse two sentinel nodes for head and tail to avoid null checks
class Node
{
public int $key;
public int $value;
public ?Node $prev = null;
public ?Node $next = null;
public function __construct(int $key, int $value)
{
$this->key = $key;
$this->value = $value;
}
}
class LRUCache
{
private int $capacity;
private array $map = [];
private Node $head;
private Node $tail;
public function __construct(int $capacity)
{
$this->capacity = $capacity;
$this->head = new Node(0, 0);
$this->tail = new Node(0, 0);
$this->head->next = $this->tail;
$this->tail->prev = $this->head;
}
public function get(int $key): int
{
if (!isset($this->map[$key])) {
return -1;
}
$node = $this->map[$key];
$this->remove($node);
$this->addToFront($node);
return $node->value;
}
public function put(int $key, int $value): void
{
if (isset($this->map[$key])) {
$node = $this->map[$key];
$node->value = $value;
$this->remove($node);
$this->addToFront($node);
return;
}
if (count($this->map) >= $this->capacity) {
$lru = $this->tail->prev;
$this->remove($lru);
unset($this->map[$lru->key]);
}
$node = new Node($key, $value);
$this->map[$key] = $node;
$this->addToFront($node);
}
private function remove(Node $node): void
{
$node->prev->next = $node->next;
$node->next->prev = $node->prev;
}
private function addToFront(Node $node): void
{
$node->next = $this->head->next;
$node->prev = $this->head;
$this->head->next->prev = $node;
$this->head->next = $node;
}
}