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 Big-O nói về tiệm cận — hành vi khi n tiến tới vô cùng — và nó cố tình bỏ qua hằng số. Ở n nhỏ, chính cái 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 vào câu hỏi: 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 kiện 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).
-
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.
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.
Một lần tôi đo hớ: "hash map O(1) luôn nhanh nhất" và "mảng quét O(n) luôn chậm hơn"
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ĩ". Đo phá tan 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 đo cũng phá luôn niềm tin ngược — cái mà người vừa học được bài trên dễ mắc: "vậy mảng quét lúc nào cũng nhanh hơn hash cho tập nhỏ". 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.
Bài học đo lường: Big-O là TIỆM CẬN (n→∞) và bỏ qua hằng số — ở n NHỎ hằng số quyết định. Đo khóa CHUỖI 24 ký tự: mảng quét tuyến tính (O(n)) thắng unordered_map (O(1)) tới n≈16 (mảng cache liền, so sánh thoát sớm, không băm/con trỏ; hash phải băm cả chuỗi ~10 ns + theo con trỏ tới node rải rác), điểm giao n≈16–32; từ n=32 hash phẳng ~14 ns thắng mảng (tăng tới 168 ns ở n=256). Điểm giao TÙY giá khóa: khóa int (băm ~miễn phí) hash thắng cả n=4. Nếu tôi tin "hash luôn nhanh nhất" tôi phức tạp hóa các tra cứu nhỏ; nếu tin "mảng nhỏ luôn thắng" tôi để O(n) leo thang khi n lớn.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầ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.
Hệ quả 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.
Hệ quả thứ ba là tinh thần đo lường: Big-O trả lời "quy mô lớn", không trả lời "nhanh ở n của tôi" — hằng số bị giấu mới quyết định điểm giao. Con số mang theo: mảng quét tuyến tính O(n) thắng hash O(1) khi n nhỏ VÀ khóa đắt để băm (khóa chuỗi 24 ký tự: mảng thắng tới n≈16, điểm giao n≈16–32); khóa rẻ (int) hash thắng cả n=4. Big-O bỏ qua hằng số; ở n nhỏ hằng số (băm, con trỏ, cache) quyết định. Đo ở đúng n và kiểu khóa. "Big-O tốt hơn" không đồng nghĩa "nhanh hơn ở đây".
Thử ba mươi giây
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 bạn 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ỏ.
