Khi mảng quét O(n) đánh bại hash map O(1)

Bài học Big-O in sâu vào mọi lập trình viên: O(1) đánh bại O(log n) đánh bại O(n). Nên phản xạ tự nhiên khi cần tra cứu là "dùng hash map, nó O(1)".

Nhưng nghĩ tới chuyện tìm một cái tên. Nếu danh sách chỉ có năm người, bạn liếc từ trên xuống là thấy ngay — nhanh hơn cả việc lật một cuốn danh bạ dày có vần A-Z, vì mở danh bạ, dò tới đúng vần, lần theo cột cũng mất mấy giây. Nhưng nếu danh sách có năm nghìn người thì ngược lại: liếc tay mỏi mắt, còn danh bạ vẫn chỉ mất mấy giây như cũ. Big-O nói về cái danh sách năm nghìn người — hành vi khi n tiến tới vô cùng — và nó cố tình bỏ qua hằng số, tức cái công "mở danh bạ" cố định kia. Ở n nhỏ, chính hằng số bị bỏ qua đó mới quyết định, và một cấu trúc O(n) "tệ hơn về lý thuyết" có thể nhanh hơn thật. Suốt sê-ri này ta đã gặp nhiều điểm giao; phần này đo thẳng: khi nào một mảng quét tuyến tính đánh bại một hash map? Tôi đo trong container gcc:13, và con số cho thấy điểm giao — cùng một điều làm nó dịch chuyển.

Quét mảng liền so với băm khóa và theo con trỏ

Hai cách tra cứu một khóa trong một tập nhỏ:

• Mảng phẳng + quét tuyến tính (O(n)): giữ các khóa trong một mảng liền, quét từ đầu tới khi khớp. Về Big-O là O(n) — tệ. Nhưng hằng số rất nhỏ: không băm, không con trỏ, không cấp phát; dữ liệu liền mạch nên n nhỏ nằm gọn trong 1–2 cache line, quét cực nhanh và CPU đoán nhánh tốt; so sánh thường thoát sớm (khác ở ký tự đầu là dừng). Đây là "liếc danh sách năm người".

• Hash map (O(1)): về Big-O là hằng số. Nhưng mỗi tra cứu phải: băm khóa (với chuỗi, băm = đọc cả chuỗi, ~10 ns), rồi theo con trỏ tới node rải rác trên heap (cache miss), rồi so khóa. Hằng số đó lớn hơn nhiều một phép so sánh trong mảng — là cái công "mở danh bạ".

Câu hỏi đo lường: hằng số nhỏ của mảng bù được cho O(n) tới n bằng bao nhiêu?

Đo: mảng thắng tới n≈16, và điểm giao tùy giá của khóa

Tôi tìm một khóa (có mặt) trong tập n phần tử, 10 triệu truy vấn, với khóa chuỗi 24 ký tự — so quét tuyến tính mảng với unordered_map:

Tìm 1 khóa chuỗi (24 ký tự), 10 triệu truy vấn, g++ -O2:

    n   | mảng quét tuyến tính (O(n)) | unordered_map (O(1))
   -----|-----------------------------|----------------------
     4  |    10,1 ns                  |   10,9 ns    (MẢNG thắng)
     8  |    13,3 ns                  |   13,8 ns    (MẢNG thắng)
    16  |    18,3 ns                  |   18,9 ns    (MẢNG thắng, sát)
    32  |    28,6 ns                  |   12,6 ns    (map thắng)
    64  |    48,3 ns                  |   12,2 ns    (map thắng)
   256  |   168,6 ns                  |   14,0 ns    (map thắng)
   -> điểm giao ở n ≈ 16–32

Nhìn các dòng n = 4, 8, 16: mảng quét tuyến tính thắng hash map (10,1 vs 10,9; 13,3 vs 13,8; 18,3 vs 18,9 ns). Với ≤16 chuỗi, quét cả mảng — mỗi phép so thoát sớm ở ký tự đầu, dữ liệu liền trong cache — vẫn nhanh hơn (hoặc ngang) việc băm cả một chuỗi 24 byte rồi theo con trỏ tới node. Cái O(n) "tệ" ở đây rẻ hơn cái O(1) "tốt".

Nhìn từ n = 32 trở lên: hash map thắng, và khoảng cách giãn nhanh. Thời gian của map giữ gần như hằng số (~12–14 ns bất kể n), còn mảng tăng tuyến tính (từ 10 lên 168 ns khi n từ 4 lên 256). Đây đúng là O(n) so với O(1): ở n lớn, tiệm cận thắng, mảng thua đậm. Điểm giao rơi vào khoảng n ≈ 16–32.

Còn một điều tôi đo được (và suýt nhầm) làm rõ tại sao: điểm giao phụ thuộc giá của khóa. Khi tôi đo cùng thí nghiệm với khóa int, hash map thắng ngay cả ở n = 4 (1,6 ns so với mảng 6,9 ns) — vì băm một int gần như miễn phí (một phép nhân), nên hằng số của hash cực nhỏ, mảng không kịp thắng. Với khóa chuỗi, băm đắt (đọc cả chuỗi), nên mảng thắng ở n nhỏ. Cùng một cấu trúc, điểm giao dịch chuyển hoàn toàn theo chi phí băm/so sánh khóa.

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

