LRUCache là viết tắt của Least Recently Used Cache, đây là phương pháp phổ biến nhất để cập nhật cache bằng cách loại bỏ những giá trị ít được sử dụng gần đây nhất.
Do đây là cache, vì vậy ta cần thực hiện các thao tác “get - truy xuất dữ liệu”, “put - cập nhật dữ liệu”, nhanh nhất có thể. Cách nhanh nhất để thực hiện những việc này là sử dụng bảng băm (HashTable hoặc HashMap).
Để đảm bảo tính chất “loại bỏ những giá trị ít được sử dụng gần đây nhất” của LRUCache, ta cần biết những giá trị nào được sử dụng gần đây nhất. Ta có thể sử dụng LinkedList với quy ước: giá trị được sử dụng cuối cùng luôn ở đầu của LinkedList. Như vậy, khi ta thêm giá trị mới vào LRUCache, giá trị mới luôn nằm ở đầu của LinkedList.
Với quy ước trên, giá trị nằm ở cuối LinkedList là giá trị ít được sử dụng gần đây nhất. Khi số lượng phần tử trong LRUCache vượt quá quy định, ta đơn giản chỉ cần xóa đi giá trị nằm ở cuối LinkedList và key tương ứng trong HashMap.
Tổng kết lại, ta có cấu trúc dữ liệu vào giải thuật như sau:
1. Ta sử dụng LinkedList để lưu trữ giá trị cache với quy ước: “giá trị được sử dụng cuối cùng luôn ở đầu của LinkedList”.
2. Ta sử dụng HashMap để lưu trữ cache key và tham chiếu tới node chứa giá trị trong LinkedList.
3. Khi hàm int get(int key)
được gọi, ta kiểm tra HashMap và di chuyển node tương ứng lên đầu của LinkedList.
4. Khi hàm void put(int key, int value)
được gọi, ta thêm một node mới vào đầu của LinkedList, đồng thời cập nhật HashMap. Nếu số lượng phần tử vượt quá quy định, ta xoá đi giá trị nằm ở cuối LinkedList, đồng thời xóa key tương ứng trong HashMap.
Thao tác xóa node trong Singly Linked List có độ phức tạp thời gian Time Complexity là O(n), để tối ưu xuống O(1), ta có thể sử dụng Doubly Linked List.
Cả hàm get và put đều có độ phức tạp thời gian Time Complexity là O(1).
(by phucnh)