Một LRU (Least Recently Used) cache loại bỏ phần tử chưa được truy cập lâu nhất khi đạt đến dung lượng. Thiết kế kinh điển kết hợp một hash map (tra cứu O(1)) với một doubly linked list (sắp xếp lại O(1)), cho get và put O(1).
HashMap: key -> node DLL (thứ tự gần đây):
MRU <-> ... <-> LRU
get/put: map tìm node chuyển node vừa chạm lên đầu (MRU)
trong O(1); DLL nối nó loại bỏ tail (LRU) khi đầy
lên đầu trong O(1)
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cap = capacity
self.cache = OrderedDict() # giữ thứ tự truy cập
def get(self, key): # O(1)
if key not in self.cache:
return -1
self.cache.move_to_end(key) # đánh dấu là dùng gần đây nhất
return self.cache[key]
def put(self, key, value): # O(1)
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.cap:
self.cache.popitem(last=False) # loại bỏ cái ít dùng gần đây nhất
OrderedDict bản thân nó là một hash map cộng với một doubly linked list, chính xác là cấu trúc được mô tả ở trên.
| Thao tác | Thời gian |
|---|---|
| get | O(1) |
| put | O(1) |
| không gian | O(capacity) |
Một doubly linked list cho phép bạn tách một node ở giữa trong O(1) (bạn giữ prev/next của nó), điều này không thể với một singly linked list hoặc array mà không có một lần dịch O(n).
LRU cache nằm ở phía trước database, web server, và CPU để giữ dữ liệu nóng nhanh và bộ nhớ có giới hạn.
Bài toán này là chủ đề chủ lực trong phỏng vấn senior vì nó kiểm tra việc kết hợp hai cấu trúc sao cho điểm yếu của mỗi cái được che bởi cái kia — một kỹ năng thiết kế hệ thống then chốt.