Hash nhanh hơn cây 32 lần — nhưng thua 7000 lần ở range query

Hình dung hai kiểu quầy giữ đồ. Kiểu thứ nhất: bạn đưa phiếu số, nhân viên nhảy thẳng tới đúng móc — tức thì, nhưng áo được treo theo thứ tự ngẫu nhiên theo số phiếu. Kiểu thứ hai: áo treo theo thứ tự bảng chữ cái tên chủ — tìm một cái mất vài bước lần theo, nhưng nếu ai hỏi "cho tôi mọi áo của người tên A đến C" thì chỉ việc quét một đoạn liền. Kiểu thứ nhất là bảng băm (hash table), kiểu thứ hai là cây tìm kiếm nhị phân có thứ tự — và chúng đổi cho nhau đúng cái mà kiểu kia có.

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). Đây là quầy áo treo theo số phiếu.

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. Đây là quầy áo treo theo bảng chữ cá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ôi trường đo: container gcc:13 trên host ARM AArch64, g++ -O2, 1 triệu phần tử, mỗi số lấy MIN sau warmup. Con số đổi theo máy; cái cần nhìn là hash thắng tra điểm còn cây thắng mọi truy vấn cần thứ tự — hai sân khác nhau.)

Hai niềm tin đối nghịch, cùng sai

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". Con số 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 một niềm tin phụ cũng thiếu: "cây O(log n) chậm chỉ vì phải đi 20 bước so sánh". Không hẳn — mỗi bước là một cú nhảy theo con trỏ tới node rải rác, một cache miss, nên 518 ns đắt hơn nhiều so với cảm giác "20 phép so sánh". Phần cứng lại xen vào, đúng như bài học phần 1: số bước trên giấy không bằng số lần chạm bộ nhớ thật.

Về đến code hằng ngày

Điều đầ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ộ.

Điều 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 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.

Điều này lý giải luôn một quyết định thiết kế lớn ở nhiều ngôn ngữ và database. Java có cả hai và đặt tên rõ: HashMap (không thứ tự, nhanh) và TreeMap (đỏ-đen, có thứ tự, cho firstKey/subMap/headMap); C++ tách unordered_map và map; Python dict (hash) và sortedcontainers.SortedDict. Và ở tầng database, đây chính là lý do có hai loại chỉ mục: hash index cho tra cứu bằng (WHERE id = ?) và B-tree index cho truy vấn khoảng và sắp xếp (WHERE age BETWEEN ..., ORDER BY) — Postgres cho bạn chọn USING hash hay USING btree đúng theo bài này, và B-tree là mặc định vì nó phục vụ được cả hai (tra điểm và khoảng), chỉ chậm hơn hash một chút ở tra điểm. Nhận ra "truy vấn của mình có cần khoảng/thứ tự không" là lúc chọn đúng loại chỉ mục.

Muốn tự thấy thì 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. Vài phút đó 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ỏ.