Bảng băm (hash map) là cấu trúc dữ liệu được yêu thích vì một lời hứa gọn gàng: tra cứu và chèn trong O(1) — thời gian hằng số, không phụ thuộc số phần tử. Đúng như bài mở sê-ri nhắc, một ký hiệu big-O đẹp không kể hết câu chuyện; và với bảng băm, cái chữ nhỏ "trung bình" trước "O(1)" giấu ba chi phí mà tôi chỉ thấy khi đo tận từng thao tác. Một trong số đó là một thao tác chèn chậm hơn thao tác thường hai trăm ba mươi nghìn lần.
Ba chi phí ẩn sau chữ "trung bình"
"O(1) trung bình" nghĩa là tính bình quân trên nhiều thao tác, với giả định mọi thứ lý tưởng. Ba điều phá vỡ lý tưởng đó. Một, hệ số tải (load factor — tỉ lệ ô đã dùng): bảng càng đầy, các khóa băm vào cùng vùng càng phải dò (probe) qua nhiều ô để tìm chỗ, nên tra chậm dần. Hai, rehash: khi bảng gần đầy, nó phải cấp một bảng lớn gấp đôi và băm lại toàn bộ phần tử cũ — một thao tác O(n) núp trong một lần chèn tưởng như O(1). Ba, hàm băm: cả O(1) dựa trên giả định hàm băm rải khóa đều; một hàm băm tồi dồn khóa vào ít ô, biến bảng thành một danh sách dài. Tôi đo cả ba bằng C, tự cài một bảng băm địa chỉ mở (open addressing, dò tuyến tính) — kiểu lưu tất cả khóa ngay trong một mảng liền mạch và khi đụng độ thì dò sang ô kế tiếp. Cách này thân thiện cache hơn kiểu móc xích (mỗi ô một danh sách liên kết rải rác), nên nó đã là lựa chọn tốt; các chi phí ẩn dưới đây là cố hữu của bảng băm, không phải do cài kém.
Một lần tôi đo hớ: một lần chèn 9.8 mili giây
Tôi chèn 2 triệu khóa vào bảng, và thay vì chỉ đo tổng thời gian, tôi ghi latency của từng lần chèn — để xem chúng có đều không. Kết quả lật đổ niềm tin "O(1) nên mọi lần đều nhanh như nhau":
chèn 2 triệu phần tử, latency mỗi lần:
trung vị : 42 ns
p99.9 : 333 ns
max (lần rehash) : 9.8 mili giây (233.000 lần trung vị!)
Đại đa số lần chèn tốn 42 nano giây. Nhưng có một lần tốn 9.8 mili giây — đúng lần bảng chạm ngưỡng đầy, phải cấp bảng gấp đôi và băm lại cả 2 triệu phần tử đang có. Một thao tác duy nhất, cùng lời gọi put(), chậm hơn thao tác thường hai trăm ba mươi ba nghìn lần. Cái sai của tôi là tin "O(1)" và tưởng latency phẳng lì. Thực ra O(1) ở đây là khấu hao (amortized): tổng chi phí chia đều thì nhỏ, nhưng chi phí tức thời của một thao tác đơn lẻ có thể vọt lên khủng khiếp. Nếu bạn có yêu cầu về độ trễ đuôi — một hệ thống thời gian thực, một API hứa p99 thấp — cú spike rehash đó là kẻ thù, và nó không hề xuất hiện trong ký hiệu "O(1)".
Load factor: O(1) với hằng số phình dần
Chi phí ẩn thứ hai hiện ra khi đo tra cứu ở các độ đầy khác nhau. Tôi xây bảng ở hệ số tải cố định rồi đo thời gian tra trung bình một khóa có thật:
tra cứu theo load factor:
0.50 -> 6.45 ns
0.90 -> 12.9 ns
0.95 -> 16.2 ns
0.99 -> 26.2 ns
Từ nửa đầy tới gần đầy, tra chậm đi hơn bốn lần. Vẫn là "O(1)" — thời gian không phụ thuộc số phần tử — nhưng cái hằng số ẩn trong O(1) phình dần theo độ đầy, vì bảng càng đầy thì chuỗi dò càng dài. Đây là lý do các bảng băm thật giữ hệ số tải dưới một ngưỡng (thường 0.7-0.75) bằng cách rehash sớm: đổi lấy vài cú spike rehash để giữ tra cứu luôn nhanh. Nói cách khác, hai chi phí ẩn đầu tiên đánh đổi lẫn nhau — muốn tra nhanh (load factor thấp) thì phải rehash thường xuyên hơn (nhiều spike hơn); muốn ít spike thì phải chịu bảng đầy hơn và tra chậm hơn. Không có cấu hình nào tối ưu cho mọi tải, và cách duy nhất biết mình đang ở đâu là đo.
Hàm băm xấu: O(1) thoái hóa thành O(n)
Chi phí ẩn thứ ba là nghiêm trọng nhất. Cả O(1) dựa trên giả định hàm băm rải khóa đều khắp bảng. Tôi so một hàm băm tốt (trộn bit kỹ) với một hàm băm tồi (dồn khóa vào một nhúm ô), đo số ô phải dò trung bình cho mỗi lần tra ở cùng hệ số tải 0.7:
hàm băm tốt : 2.2 ô dò mỗi lần tra
hàm băm xấu : 5707 ô dò mỗi lần tra (2600 lần)
Với hàm băm tốt, mỗi tra chỉ dò trung bình hơn hai ô. Với hàm băm tồi, khóa dồn thành một cụm khổng lồ, và mỗi tra phải quét trung bình 5707 ô — bảng băm đã thoái hóa thành một cuộc quét tuyến tính, đúng như tìm tuyến tính trên một mảng dài mà ta đo ở bài trước, chỉ khác là ta tưởng mình đang dùng O(1). Đây là cách một hash map "O(1)" trở thành O(n) trong thực tế: không phải vì thuật toán sai, mà vì hàm băm không rải đều. Đó cũng là lý do không bao giờ nên tin dữ liệu đầu vào là "ngẫu nhiên đủ tốt"; kẻ tấn công cố tình tạo khóa đụng độ có thể biến dịch vụ của bạn thành O(n) (một dạng tấn công từ chối dịch vụ).
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: hiểu "O(1)" của bảng băm cho đúng — nó là trung bình khấu hao với giả định hàm băm tốt, không phải một đảm bảo mỗi thao tác. Với thông lượng trung bình, bảng băm tuyệt vời. Nhưng nếu bạn cần độ trễ đuôi ổn định (không có cú spike bất chợt), một cây cân bằng O(log n) — chậm hơn trung bình nhưng không bao giờ rehash cả bảng — có thể là lựa chọn đúng hơn.
Hệ quả thứ hai: hàm băm và hệ số tải là những núm chỉnh thật, không phải chi tiết bỏ qua được. Con số mang theo: bảng băm O(1) là trung bình khấu hao: latency chèn có trung vị 42ns nhưng spike tới 9.8ms ở lần rehash (233.000 lần); tra chậm dần theo load factor (6.45ns ở 0.5 lên 26.2ns ở 0.99); và hàm băm xấu đẩy số ô dò từ 2.2 lên 5707, biến O(1) thành O(n). Trước khi tin một bảng băm "luôn O(1)", hỏi: hàm băm có rải đều không, hệ số tải bao nhiêu, và bạn có chịu được một cú spike rehash không.
Thử ba mươi giây
Nếu ngôn ngữ của bạn cho phép, hãy nạp một triệu phần tử vào một hash map và đo thời gian từng lần thêm thay vì tổng — bạn sẽ thấy đa số lần rất nhanh, xen kẽ vài lần chậm vọt đúng ở các mốc bảng phải lớn lên (thường là các lũy thừa của 2). Vẽ chúng ra và bạn có một biểu đồ răng cưa: nền phẳng của các thao tác O(1) thường, cắt ngang bởi những cột spike của các lần rehash O(n). Ba mươi giây nhìn cái răng cưa đó dạy bạn nhiều về chữ "khấu hao" hơn bất kỳ định nghĩa nào — và nhắc bạn rằng "trung bình nhanh" không có nghĩa "luôn nhanh".
