Phần trước cho thấy một cách hash table chết: để hệ số tải bò lên gần 1, va chạm dồn thành chuỗi dài và tra cứu chậm cả chục lần. Nhưng có một cách chết âm thầm hơn nhiều, xảy ra ngay cả khi tải thấp: dùng một hàm băm xấu. Nếu hàm băm không rải khóa đều khắp các bucket mà dồn chúng vào một góc, thì dù bảng còn rỗng 70%, tra cứu vẫn có thể chậm hàng chục lần — hoặc thoái hóa hoàn toàn về O(n). Tôi giữ nguyên hệ số tải và chỉ đổi hàm băm, đo trong container gcc:13, và con số cho thấy chất lượng hàm băm quyết định O(1) hay thảm họa.
Hàm băm làm gì, và vì sao "xấu" lại chết người
Nhiệm vụ của hàm băm là biến khóa thành chỉ số bucket sao cho các khóa rải đều. "Đều" là chìa khóa: nếu hai khóa khác nhau hay bị đẩy về cùng vùng bucket, chúng va chạm, tạo chuỗi probe dài — đúng cái làm tra cứu chậm.
Hàm băm tốt trộn đều mọi bit của khóa vào kết quả. Ví dụ kinh điển là "murmur finalizer": vài lần xor-shift (k ^= k >> 33) xen với nhân một hằng số lẻ lớn. Kết quả: đổi một bit của khóa làm đổi khoảng nửa số bit của mã băm — nên khóa dù có cấu trúc (id tăng đều, con trỏ căn 16 byte, timestamp bước đều) vẫn rải khắp các bucket.
Hàm băm xấu bỏ qua bước trộn: chỉ lấy vài bit thấp của khóa, hoặc dùng nguyên khóa làm chỉ số (bucket = key % cap). Điều này chết người khi khóa có cấu trúc — mà khóa thực tế gần như luôn có cấu trúc. Nếu mọi khóa là bội số của 1024, thì 10 bit thấp của chúng đều bằng 0; lấy bit thấp làm bucket nghĩa là tất cả dồn vào một phần nhỏ bảng, phần còn lại rỗng không. Bảng "đầy 70%" nhưng khóa chen chúc trong 0,2% số bucket.
Đo: cùng tải, khác hàm băm — chênh 23 lần
Tôi chèn cùng một bộ khóa có cấu trúc (bội số của 1024 — mô phỏng id/con trỏ căn lề) vào cùng một bảng, giữ hệ số tải cố định ở 0,70, chỉ đổi hàm băm:
CÙNG tải 0,70, khóa bội số 1024, chỉ khác HÀM BĂM:
băm TỐT (murmur mix) : probe_tb = 2,17 | 7,7 ns/tra cứu
băm XẤU (lấy bit thấp) : probe_tb = 358,90 | 174,2 ns/tra cứu
-> băm xấu chậm hơn ~23 lần, dù CÙNG hệ số tải
Nhìn kỹ: cùng bảng, cùng số phần tử, cùng tải 0,70. Băm tốt cho 2,17 probe trung bình (7,7 ns) — đúng vùng O(1) rẻ. Băm xấu cho 358,90 probe (174,2 ns) — mỗi tra cứu phải dò trung bình 359 bucket! Chậm hơn ~23 lần, và khác biệt duy nhất là hàm băm. Vì khóa bội số 1024 có bit thấp trùng nhau, băm xấu dồn hết vào vài chuỗi khổng lồ, trong khi phần lớn bảng rỗng. Đây là bằng chứng đanh thép: hệ số tải thấp của phần 4 là điều kiện cần, không đủ — bạn còn phải phân bố đều.
Và trường hợp cực đoan nhất, khi hàm băm trả cùng một giá trị cho mọi khóa:
BỆNH LÝ: băm hằng số (mọi khóa -> cùng bucket), N=20.000, tải chỉ 0,3:
probe_tb = 10.000 (=~N/2) | 4.822,7 ns/tra cứu -> O(n)
Mọi khóa dồn vào một chuỗi probe dài N phần tử; tra cứu trung bình quét N/2 = 10.000 bucket. Hash table đã thoái hóa hoàn toàn thành O(n) — không hơn gì duyệt một linked list, dù tải chỉ 0,3. "Cấu trúc O(1)" biến thành cấu trúc O(n) chỉ vì hàm băm.
Chi phí tính hàm băm — có đáng không?
Băm tốt làm nhiều phép tính hơn (xor-shift + nhân). Có đáng bỏ CPU đó không? Tôi đo riêng chi phí tính hàm băm, không đụng bảng:
Tính hàm băm 50 triệu lần:
băm TỐT (murmur, 3 nhân + 3 xor) : 0,42 ns/lần
băm XẤU (identity, trả nguyên khóa) : ~0 ns/lần
Băm tốt tốn 0,42 ns mỗi lần tính, băm xấu gần như miễn phí. Nhưng nhìn lại phần A: băm tốt tiết kiệm 356 probe mỗi tra cứu, mà mỗi probe (đọc một bucket, có thể là cache miss) đắt hơn 0,42 ns nhiều. Đổi 0,42 ns lấy việc cắt hàng trăm probe là món hời gần như luôn đáng. Đây là đánh đổi cần cân, nhưng cán cân nghiêng hẳn về phía băm tốt trừ những trường hợp cực hiếm (khóa đã ngẫu nhiên sẵn, hoặc băm nằm trong vòng lặp siêu nóng mà va chạm vốn đã ít).
Một lần tôi đo hớ: "hash table nào cũng O(1)"
Tôi vào đo với niềm tin đã ăn sâu: "cứ là hash table thì O(1)". Đo phá tan: ở cùng hệ số tải 0,70, chỉ đổi hàm băm tốt sang xấu, tra cứu chậm 23 lần (2,17 → 358,9 probe); và với băm hằng số, nó thành O(n) đầy đủ. "O(1)" của hash table không đến từ cái tên hash table — nó đến từ hàm băm phân bố đều cộng tải thấp. Thiếu hàm băm tốt, bạn có một cái tên "hash map" với hiệu năng của một linked list. Còn niềm tin ngược "băm càng phức tạp càng tốt" cũng cần chỉnh: băm tốt tốn CPU (0,42 ns/lần), nên với dữ liệu đã ngẫu nhiên hoặc vòng lặp cực nóng, một hàm băm vừa đủ tốt mà rẻ có thể thắng — phải cân chi phí tính với số va chạm tiết kiệm.
Bài học đo lường: O(1) của hash table phụ thuộc CẢ hệ số tải thấp LẪN hàm băm phân bố đều — cùng tải 0,70, băm xấu (dồn cụm khóa có cấu trúc) cho 358 probe (chậm 23x) và băm hằng số thoái hóa về O(n); tải thấp là điều kiện cần, không đủ. Nếu tôi tin "hash table nào cũng O(1)" và viết một hàm băm cẩu thả (hay để hashCode() mặc định trả identity cho khóa có cấu trúc), tôi đã tạo ra một cấu trúc chậm dần bí ẩn — profiler chỉ vào "một tra cứu map" trông vô tội, trong khi thủ phạm là hàm băm dồn cụm mà tôi không ngờ tới.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: dùng hàm băm của thư viện chuẩn, đừng tự chế cẩu thả. std::hash, hashCode() của Java cho kiểu chuẩn, hash() của Python đều đã trộn bit cẩn thận. Chỗ dễ sai là khi bạn tự viết hàm băm cho kiểu của mình (struct, khóa ghép): nếu chỉ return a.id hay cộng vài trường, và các trường đó có cấu trúc (id liên tiếp, con trỏ căn lề), bạn dựng ngay một hàm băm dồn cụm. Luôn trộn (xor-shift + nhân, hoặc kết hợp qua một hàm có sẵn như boost::hash_combine).
Hệ quả thứ hai: cảnh giác với khóa "có cấu trúc" — chúng là bẫy của hàm băm xấu. Id tự tăng, con trỏ, timestamp, chuỗi có tiền tố chung: đây là dữ liệu thực tế điển hình, và chính là loại khóa mà hàm băm identity/bit-thấp xử lý tệ nhất. Một hàm băm tốt biến cấu trúc thành nhiễu đều; một hàm băm xấu để cấu trúc đó dồn khóa lại. Nếu hash map của bạn chậm bất thường mà tải vẫn thấp, hãy nghi ngờ phân bố băm trước tiên.
Hệ quả thứ ba là tinh thần đo lường: "O(1)" là kết quả của điều kiện, không phải thuộc tính của cái tên. Con số mang theo: hiệu năng hash table phụ thuộc CẢ tải LẪN chất lượng hàm băm — cùng tải 0,70, băm tốt (murmur mix) 2,17 probe/7,7 ns vs băm xấu (lấy bit thấp, khóa bội số 1024) 358,9 probe/174 ns = chậm 23x; băm hằng số thoái hóa về O(n) (10.000 probe = N/2, như linked list). Băm tốt tốn 0,42 ns/lần tính nhưng cắt 356 probe -> gần như luôn đáng. Tự viết hàm băm phải TRỘN bit (xor-shift + nhân); cảnh giác khóa có cấu trúc. Tải thấp là điều kiện cần; hàm băm phân bố đều mới cho O(1) thật.
Thử ba mươi giây
Cài một hash table nhỏ (open addressing), rồi thử hai hàm băm trên cùng bộ khóa và cùng mức đầy: một hàm trộn bit tử tế (xor-shift rồi nhân một số lẻ lớn), một hàm chỉ lấy key % cap. Cho khóa là bội số của một lũy thừa 2 (ví dụ mọi khóa chia hết cho 256 — giống id căn lề) và đếm số lần dò trung bình khi tra cứu. Bạn sẽ thấy hàm trộn bit cho ~1–2 lần dò, còn hàm % cap cho hàng trăm — cùng bảng, cùng tải, chỉ khác cách băm. Rồi thử hàm băm trả hằng số và xem nó thoái hóa thành quét tuyến tính. Ba mươi giây đó cho bạn thấy điều mà "hash table là O(1)" giấu đi: O(1) không nằm trong cái tên cấu trúc, mà nằm trong hàm băm rải khóa đều thế nào — và một hàm băm cẩu thả biến map thành list mà không một dòng lỗi nào báo cho bạn.
