Mọi bảng băm phải xử lý va chạm — khi hai khóa khác nhau băm về cùng một ô. Có hai cách kinh điển, và cách bạn chọn quyết định bảng băm nhanh hay chậm hơn nhiều so với những gì Big-O gợi ý.

Hình dung một bãi đỗ xe. Cách chaining: mỗi vị trí có một sợi dây xích, xe nào trùng chỗ thì móc nối đuôi nhau thành một hàng kéo dài ra ngoài — tìm xe của mình phải lần theo cả sợi xích. Cách open addressing: không có xích, xe nào tới thấy chỗ đã đầy thì chạy sang ô trống kế tiếp mà đỗ — tìm xe thì dò tuần tự từ vị trí "đúng ra phải ở đó". std::unordered_map dùng cách xích (chaining): mỗi bucket là một danh sách liên kết. Cách kia — open addressing (probing) — nhét mọi phần tử vào chính mảng, va chạm thì dò ô kế. Nhiều người mặc định "chaining là cách chuẩn nên nhanh nhất". Tôi đo cả hai trong container gcc:13 ở nhiều hệ số tải, và con số cho thấy một điểm giao — không có câu trả lời duy nhất.

Chuỗi con trỏ rải rác so với dò trong mảng liền

Hai chiến lược xử lý va chạm khác nhau ở nơi cất phần tử va chạm:

  • Chaining (như std::unordered_map): mỗi bucket giữ một danh sách liên kết. Va chạm → thêm một node vào chuỗi của bucket đó. Mỗi node được cấp riêng trên heap và nối bằng con trỏ next. Ưu: đơn giản, tải cao vẫn hoạt động (chuỗi chỉ dài ra). Nhược: mỗi bước đi trong chuỗi là một con trỏ tới node rải rác → cache miss, và mỗi node tốn thêm bộ nhớ cho next cộng chi phí cấp phát.

  • Open addressing (linear probing): mọi phần tử nằm trong chính mảng. Va chạm → dò ô kế tiếp (i, i+1, i+2, …) tới khi gặp ô trống thì đặt vào đó; tra cứu cũng dò như vậy tới khi gặp khóa hoặc ô trống. Ưu: mảng liền mạch, cache tốt, không con trỏ next, không cấp phát lẻ. Nhược: khi bảng gần đầy, các ô bị dồn cụm (clustering) → chuỗi dò dài ra nhanh.

Điểm mấu chốt: chaining phân tán dữ liệu ra heap (mềm dẻo, cache kém); open addressing dồn dữ liệu vào một mảng (cache tốt, nhưng nhạy với hệ số tải).

Đo: open thắng ở tải vừa, chaining vượt ở tải cao

Tôi đo tra cứu thành công trên bảng 4,19 triệu ô, ở ba hệ số tải, cộng bộ nhớ:

CAP = 4,19 triệu ô, tra 10 triệu lần (thành công), g++ -O2:

   tải | open addressing        | chaining
  -----|------------------------|----------
   0,5 | 10,4 ns (TB 1,50 dò)   | 15,1 ns
   0,7 | 15,0 ns (TB 2,17 dò)   | 18,3 ns
   0,9 | 26,8 ns (TB 5,45 dò)   | 21,0 ns   <- điểm giao, chaining vượt lên

BỘ NHỚ (tải 0,7, N=2,94 triệu):
   open addressing (mảng key+val+cờ) : 36 MB
   chaining (bucket + 2,94tr node)   : 122 MB   (node + con trỏ next)
   -> open gọn hơn ~3,4 lần

Nhìn cột hệ số tải thấp: ở 0,5, open addressing tra một khóa mất 10,4 ns (trung bình chỉ 1,5 lần dò), còn chaining mất 15,1 ns — open nhanh hơn ~45%. Toàn bộ khác biệt là cache: open đọc các ô liền nhau trong một mảng, còn chaining phải theo con trỏ tới các node rải rác. Ở 0,7, open (15,0 ns, 2,17 dò) vẫn nhanh hơn chaining (18,3 ns).

Nhưng nhìn dòng 0,9 — đây là điểm giao: khi bảng đầy 90%, open addressing phải dò trung bình 5,45 lần mỗi tra cứu vì các cụm đã dồn lại (clustering), và thời gian vọt lên 26,8 ns — chậm hơn chaining (21,0 ns). Chaining ổn định hơn ở tải cao vì thêm một phần tử chỉ làm một chuỗi dài thêm một node, không gây dồn cụm lan rộng như linear probing. Đúng một điểm giao như phần tìm nhị phân vs tuyến tính: cái nào thắng phụ thuộc điều kiện, ở đây là hệ số tải.

Nhìn bộ nhớ: open addressing dùng 36 MB, chaining 122 MB — open gọn hơn ~3,4 lần. Vì open chỉ là ba mảng phẳng (khóa, giá trị, cờ dùng/trống), không con trỏ next, không cấp phát từng node; còn chaining trả một malloc cộng một con trỏ 8 byte cho mỗi phần tử. Đây là lý do các bảng băm gọn quan tâm hệ số tải để đổi lấy dung lượng.

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

