Chào các bạn, hôm nay mình muốn giới thiệu một bài code từng được phỏng vấn role junior. Nội dung của bài toán là: Implement thuật toán cache LRU.

Mô tả bài toán

Như các bạn đã biết thì cache là bộ nhớ đệm giúp tăng hiệu năng hệ thống, tuy nhiên nó cũng có giới hạn dung lượng của nó. Vì vậy mà khi cache đầy mà muốn thêm data vào thì phải loại bớt những data cũ trong hệ thống. Đó chính là thuật toán cache replacement, trong đó thì có bao gồm thuật toán LRU.

Least Recently Used (LRU) là 1 thuật toán cache replacement, khi bộ nhớ đệm đầy, LRU sẽ chọn dữ liệu được sử dụng ít nhất và loại bỏ nó để tạo không gian cho dữ liệu mới. Ưu tiên của dữ liệu trong bộ nhớ đệm thay đổi tùy theo nhu cầu của dữ liệu đó, tức là nếu một số dữ liệu được lấy hoặc cập nhật gần đây thì ưu tiên của dữ liệu đó sẽ được thay đổi và gán cho mức ưu tiên cao nhất, và ưu tiên của dữ liệu giảm nếu nó vẫn không được sử dụng qua các lần thao tác.

Xác định bài toán

Đầu tiên cần xác định những thao tác với cache. Có 3 thao tác chính:

LRUCache(capacity n): khởi tạo cache với tối đa n phần tử
Get(key): lấy ra dữ liệu bằng key
Put(key, value): Update value cho key nếu tồn tại key trong hệ thống, nếu ko tồn tại key thì thêm mới một cặp key-value

Article content

Cách LRU cache hoạt động

Phân tích bài toán

Bài toán có key-value, cần value khi truyền key, dữ liệu trả ra phải nhanh (O(1)) nghĩ ngay đến HashMap hay Dictionary để lưu dữ liệu.
Cần phải loại bỏ key “cũ” nhất khi add thêm một cặp k-v mới. Đầu tiên cần xác định đâu là key cũ nhất để loại bỏ (thời gian tối đa nên là O(1)), và thời gian để loại bỏ key đó khỏi cache (cũng tối đa nên là O(1). Mình có thể liên tưởng đến Queue, Tuy nhiên queue này phải được implement bằng DoubleLinkedList. Bởi vì ta có thể chèn hay xóa phần tử mất O(1). Vấn đề là nếu truy cập 1 phần tử ở giữa queue, tức là cần “bốc” nó lên đầu queue, nhưng khổ nỗi Queue implement bằng LinkedList, nên muốn truy cập phần tử ở giữa queue phải duyêt từ đầu cho đến khi gặp, tức mất O(n)
Vậy thì: sao không kết hợp HashMap và LinkedList, HashMap có value là địa chỉ của ô giá trị trong LinkedList, bằng cách này, truy cập giá trị mất O(1) do HashMap, đồng thời truy cập ô địa chỉ trong LinkedList cũng chỉ mất O(1), và có thể thực hiện nhanh việc xếp giá trị lên đầu Queue(LinkedList)