Hash table O(1) — cho tới khi bạn để nó đầy 99%

Hình dung một bãi đỗ xe. Khi bãi mới đầy một phần tư, bạn lái thẳng vào ô của mình, đỗ cái xong. Nhưng khi bãi đầy 99%, ô của bạn đã có người, bạn phải chạy sang ô kế, rồi ô kế nữa, vòng vèo mãi mới tìm được chỗ trống — và càng đầy càng lâu, không phải chậm đi một chút mà chậm theo cấp số. Một hash table với linear probing hành xử đúng như vậy: "ô đỗ" là bucket, "chạy sang ô kế" là mỗi lần probe, và "bãi đầy bao nhiêu" chính là hệ số tải — con số quyết định cái "O(1)" mà ai cũng thuộc lòng có thật hay không.

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 — bãi đỗ đầy 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 — đúng cảnh chạy sang ô kế. 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ãi còn nhiều chỗ trống.

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 — xây một bãi đỗ lớn gấp đôi rồi dời mọi xe sang. 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ôi trường đo: container gcc:13 trên host ARM AArch64, g++ -O2, open addressing/linear probing, 1.048.576 bucket, mỗi số lấy MIN sau warmup. Con số đổi theo máy; cái cần nhìn là probe khớp công thức ½(1+1/(1−tải)) và nổ khi tải → 1.)

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

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". Con số 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.

Nhưng có một niềm tin ngược cũng sai, mà 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 đỗ chật cứng nhìn thì "hiệu quả", nhưng ai vào cũng phải vòng vèo cả buổi.

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

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

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

Chỗ này biết cách các nền tảng thật xử lý rất đáng. Java HashMap mặc định ngưỡng tải 0,75 và tăng gấp đôi bucket khi vượt — đúng con số trong bài; và cho constructor nhận initialCapacity để bạn nạp sẵn, tránh rehash lặp lại. Go thì map tự tăng khi tải trung bình vượt ~6,5 phần tử/bucket (nó dùng bucket chứa nhiều slot), và make(map[K]V, n) gợi ý kích thước. Python dict giữ tải dưới 2/3 và tăng gấp bốn (với dict nhỏ) khi đầy. Ở tầng database, cùng nguyên lý áp cho hash index và hash join — engine theo dõi tải và tràn sang đĩa (spill) khi hash table không vừa RAM, vì để nó "đầy quá" cũng làm truy vấn thoái hóa. Mọi nơi, "giữ bãi còn chỗ" là luật ngầm để hash tiếp tục nhanh.

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