Tôi vào đo với một mặc định: "std::unordered_map dùng chaining, đó là cách chuẩn của thư viện, nên chaining chắc là nhanh nhất". Con số bác ngay: open addressing (dò trong một mảng liền) tra cứu nhanh hơn ở hệ số tải vừa (10,4 vs 15,1 ns ở 0,5) nhờ cache liền và không con trỏ, đồng thời gọn hơn 3,4 lần bộ nhớ. Không phải ngẫu nhiên mà các bảng băm hiệu năng cao (Abseil flat_hash_map, Google dense_hash_map, bảng băm trong nhiều ngôn ngữ hiện đại) dùng open addressing chứ không phải chaining. "Cách chuẩn của thư viện" không đồng nghĩa với "nhanh nhất" — unordered_map chọn chaining vì ràng buộc chuẩn C++ (giữ tham chiếu ổn định), không phải vì tốc độ.

Nhưng nếu vì thế mà nhảy sang "vậy open addressing luôn nhanh hơn, cứ dùng nó" thì cũng sai. Ở hệ số tải cao (0,9), linear probing bị dồn cụm — trung bình 5,45 lần dò mỗi tra cứu — khiến open (26,8 ns) chậm hơn chaining (21,0 ns). Open addressing chỉ nhanh khi bảng không quá đầy; nó đòi bạn giữ hệ số tải thấp và resize sớm. Nếu để nó gần đầy, clustering ăn hết lợi thế cache. Chaining chịu tải cao "duyên dáng" hơn — sợi xích dài thêm một mắt, không làm cả bãi xe tắc.

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

Việc đầu tiên: khi cần bảng băm nhanh và bạn kiểm soát được cài đặt, cân nhắc open addressing với hệ số tải thấp. Cho các bảng đọc nhiều, khóa nhỏ (số, chuỗi ngắn), open addressing thường nhanh hơn std::unordered_map đáng kể nhờ cache liền — đó là lý do có absl::flat_hash_map, robin_hood, ankerl::unordered_dense. Nếu bạn dùng chúng, nhớ đặt ngưỡng resize ở tải vừa (0,5–0,75), không để bảng gần đầy.

Việc thứ hai: chọn theo hệ số tải và ràng buộc, không theo mặc định. Nếu bạn phải dùng std::unordered_map (cần tham chiếu/con trỏ tới phần tử ổn định khi bảng resize — điều open addressing không đảm bảo vì nó dời phần tử), thì chaining là đúng. Nếu bảng thường xuyên gần đầy và bạn không resize được, chaining chịu tải cao tốt hơn. Nếu bạn cần gọn bộ nhớ và nhanh ở tải vừa, open addressing thắng. Ba tình huống, ba lựa chọn.

Cái điểm-giao và lựa-chọn này không phải chuyện riêng của C++ — nó là quyết định thiết kế của gần như mọi runtime hiện đại. Bảng băm mặc định của Go dùng một biến thể chaining theo bucket (tối ưu cache hơn danh sách liên kết thuần); nhưng làn sóng gần đây nghiêng hẳn về open addressing với các mẹo chống clustering: Python 3.6+ đổi dict sang bố cục compact + open addressing (vừa gọn vừa giữ thứ tự chèn), Rust dùng hashbrown (bản SwissTable của Abseil, open addressing + SIMD dò song song), và chính SwissTable là lý do các bảng này thắng chaining cả ở tải cao — chúng dò nhiều ô một lúc bằng một lệnh SIMD. Nói cách khác, "clustering ở tải cao" là bài toán giải được bằng kỹ thuật dò tốt hơn, và ngành đã chọn open addressing làm mặc định mới. Nguyên tắc chung: cùng O(1) trung bình, hằng số do chiến lược va chạm + hệ số tải + bố cục cache quyết định, và mặc định của thư viện cũ không phải chân lý.

Muốn tự thấy thì cài hai bảng băm cho khóa số nguyên: một open addressing (ba mảng phẳng — khóa, giá trị, cờ dùng/trống — va chạm thì i = (i+1) & mask), và một chaining (mảng bucket, mỗi bucket một danh sách liên kết node cấp bằng malloc). Nạp cùng số phần tử vào cùng số ô để đạt hệ số tải 0,5, rồi bấm giờ vài triệu lần tra cứu: open addressing sẽ nhanh hơn vì nó đọc các ô liền nhau thay vì nhảy theo con trỏ. Rồi tăng tải lên 0,9 và đo lại — bạn sẽ thấy open addressing chậm lại rõ rệt (đếm số lần dò trung bình, nó vọt lên vì clustering) trong khi chaining nhích lên nhẹ nhàng, và có một điểm mà chaining vượt qua. Cuối cùng, so bộ nhớ hai bảng: open addressing gọn hơn nhiều vì không có con trỏ next và không cấp phát từng node. Ba mươi giây đó cho thấy điều mà "chaining là cách chuẩn nên nhanh nhất" giấu đi: cách xử lý va chạm và hệ số tải cùng quyết định tốc độ, và cấu trúc mặc định của thư viện không phải lúc nào cũng là cấu trúc nhanh nhất.