Hash map O(1) — nhưng có một lần chèn chậm hơn 233.000 lần, và nó không báo trước

Một nhân viên thu ngân trung bình phục vụ mỗi khách trong 30 giây — nghe như hàng lúc nào cũng chạy đều. Nhưng cứ vài chục khách lại có một lần máy tính tiền phải khởi động lại mất năm phút, và đúng người xui xẻo đứng đó lãnh trọn. "Trung bình 30 giây" là thật, mà cũng che mất cú kẹt năm phút. Hash map có đúng cái bẫy con số trung bình ấy. Nó được yêu thích vì một lời hứa gọn gàng: tra cứu và chèn 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, 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 lần chèn chậm hơn thao tác thường hai trăm ba mươi ba 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 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ó (chính là cú "máy tính tiền khởi động lại" ở đầu bài). 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ề đến code hằng ngày

Điều đầ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 (Java có TreeMap, C++ có std::map). Và nếu biết trước số phần tử, hãy dựng bảng với sức chứa đủ lớn ngay từ đầu (new HashMap<>(capacity), make(map, n) trong Go) — bạn xóa sạch các cú spike rehash bằng cách trả tiền một lần lúc dựng.

Điều 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. Đây là chỗ các thứ bạn dùng mỗi ngày lộ ra sự khác biệt: Java HashMap mặc định rehash ở load factor 0.75 và tự trộn thêm bit vào hashCode(); Go map tăng trưởng dần và cũng randomize thứ tự để bạn không lỡ phụ thuộc vào nó; Python dict dùng open addressing như bài này. Cùng bài học lặp lại ở tầng cơ sở dữ liệu: một hash join hay index băm cũng thoái hóa khi khóa phân bố lệch — đó là lý do bộ tối ưu ước lượng số dòng trước khi chọn hash join. Gói lại bằng số: bảng băm O(1) là trung bình khấu hao — latency chèn 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.

Muốn tự thấy thì 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".