Ở bài trước ta mổ bảng băm ra và thấy khi hàm băm dồn cụm, chuỗi probe dài ra và tra cứu tụt từ O(1) về gần O(n). Bài đó đo tác hại của một hàm băm tồi. Bài này quay vào chính hàm băm: điều gì làm một hàm băm tốt? Câu trả lời quen tai là "rải đều" — nhưng còn một vế thứ hai ít ai đo: hàm băm chạy mỗi lần tra hay chèn, nên nó phải tính nhanh nữa. Hai yêu cầu này kéo về hai hướng, và tôi đã vào bài với một thiên kiến sai về chúng.
Hàm băm cân hai thứ đối nhau
Một hàm băm nhận khóa (số, chuỗi, con trỏ) và trả về một số nguyên, rồi bảng lấy số đó chia lấy dư cho số bucket để chọn ô. Nó phải làm tốt hai việc cùng lúc:
- Phân bố: rải khóa đều khắp các bucket, ít va chạm. Rải càng đều, chuỗi probe càng ngắn, tra cứu càng gần O(1). Đây là điều bài trước đã đo mặt trái.
- Tốc độ: tính ra giá trị băm càng nhanh càng tốt, vì hàm băm chạy mỗi lần đụng bảng. Một hàm băm rải hoàn hảo nhưng tính chậm có thể đắt hơn cả cái nó tiết kiệm được.
Có ba mức hàm băm, đứng ở ba chỗ khác nhau trên trục cân bằng này. Quá đơn giản (identity — lấy nguyên khóa làm giá trị băm; hay modulo trần): tính cực nhanh, gần như không tốn gì, nhưng với khóa có mẫu thì rải rất tệ. Trộn bit (FNV, murmur-style): xáo các bit của khóa bằng vài phép nhân và dịch, nhanh gần bằng identity mà rải đều. Mật mã (SHA-256): rải hoàn hảo và chống được cả kẻ cố tình gây va chạm, nhưng tính đắt hơn hẳn. Câu hỏi là: cái giá và cái lợi của mỗi mức là bao nhiêu? Tôi đo.
Đo: tốc độ tính và độ đều phân bố
Tôi viết một chương trình C (biên dịch gcc -O2) băm một triệu khóa bằng bốn hàm, đo hai thứ: thời gian tính trung bình mỗi khóa (nano giây), và độ đều phân bố vào một bảng B = 2^20 bucket. Để đo độ đều tôi dùng chi-square chia B: với phân bố ngẫu nhiên lý tưởng con số này quanh 1.0; càng lớn hơn 1 nghĩa là càng dồn cụm. Kèm theo là max bucket — bucket đông khóa nhất, con số quyết định chuỗi probe dài nhất.
Điểm mấu chốt của phép đo: tôi cố tình dùng khóa có mẫu — dãy i * 4096 (bội số của 4096, mô phỏng con trỏ căn lề theo trang, hay id cấp phát theo khối, rất thường gặp trong thực tế). Đây là chỗ hàm băm bộc lộ bản chất.
Tốc độ tính (ns mỗi khóa):
identity : 0,77 ns
mix(bit) : 0,72 ns
FNV-1a : 2,57 ns
SHA-256 : 184,15 ns
Độ đều phân bố trên khóa có mẫu (lý tưởng: max ~8, chi-square/B ~1):
| Hàm băm | max bucket | chi-square/B | Nhận xét |
|---|---|---|---|
| identity | 3907 | 3905 | thảm họa |
| FNV-1a | 3 | 0,57 | rất đều |
| mix (bit) | 8 | 1,00 | lý tưởng |
| SHA-256 | 8 | 1,00 | lý tưởng |
Hai bảng này gộp lại kể một câu chuyện gọn: identity nhanh nhất để tính nhưng phân bố sụp đổ; SHA rải hoàn hảo nhưng tính chậm gấp 240 lần; và ở giữa có một hàm vừa nhanh vừa đều. Trước khi chỉ ra nó, phải nói về cú hớ của tôi.
Một lần tôi đo hớ: nhanh nhất không phải tốt nhất
Tôi vào bài với niềm tin thẳng thừng: hàm băm chạy mỗi lần tra, nên hàm băm nhanh nhất cho bảng nhanh nhất — cứ chọn identity, tốn 0,77ns, khỏi phải trộn bit làm gì. Nghe rất hợp lý, và với khóa ngẫu nhiên nó còn đúng.
Nhưng khóa thật hiếm khi ngẫu nhiên. Khi tôi đưa vào dãy i * 4096, identity dồn cả triệu khóa vào đúng 256 bucket: max bucket 3907, gần 100% số bucket còn lại trống trơn, chi-square/B lên 3905 — tức lệch phân bố lý tưởng gần bốn nghìn lần. Lý do lộ ngay khi nhìn số học: identity lấy nguyên khóa, rồi bảng chia dư cho 2^20. Mà i * 4096 = i * 2^12, nên phần dư khi chia 2^20 chỉ phụ thuộc 8 bit thấp của i — đúng 256 giá trị. Mọi bit "thông tin" của khóa nằm ở các bit cao đều bị phép chia dư ném đi. Bảng băm với hàm này, như bài trước đã đo, thoái hóa về danh sách: tra cứu O(n). Hàm băm "nhanh nhất" của tôi tạo ra bảng chậm nhất.
Cú hớ này có một người anh em sinh đôi ở đầu kia. Nếu identity quá liều lĩnh, sao không chọn SHA-256 "cho an toàn" — nó rải hoàn hảo, chống được cả tấn công va chạm cố ý? Đo ra: SHA cho phân bố y hệt hàm trộn bit (cả hai max 8, chi-square 1,00) — không đều hơn một chút nào cho mục đích bảng băm — nhưng tính mất 184ns mỗi khóa, gấp 240 lần hàm trộn bit. Với nhiều bảng băm, băm một khóa bằng SHA còn đắt hơn cả thao tác tra cứu mà nó phục vụ. Tôi suýt trả cái giá 240 lần để đổi lấy đúng con số không.
Người thắng nằm chính giữa: hàm trộn bit (ở đây là bộ trộn cuối của murmur3 — vài phép nhân với hằng số lớn xen kẽ phép dịch–XOR). Nó tính 0,72ns — nhanh ngang identity, thậm chí nhỉnh hơn trong lần đo này — mà rải hoàn hảo (max 8, chi-square 1,00) ngay trên khóa có mẫu, vì mỗi phép trộn kéo thông tin từ bit cao xuống trộn với bit thấp, nên phần dư không còn bỏ sót bit nào. FNV-1a cũng rất tốt (max 3, chi-square 0,57), chỉ chậm hơn chút (2,57ns). Bài học đo được: hàm băm tốt không phải hàm nhanh nhất, cũng không phải hàm mạnh nhất, mà là hàm cân bằng đúng cho dữ liệu của bạn — và với khóa thật (thường có mẫu), một chút trộn bit gần như miễn phí nhưng cứu cả phân bố.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: đừng dùng identity/modulo trần làm hàm băm cho khóa số thật. Nó cám dỗ vì đơn giản và nhanh, và nó sẽ qua được mọi test bạn viết bằng khóa ngẫu nhiên. Rồi production đưa vào id tuần tự, con trỏ căn lề, timestamp cách đều — tất cả đều "có mẫu" theo nghĩa vài bit lặp lại — và bảng dồn cụm, tra cứu chậm dần mà không có lỗi nào nổ ra. Nhiều thư viện chuẩn (Java HashMap, Go map) vì thế tự trộn thêm bit vào giá trị hashCode() bạn cung cấp, đúng để chống lại đúng cái bẫy này. Biết vậy thì đừng chống lại nó bằng một hàm băm tự chế quá ngây thơ.
Hệ quả thứ hai: chọn mức hàm băm theo mối đe dọa, không theo cảm giác an toàn. SHA và các hàm băm mật mã có chỗ của chúng — khi khóa đến từ đối thủ có thể cố tình chế khóa cùng bucket để tấn công (hash-flooding, một dạng từ chối dịch vụ). Lúc đó cái giá 240 lần là đáng, hoặc dùng SipHash (hàm băm có khóa bí mật, rẻ hơn SHA nhiều mà vẫn chống tấn công — đó là lý do Python và Rust dùng nó cho bảng băm mặc định). Nhưng nếu khóa của bạn là dữ liệu nội bộ không có đối thủ, trả giá mật mã chỉ để "cho chắc" là đốt CPU vô ích cho một phân bố không tốt hơn hàm trộn bit rẻ tiền.
Hệ quả thứ ba là bài học đo lường bao trùm: "nhanh" của một thành phần vô nghĩa cho tới khi hỏi nó làm hệ thống nhanh hay chậm. Identity là hàm băm nhanh nhất khi đo cô lập, và là hàm băm tệ nhất khi đo trong bảng thật với khóa thật — cùng một hàm, hai kết luận trái ngược, chỉ khác ở chỗ ta đo cái gì. Con số mang theo: với khóa có mẫu, identity dồn 1 triệu khóa vào 256 bucket (max 3907, chi-square 3905) dù tính chỉ 0,77ns; SHA rải hoàn hảo (max 8) nhưng tính 184ns — gấp 240 lần; hàm trộn bit murmur đạt cùng phân bố hoàn hảo với 0,72ns, và đó là lựa chọn đúng. Đo hàm băm phải đo cả hai trục — tốc độ tính lẫn độ đều phân bố — và đo trên khóa giống dữ liệu thật, không phải khóa ngẫu nhiên tô hồng.
Thử ba mươi giây
Lấy loại khóa bạn thật sự bỏ vào bảng băm — id tăng dần, con trỏ, đường dẫn file, timestamp — và hỏi: các bit thấp của chúng có thay đổi đều không? Nếu khóa của bạn là bội số của một lũy thừa 2 (con trỏ căn lề 8 hay 16 byte, id cấp theo khối), thì vài bit thấp nhất luôn bằng 0, và một hàm băm chỉ nhìn bit thấp (identity + modulo lũy thừa 2) sẽ dồn cụm — đúng cái bài này đo. Cách thử nhanh trong đầu: viết ra bốn năm khóa điển hình dưới dạng nhị phân, che đi các bit cao, xem phần còn lại có trùng nhau nhiều không. Trùng nhiều nghĩa là bạn cần trộn bit trước khi chia dư. Và nếu đang định với tay lấy SHA "cho chắc", hỏi ngược: khóa của mình có đến từ đối thủ không? Không, thì một hàm trộn bit rẻ tiền cho bạn đúng cùng độ đều mà không phải trả cái giá mật mã.
