Khi thiết kế một hệ thống Caching cho dữ liệu người dùng, tại sao việc sử dụng mảng để lưu trữ cache lại có độ phức tạp O(N) cho việc xóa phần tử cũ nhất và cấu trúc dữ liệu nào giúp tối ưu hóa điều này?

Question

Accepted Answer

Phân tích vấn đề
Khi dùng mảng, việc xóa phần tử ở đầu (để duy trì kích thước cache) yêu cầu dịch chuyển tất cả các phần tử còn lại lên một vị trí, dẫn đến độ phức tạp O(N). Trong hệ thống có tần suất truy cập cao, điều này gây lãng phí tài nguyên CPU.
Giải pháp tối ưu
Sử dụng Doubly Linked List kết hợp với Hash Map (cấu trúc của LRU Cache).

Hash Map cho phép tìm kiếm phần tử trong O(1).
Doubly Linked List cho phép thêm/xóa phần tử ở đầu hoặc cuối trong O(1) bằng cách thay đổi con trỏ (pointer).

Cơ chế hoạt động

Get: Tìm trong Map -> O(1), di chuyển node trong Linked List -> O(1).
Put: Thêm vào Map -> O(1), thêm vào Linked List -> O(1).

Lưu ý thực chiến
Trong các dự án Enterprise, thay vì tự viết LRU Cache, hãy sử dụng các giải pháp đã được tối ưu hóa như Redis hoặc các thư viện chuyên dụng để đảm bảo tính sẵn sàng và hiệu năng cao.

Khi thiết kế một hệ thống Caching cho dữ liệu người dùng, tại sao việc sử dụng mảng để lưu trữ cache lại có độ phức tạp O(N) cho việc xóa phần tử cũ nhất và cấu trúc dữ liệu nào giúp tối ưu hóa điều này?

Phân tích vấn đề

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi big-o notation liên quan cùng chủ đề