Cùng tải 0,70, đổi hàm băm: hash table chậm đi 23 lần

Hình dung một phòng gửi đồ nghìn tủ khóa, và cách chia tủ cho khách là dựa trên số thẻ của họ. Nếu bạn trộn thật kỹ con số ấy trước khi chọn tủ, khách rải đều khắp phòng — ai cũng có tủ riêng, lấy đồ tức thì. Nhưng nếu bạn chỉ lấy hai chữ số cuối của thẻ làm số tủ, mà thẻ lại phát theo lô nên phần lớn cùng đuôi, thì cả trăm người chen vào một dãy tủ trong khi 70% phòng bỏ trống — muốn lấy đồ phải dò từng tủ trong dãy đông nghịt. Cùng số khách, cùng số tủ, chỉ khác cách chọn tủ. Đó chính là chuyện hàm băm tốt và hàm băm xấu trong một hash table.

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. Đây là "trộn kỹ số thẻ trước khi chọn tủ".

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 — đúng cái dãy tủ đông nghịt.

Đ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 đầu: 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ôi trường đo: container gcc:13 trên host ARM AArch64, g++ -O2, open addressing, mỗi số lấy MIN sau warmup. Con số đổi theo máy và mẫu khóa; cái cần nhìn là cùng tải mà băm xấu dồn cụm khóa-có-cấu-trúc thành chuỗi dài.)

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

Tôi vào đo với niềm tin đã ăn sâu: "cứ là hash table thì O(1)". Con số 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.

Nhưng 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. Chỉ là trong hầu hết trường hợp thực tế, cán cân nghiêng hẳn về phía trộn-cho-kỹ.

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

Điều đầ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).

Điều 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.

Chỗ này lịch sử ngôn ngữ có những bài học đắt giá đáng biết. Java HashMap từng dễ bị dồn cụm với khóa có bit thấp giống nhau, nên nó thêm một bước "trộn lại" (h ^= h >>> 16) trên hashCode() của bạn, và từ Java 8, một bucket quá dài tự chuyển từ linked list sang cây đỏ-đen để chặn thoái hóa O(n) — đúng phòng bị đúng cái đo được ở đây. Nghiêm trọng hơn, "hash flooding" từng là một lỗ hổng bảo mật thật: kẻ tấn công gửi các khóa cố tình đụng cùng bucket để biến web server thành O(n) và làm nghẽn (DoS) — nên các ngôn ngữ hiện đại (Python, Rust HashMap mặc định dùng SipHash) băm có khóa ngẫu nhiên mỗi lần chạy để không ai đoán được cách gây đụng. Còn database thì khi phân mảnh (sharding) theo hash, một hàm băm xấu làm dữ liệu dồn về vài node — cùng bài toán "rải đều hay dồn cụm", phóng to lên cả cụm máy.

Muốn tự thấy thì 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. Vài phút đó 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.