Họ đang đo gì
Bạn có chọn cấu trúc dữ liệu theo THAO TÁC cần thiết không, hay mặc định dùng map cho mọi thứ.
Trả lời ngắn~30 giây
Bảng băm cho tra cứu O(1) nhưng KHÔNG giữ thứ tự — đó chính là thứ nó đổi đi. Nếu cần cả hai thì dùng cây tìm kiếm cân bằng (TreeMap trong Java, std::map trong C++): tra cứu O(log n) nhưng duyệt theo thứ tự và truy vấn theo khoảng đều làm được. Nếu chỉ cần giữ thứ tự CHÈN chứ không cần sắp xếp thì LinkedHashMap cho bạn O(1) cộng thứ tự chèn, và nó cũng là nền để làm LRU cache.
Giải thích sâu
Câu hỏi này thường mở ra một câu tiếp: khi nào bạn cần khoảng chứ không chỉ một khoá. Bảng băm không trả lời được “cho tôi mọi khoá trong [a, b]” hay “khoá nhỏ nhất lớn hơn x” — vì hàm băm cố tình phá vỡ thứ tự để phân bố đều. Cây thì trả lời được cả hai trong O(log n + k). Đây cũng chính là lý do index B-tree trong database không dùng bảng băm cho phần lớn trường hợp.
Với LRU cache, cách cài đặt kinh điển đáng biết: bảng băm cho tra cứu O(1) kết hợp danh sách liên kết đôi để đưa phần tử vừa dùng lên đầu, cũng O(1). Không có cấu trúc đơn lẻ nào làm được cả hai, nên bạn ghép hai cấu trúc và mỗi mục nằm trong cả hai. Trong Java thì LinkedHashMap với accessOrder = true và ghi đè removeEldestEntry cho bạn toàn bộ điều này miễn phí.
Còn một nhóm bài toán mà câu trả lời là heap chứ không phải map: khi bạn chỉ cần phần tử NHỎ NHẤT hoặc LỚN NHẤT liên tục — hàng đợi ưu tiên, top-k, trộn nhiều luồng đã sắp xếp. Heap cho lấy phần tử cực trị O(log n) mà không phải giữ toàn bộ thứ tự, nên nó rẻ hơn cây khi bạn không cần duyệt.
Câu hỏi tiếp theo họ sẽ hỏi
?Tìm kiếm theo tiền tố thì dùng gì?
Trie, hoặc trong database thì index B-tree cũng làm được vì nó giữ thứ tự từ điển — LIKE 'abc%' dùng được index, còn LIKE '%abc' thì không. Trie thắng khi bạn cần gợi ý tự động trong bộ nhớ với hàng triệu chuỗi chung tiền tố.
Trả lời thế này là mất điểm
- Dùng map cho mọi thứ rồi sắp xếp lại mỗi lần cần thứ tự. Đó là O(n log n) mỗi lần đọc để tiết kiệm O(log n) mỗi lần ghi.