Bảng băm (hash map, unordered_map, dict) là câu trả lời mặc định cho "tra cứu nhanh": ai cũng thuộc "hash table là O(1)". Nó băm khóa thành chỉ số bucket rồi nhảy thẳng tới đó — không quét, không so sánh cả mảng. Nhưng "O(1)" ấy có một điều kiện âm thầm mà ít người nói ra, và khi tôi đo, điều kiện đó lộ ra là sống còn: đẩy bảng gần đầy thì tra cứu chậm đi cả chục lần, dù vẫn là "cùng một hash table". Tôi tự cài một bảng băm (open addressing, linear probing) trong container gcc:13 và đo tra cứu theo hệ số tải — con số cho thấy O(1) là một lời hứa có điều kiện.
Hệ số tải, va chạm, và chuỗi probe
Hệ số tải (load factor) = số phần tử / số bucket. Tải 0,5 nghĩa là bảng đầy một nửa. Đây là con số quyết định hiệu năng hash table.
Va chạm xảy ra khi hai khóa băm về cùng một bucket — không tránh được, vì bạn nén không gian khóa khổng lồ vào số bucket hữu hạn. Cách xử lý tôi đo là linear probing (dò tuyến tính): nếu bucket đã có người, dò bucket kế tiếp, kế tiếp nữa, tới khi thấy chỗ trống. Số lần dò đó gọi là probe. Khi bảng còn rỗng, hầu như mỗi khóa vào thẳng bucket của nó — 1 probe. Khi bảng gần đầy, các chuỗi probe dính vào nhau thành cụm dài (primary clustering), và một khóa có thể phải dò hàng chục bucket mới tìm thấy.
Lý thuyết cho công thức tra cứu thành công của linear probing: probe_tb ≈ ½(1 + 1/(1 − tải)). Tải 0,5 → 1,5 probe; tải 0,9 → 5,5; tải 0,99 → 50,5. Nghĩa là chi phí không tăng tuyến tính theo tải — nó phát nổ khi tải tiến gần 1. Tôi đo để xem thực tế có khớp không.
Đo: probe nổ khi bảng gần đầy
Tôi chèn khóa vào bảng 1.048.576 bucket tới các mức tải khác nhau, rồi tra cứu một mẫu khóa lấy đều trên toàn bộ khóa đã chèn (gồm cả khóa vào muộn — những khóa có chuỗi probe dài nhất), đếm probe trung bình và bấm giờ:
A. TRA CỨU HIT trung bình theo HỆ SỐ TẢI (linear probing), 1.048.576 bucket:
tải probe_tb ns/tra cứu
0,25 1,17 3,2
0,50 1,50 5,5
0,75 2,50 8,7
0,90 5,49 12,4
0,95 10,73 15,8
0,99 43,09 33,4 (!)
Nhìn cột probe_tb: ở tải 0,25, mỗi tra cứu chỉ ~1,17 lần dò — gần như O(1) thuần, nhảy thẳng tới nơi. Nhưng khi tải bò lên 0,99, probe trung bình nổ lên 43,09 — mỗi tra cứu phải dò trung bình 43 bucket! Và con số đo khớp lý thuyết đẹp đến kinh ngạc: ở tải 0,75, công thức cho 2,5 và tôi đo đúng 2,50; ở tải 0,9, công thức cho 5,5 và tôi đo 5,49. Thời gian đi theo: 3,2 ns ở tải thấp lên 33,4 ns ở tải 0,99 — chậm hơn ~10 lần, dù vẫn là cùng cấu trúc, cùng phần cứng, chỉ khác mức đầy.
Đây là điểm mấu chốt: "O(1)" của hash table là O(1) trung bình, với điều kiện hệ số tải được giữ thấp. Bỏ điều kiện đó — để bảng gần đầy — thì va chạm và clustering biến tra cứu thành thứ chậm dần không giới hạn. O(1) không phải phép màu vô điều kiện; nó là phần thưởng cho việc giữ bảng thưa.
Rehash: cái giá để ở lại vùng O(1)
Vậy làm sao giữ tải thấp khi số phần tử cứ tăng? Rehash: khi tải vượt ngưỡng (thường 0,75), cấp một bảng gấp đôi số bucket và băm lại mọi phần tử sang bảng mới. Tôi đo riêng chi phí này:
B. REHASH (cấp bảng gấp đôi + băm lại mọi phần tử):
rehash 786.432 phần tử: 0,0035 s = 4,5 ns/phần tử (một lần)
Rehash là O(n) — phải sờ tới từng phần tử. Nhưng nó hiếm khi xảy ra (chỉ khi bảng tăng gấp đôi), nên chi phí đó amortize vào các lần chèn sau — y hệt cơ chế nhân đôi capacity của vector ở phần 2: một vài thao tác đắt O(n) chia đều cho rất nhiều thao tác rẻ, cho ra O(1) trung bình mỗi chèn. Đây là lý do unordered_map/dict tự động rehash khi bạn thêm phần tử — nó âm thầm giữ tải trong vùng rẻ để "O(1)" tiếp tục đúng.
Và để thấy vì sao ta chịu chi phí đó, so hash table (tải kiểm soát) với tìm tuyến tính trong mảng:
C. TRA CỨU N=100.000 phần tử:
hash table : 1,4 ns/tra cứu (tải ~0,38, ~1 probe)
tìm tuyến tính : 236 ns/tra cứu (quét ~N/2)
-> hash nhanh hơn ~169 lần
Ở tải thấp, hash table nhanh hơn quét mảng 169 lần — đó là toàn bộ lý do nó tồn tại. Nhưng con số 169 đó chỉ có được nhờ giữ tải thấp; ở tải 0,99, khoảng cách này co lại đáng kể.
Một lần tôi đo hớ: "hash table luôn O(1)"
Tôi vào đo với câu thần chú thuộc lòng: "hash table là O(1), chấm hết". Đo phá tan sự tự tin đó: cùng một bảng, tra cứu ngốn từ 3,2 ns (tải 0,25) tới 33,4 ns (tải 0,99) — chậm 10 lần, với probe trung bình nhảy từ 1,17 lên 43. "O(1)" là O(1) trung bình khi tải được kiểm soát; nó không nói gì về trường hợp bảng gần đầy, nơi va chạm dồn thành chuỗi dài và mỗi tra cứu quét hàng chục bucket. Còn một niềm tin ngược cũng sai và tôi từng có: "giữ bảng thật đầy để tiết kiệm RAM (ít bucket trống)". Sai — tải cao giết hiệu năng theo cấp số, và cái giá vài chục phần trăm RAM tiết kiệm được không đáng so với tra cứu chậm 10 lần.
Bài học đo lường: "hash table O(1)" là trung bình CÓ ĐIỀU KIỆN — điều kiện là hệ số tải thấp; tải tiến gần 1 thì va chạm và clustering làm số probe nổ (1,17 → 43) và tra cứu chậm nhiều lần, nên phải rehash (O(n) một lần, amortize) để giữ tải ~0,5–0,75. Nếu tôi tin "luôn O(1)" và tắt/nới rehash để tiết kiệm bộ nhớ, tôi đã tạo ra một cấu trúc chậm dần khó hiểu khi dữ liệu lớn — profiler chỉ vào "một tra cứu hash" trông vô tội, trong khi thủ phạm là hệ số tải tôi để trôi lên gần 1.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: để thư viện tự rehash — đừng ép hash table chạy ở tải cao. unordered_map, dict, HashMap đều có ngưỡng tải mặc định (~0,7–0,75) và tự cấp lại; đó là thiết kế đúng, đừng chỉnh cho đầy hơn để "tiết kiệm RAM". Nếu bạn biết trước số phần tử, hãy reserve/khởi tạo đủ bucket ngay — vừa tránh nhiều lần rehash (giống reserve của vector), vừa giữ tải thấp từ đầu.
Hệ quả thứ hai: một hàm băm tốt và tải thấp quan trọng ngang nhau. Đo trên cho thấy ngay cả hàm băm phân bố đều, tải cao vẫn giết hiệu năng vì clustering; ngược lại, hàm băm dở (nhiều khóa dồn về ít bucket) làm probe nổ ngay cả ở tải thấp. Cả hai yếu tố cùng quyết định bạn có thực sự ở vùng O(1) hay không. Với open addressing, bố cục liền mạch còn cho cache locality tốt — probe kế tiếp thường cùng cache line — nên nó thường nhanh hơn separate chaining (mỗi bucket là một linked list rải rác) ở tải vừa phải.
Hệ quả thứ ba là tinh thần đo lường: đọc Big-O cùng điều kiện của nó, và đo ở đúng chế độ vận hành. Con số mang theo: hash table O(1) là TRUNG BÌNH khi hệ số tải thấp: tra cứu 1,17 probe/3,2 ns ở tải 0,25, nhưng tải 0,99 thì probe trung bình nổ lên 43,09 và 33,4 ns (~10x chậm) do va chạm + primary clustering — khớp công thức ½(1+1/(1−tải)). Phải REHASH (cấp bảng gấp đôi, băm lại = O(n) một lần, đo 4,5 ns/phần tử, amortize như vector mọc) để giữ tải ~0,5–0,75. Ở tải thấp hash nhanh hơn tìm tuyến tính 169x (1,4 vs 236 ns). Đừng để bảng gần đầy để "tiết kiệm RAM". O(1) là phần thưởng có điều kiện, không phải bảo đảm.
Thử ba mươi giây
Tự cài một hash table đơn giản (open addressing, linear probing) với số bucket cố định, rồi chèn phần tử tới các mức đầy khác nhau — 50%, 90%, 99% — và với mỗi mức, đếm số lần dò trung bình khi tra cứu. Bạn sẽ thấy ở 50% mỗi tra cứu chỉ ~1,5 lần dò, nhưng ở 99% con số vọt lên hàng chục — cùng một bảng, chỉ khác mức đầy. Rồi thử để bảng gần đầy và đo thời gian tra cứu so với khi bảng thưa: nó chậm đi cả chục lần. Ba mươi giây đó cho bạn thấy điều mà câu "hash table O(1)" giấu đi: chữ O(1) đi kèm một điều kiện — giữ nó thưa — và rehash chính là cái giá âm thầm bạn trả để điều kiện đó luôn đúng. Biết điều kiện của một Big-O quan trọng ngang biết chính Big-O đó.