Tôi vào đo với phản xạ Big-O: "cần tra cứu à? Hash map, O(1), nhanh nhất, khỏi nghĩ". Con số bác ngay cho khóa chuỗi: quét tuyến tính một mảng ≤16 chuỗi thắng unordered_map, vì hằng số của hash (băm cả chuỗi + theo con trỏ tới node rải rác + cache miss) lớn hơn nhiều một loạt phép so thoát sớm trên dữ liệu liền cache. Big-O bỏ qua hằng số, và ở n nhỏ hằng số là tất cả. Với một tập tra cứu nhỏ và cố định (vài chục mục cấu hình, một handful lựa chọn), một mảng phẳng thường nhanh hơn và đơn giản hơn một hash map.

Nhưng nếu vừa học được điều đó rồi vội tin "vậy mảng quét lúc nào cũng nhanh hơn hash cho tập nhỏ" thì lại sai. Chỉ đúng tới điểm giao. Từ n ≈ 32 trở lên, mảng tăng tuyến tính (168 ns ở n=256) trong khi hash phẳng (~14 ns) — hash thắng rõ và càng lúc càng xa. Và điểm giao không cố định: với khóa int (băm ~miễn phí), hash thắng cả n=4; mảng quét O(n) chỉ thắng khi cả n nhỏ và khóa đắt để băm. Không có câu trả lời tuyệt đối; có một điểm giao phụ thuộc n và giá khóa.

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

Việc đầu tiên: cho tập tra cứu nhỏ và cố định, một mảng phẳng thường là lựa chọn đúng — đơn giản và nhanh. Vài chục mục cấu hình, một bảng lựa chọn, các trường của một struct nhỏ — quét tuyến tính một mảng (hoặc một std::vector cặp khóa-giá trị) không cần băm, không cấp phát, nằm gọn trong cache, và với n nhỏ nhanh ngang hoặc hơn hash map. Đừng phản xạ unordered_map cho mọi tra cứu; với n nhỏ nó là phức tạp thừa.

Việc thứ hai: biết điểm giao của bạn — nó phụ thuộc n và giá của khóa. Khóa rẻ để băm (int, con trỏ) → hash thắng gần như luôn, dùng hash. Khóa đắt (chuỗi dài, cấu trúc) và n nhỏ → mảng quét thắng. Nếu không chắc, đo ở đúng n và đúng kiểu khóa của bạn — đừng suy từ Big-O. Và nhớ: khi n sẽ lớn dần, hãy chọn cấu trúc thắng ở quy mô đích, không phải quy mô hiện tại.

Điều thú vị là những người viết trình biên dịch và thư viện đã đo đúng bài này và hành động theo nó, dù bạn không thấy. Trình biên dịch C/C++ khi gặp một switch nhỏ thường sinh chuỗi so sánh tuyến tính, chỉ chuyển sang bảng nhảy (jump table, kiểu O(1)) khi số nhánh đủ lớn — đúng logic điểm giao. Nhiều triển khai HashMap hiện đại lưu vài entry đầu dạng mảng phẳng và chỉ "nâng cấp" lên cấu trúc băm/cây khi map lớn lên; các thư viện có small_vector/flat_map (Boost, Abseil flat_hash_map) tồn tại chính vì mảng liền thắng ở quy mô nhỏ. Ngay cả bộ tối ưu database cũng chọn nested-loop join (giống quét tuyến tính) cho bảng nhỏ và chỉ dựng hash join khi số hàng lớn — cùng một quyết định điểm-giao ở quy mô truy vấn. Nguyên tắc chung: Big-O trả lời "quy mô lớn", không trả lời "nhanh ở n của tôi" — và ở n nhỏ, hằng số bị giấu mới cầm trịch.

Muốn tự thấy thì tạo một mảng nhỏ vài phần tử (khóa là chuỗi, ví dụ tên) và một unordered_map cùng dữ liệu. Viết hai hàm tra cứu: một quét tuyến tính mảng (so sánh tới khi khớp), một gọi map.find. Bấm giờ hàng triệu truy vấn với n = 4, 8, 16, 32, 64, 256. Bạn sẽ thấy ở n nhỏ mảng nhanh ngang hoặc hơn map (vì map phải băm cả chuỗi rồi theo con trỏ), rồi có một điểm mà map vượt lên và bỏ xa khi n lớn — thời gian map gần như phẳng, còn mảng tăng tuyến tính. Rồi đổi khóa sang int và đo lại: lần này map thắng ngay cả ở n=4, vì băm một int gần như miễn phí. Ba mươi giây đó cho thấy điều mà "hash map O(1) nên nhanh nhất" giấu đi: Big-O nói về khi n rất lớn, còn ở n nhỏ chính hằng số — chi phí băm, con trỏ, cache — quyết định ai thắng, và một mảng phẳng "tệ về lý thuyết" thường là câu trả lời nhanh và giản dị nhất cho một tập nhỏ.