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 ý. Cách quen thuộc — cách std::unordered_map dùng — là chaining (nối chuỗi): mỗi bucket là một danh sách liên kết các phần tử va chạm. Cách kia là open addressing (tập mở, probing): mọi phần tử nằm trong chính mảng, va chạm thì dò sang ô kế tiếp. 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ớ chonextcộ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.
Một lần tôi đo hớ: "chaining là chuẩn nên nhanh nhất" và "open addressing luôn nhanh hơn"
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". Đo phá tan: 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 đo cũng phá luôn niềm tin ngược mà tôi suýt rơi vào: "vậy open addressing luôn nhanh hơn, cứ dùng nó". 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.
Bài học đo lường: hai cách xử lý va chạm — CHAINING (chuỗi node rải rác, như unordered_map) vs OPEN ADDRESSING (dò trong mảng liền): open nhanh hơn ở tải vừa nhờ cache (0,5: 10,4 vs 15,1 ns; 0,7: 15,0 vs 18,3 ns) và gọn hơn ~3,4x bộ nhớ (36 vs 122 MB); NHƯNG ở tải cao 0,9 open dò dồn cụm (TB 5,45 dò) chậm hẳn (26,8 ns) và chaining (21,0 ns) VƯỢT lên — điểm giao. Bảng băm nhanh (Abseil, Google) dùng open + giữ tải thấp. Nếu tôi tin "chaining là chuẩn nên nhanh nhất" tôi bỏ lỡ một tối ưu cache; nếu tôi tin "open luôn nhanh hơn" tôi để nó gần đầy và clustering giết hiệu năng.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầ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.
Hệ quả 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.
Hệ quả thứ ba là tinh thần đo lường: cùng một Big-O (O(1) trung bình), hai chiến lược cho hằng số rất khác nhau, và ai thắng đổi theo hệ số tải. Con số mang theo: open addressing (mảng liền) nhanh hơn chaining ở tải vừa nhờ cache (0,5: 10,4 vs 15,1 ns) và gọn ~3,4x (36 vs 122 MB); nhưng ở tải cao 0,9 dò dồn cụm (5,45 dò) làm open (26,8 ns) chậm hơn chaining (21,0 ns) — điểm giao. Giữ tải thấp để open thắng; chaining ổn định hơn khi đầy và cho tham chiếu ổn định. Hệ số tải không chỉ ảnh hưởng "có va chạm hay không" — nó quyết định chiến lược nào nên dùng.
Thử ba mươi giây
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 bạn 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.
