Bạn cần một cấu trúc tra cứu theo khóa. Hash table (unordered_map) là O(1) trung bình, cây tìm kiếm nhị phân cân bằng (std::map, cây đỏ-đen) là O(log n). So Big-O thì rõ ràng: O(1) nhỏ hơn O(log n), vậy chọn hash, hết chuyện? Đây là một trong những "so sánh Big-O" gây hiểu lầm nhất, vì hai cấu trúc này không làm cùng một việc — một cái đổi thứ tự lấy tốc độ, một cái giữ thứ tự. Tôi đo cả hai với 1 triệu phần tử trong container gcc:13, cả tra cứu điểm lẫn truy vấn khoảng, và con số cho thấy "cái nào nhanh hơn" là câu hỏi sai.
Cùng "tra cứu", nhưng đổi thứ tự lấy tốc độ (hoặc ngược lại)
Hash table băm khóa thành chỉ số bucket rồi nhảy thẳng tới đó — tra cứu điểm O(1), chỉ 1–2 probe liền mạch khi tải thấp. Nhưng cái giá của tốc độ đó là vứt bỏ thứ tự: khóa nằm rải rác theo giá trị băm, không theo giá trị khóa. Muốn "phần tử nhỏ nhất", "mọi khóa trong khoảng [a, b]", hay "duyệt theo thứ tự tăng dần", hash table chịu — nó phải lấy hết khóa ra rồi sort lại, O(n log n).
Cây tìm kiếm nhị phân cân bằng (cây đỏ-đen của std::map) giữ khóa có thứ tự trong cây. Tra cứu điểm là O(log n) — đi từ gốc xuống, mỗi bước rẽ trái/phải. Nhưng chú ý: mỗi bước là theo một con trỏ tới node con, và node con nằm ở đâu đó malloc trả về — nên mỗi bước rẽ là một cache miss, y như duyệt linked list. Đổi lại, cây có sẵn thứ tự: lower_bound(x) tìm phần tử nhỏ nhất ≥ x trong O(log n), rồi duyệt tiếp theo thứ tự trong O(k) — range query mà hash không mơ tới.
Đo: hash thắng tra điểm, cây thắng thứ tự
Tôi nạp 1 triệu cặp khóa-giá trị vào cả std::unordered_map và std::map, rồi đo hai loại truy vấn:
A. TRA CỨU ĐIỂM (point lookup), 1 triệu truy vấn hit:
hash (unordered_map) : 16,2 ns/tra cứu
BST (map, ~log2(1tr)=20 bước) : 518,5 ns/tra cứu
-> hash nhanh hơn ~32 lần
B. RANGE QUERY (tìm phần tử >= x rồi duyệt 100 phần tử theo thứ tự):
BST (lower_bound + duyệt k) : 7,8 µs/truy vấn (O(log n + k))
hash : KHÔNG có thứ tự -> lấy hết + SORT O(n log n)
1 lần sort 1 triệu khóa: 54,2 ms
Nhìn A (tra cứu điểm): hash 16,2 ns, cây 518,5 ns — hash nhanh hơn 32 lần. Big-O đúng về chiều: O(1) thắng O(log n). Nhưng chú ý con số cây lớn hơn nhiều so với "chỉ 20 bước" gợi ý — 518 ns cho ~20 bước là ~26 ns/bước, vì mỗi bước rẽ trong cây là một lần nhảy tới node ở địa chỉ khó đoán, dính cache miss. (Các node gần gốc còn nóng trong cache nên không phải 104 ns đầy đủ như phần 1, nhưng các tầng dưới thì miss.) Nếu bạn chỉ tra cứu điểm, hash thắng rõ.
Giờ nhìn B (range query) — nơi câu chuyện đảo ngược hoàn toàn. Cây làm range query một cách tự nhiên: lower_bound(x) nhảy tới đúng chỗ trong O(log n), rồi duyệt 100 phần tử kế tiếp đã có sẵn theo thứ tự — tổng cộng 7,8 µs mỗi truy vấn. Hash table thì không có khái niệm thứ tự: để trả lời "mọi khóa ≥ x", nó phải lôi toàn bộ triệu khóa ra và sort — mà chỉ riêng một lần sort 1 triệu khóa đã tốn 54,2 ms. Tức là một range query kiểu đó trên hash chậm hơn cây khoảng 7.000 lần (54,2 ms so với 7,8 µs), và đó là còn chưa tính bạn phải làm lại mỗi khi bảng thay đổi. Với truy vấn cần thứ tự, cây không chỉ thắng — nó là lựa chọn khả thi duy nhất.
Một lần tôi đo hớ: "hash luôn tốt hơn vì O(1) < O(log n)"
Tôi vào đo với phép so Big-O ngây thơ: "O(1) nhỏ hơn O(log n), nên hash luôn thắng cây". Đo cho thấy điều đó chỉ đúng cho một loại truy vấn — tra cứu điểm (nơi hash nhanh 32 lần). Với range query và mọi thứ cần thứ tự, hash không có thứ tự nên phải sort lại O(n log n) (54,2 ms cho một lần sort triệu khóa), trong khi cây trả lời trong 7,8 µs. Big-O của tra cứu điểm không nói gì về chi phí của một loại truy vấn khác. Còn niềm tin phụ "cây O(log n) chậm chỉ vì 20 bước" cũng thiếu: mỗi bước là một cache miss theo con trỏ, nên 518 ns đắt hơn nhiều so với cảm giác "chỉ 20 phép so sánh" — phần cứng lại xen vào, đúng như bài học phần 1.
Bài học đo lường: hash table và BST cân bằng đổi cho nhau THỨ TỰ lấy TỐC ĐỘ — hash thắng tra cứu điểm (16,2 vs 518,5 ns = 32x) vì O(1) và cache liền mạch; BST thắng tuyệt đối truy vấn cần thứ tự (range/min/max/duyệt sắp xếp) vì có thứ tự sẵn (7,8 µs) còn hash phải sort O(n log n) (54,2 ms); chọn theo LOẠI truy vấn, không theo Big-O. Nếu tôi tin "hash luôn hơn" và dùng unordered_map cho một bài toán cần range query, tôi đã tự ép mình sort lại toàn bộ dữ liệu mỗi truy vấn — chậm hàng nghìn lần một std::map mà đáng lẽ chọn từ đầu.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: hỏi "tôi có cần thứ tự không?" trước khi chọn. Nếu chỉ tra cứu điểm (có khóa → lấy giá trị), dùng hash (unordered_map, dict, HashMap) — nhanh hơn nhiều. Nếu cần bất kỳ thứ gì liên quan thứ tự — range query, "k phần tử nhỏ nhất", "phần tử kế tiếp lớn hơn x", duyệt theo thứ tự, tìm min/max liên tục — dùng cây (std::map, TreeMap, SortedDict). Đây không phải chuyện tối ưu vi mô; chọn sai làm bạn không thể trả lời truy vấn cần thứ tự mà không sort lại toàn bộ.
Hệ quả thứ hai: nhớ rằng "O(log n)" của cây đắt hơn cảm giác vì cache miss. Ngay cả khi bạn không cần thứ tự nhưng đã lỡ dùng cây, hãy biết mỗi tra cứu là ~20 bước theo con trỏ, mỗi bước có thể miss cache — nên cây chậm hơn hash nhiều hơn tỉ số log n / 1 gợi ý (đo được 32 lần). Nếu tra cứu điểm là điểm nóng và bạn không cần thứ tự, đổi sang hash là một trong những tối ưu dễ và hiệu quả nhất. (Ngược lại, có những cấu trúc cây thân thiện cache hơn như B-tree/B+-tree gom nhiều khóa vào một node để giảm số lần nhảy — đó là lý do cơ sở dữ liệu dùng chúng.)
Hệ quả thứ ba là tinh thần đo lường: so hai cấu trúc phải so trên tập thao tác thật của bạn, không so một con Big-O tách rời. Con số mang theo: hash table (O(1), không thứ tự) vs BST cân bằng (O(log n), có thứ tự) — tra cứu ĐIỂM: hash 16,2 ns vs BST 518,5 ns = hash nhanh 32x (BST mỗi bước con trỏ = cache miss, đắt hơn '20 bước' gợi ý); RANGE QUERY / cần THỨ TỰ: BST 7,8 µs (lower_bound O(log n) + duyệt k, có sẵn) vs hash phải lấy hết + sort O(n log n) = 54,2 ms/lần. Chọn theo bạn cần TRA ĐIỂM (hash) hay THỨ TỰ (cây), không theo O(1) < O(log n). Câu hỏi đúng không phải "cái nào nhanh hơn" mà "bạn cần loại truy vấn nào".
Thử ba mươi giây
Nạp một triệu khóa vào cả std::unordered_map và std::map (hoặc dict và một SortedDict trong Python), rồi đo hai việc. Thứ nhất, tra cứu điểm một triệu lần: hash sẽ nhanh hơn hàng chục lần. Thứ hai, thử "cho tôi mọi khóa trong khoảng [a, b] theo thứ tự": với cây, đó là lower_bound rồi duyệt — vài micro-giây; với hash, bạn sẽ nhận ra mình không có cách nào ngoài việc lôi hết khóa ra và sort, tốn hàng chục mili-giây. Ba mươi giây đó cho bạn thấy điều mà "O(1) < O(log n)" giấu đi: hash và cây không cạnh tranh trên cùng một sân — hash bán tốc độ bằng cách vứt thứ tự, cây giữ thứ tự bằng cách chấp nhận chậm hơn khi tra điểm. Chọn cấu trúc theo câu hỏi bạn sẽ hỏi nó, không theo con số Big-O to hay nhỏ.
