Câu hỏi phỏng vấn Big-O và Hash Table

Big-O đo tốc độ tăng trưởng của số bước khi n lớn, không phải thời gian tuyệt đối tính bằng mili giây. Chính xác hơn, nó là chặn trên: T(n) = O(f(n)) nghĩa là tồn tại hằng số c và n0 sao cho với mọi n từ n0 trở đi, T(n) không vượt quá c nhân f(n). Vì thế nó không nói gì về hằng số, về cache miss, hay về hành vi ở n nhỏ — hai đoạn code cùng O(n) vẫn có thể chênh nhau hàng chục lần chỉ vì memory layout. Cách dùng đúng trong công việc: Big-O trả lời "code này scale thế nào", còn profiler trả lời "nó nhanh bao nhiêu ở đây và bây giờ".

Vì ở n đủ lớn, hạng bậc cao nuốt trọn phần còn lại: với T(n) = 3n² + 100n + 5, ở n = 10 hạng 100n còn chiếm 76%, nhưng ở n = 1.000 thì 3n² đã chiếm 97%. Hằng số cũng mờ dần vì nó phản ánh phần cứng chứ không phản ánh cấu trúc: máy nhanh gấp đôi biến hệ số 3 thành 1.5 nhưng bậc vẫn là n². Nói cách khác, tỷ lệ hạng thấp trên hạng cao tiến về 0 khi n tiến ra vô cực, nên giữ chúng lại cũng không đổi được kết luận về khả năng scale. Có mất thông tin, và mất đúng phần mà Big-O cố tình không nhận trách nhiệm: khi hai thuật toán cùng bậc thì hằng số mới là thứ quyết định, lúc đó phải đo chứ không suy từ ký hiệu.

Không, vòng lặp lồng thì nhân độ phức tạp của hai tầng chứ không mặc định ra O(n²). Nếu tầng trong là binary search thì tổng là O(n) nhân O(log n), tức O(n log n); chỉ khi tầng trong duyệt tuyến tính mới ra O(n²). Ngược lại, hai vòng lặp tuần tự thì cộng: O(n) + O(n) = O(2n), rồi bỏ hằng số còn O(n). Quy tắc thực hành là phân tích từng vòng riêng rồi mới ghép — lồng thì nhân, nối tiếp thì cộng rồi bỏ hạng bậc thấp.

O là chặn trên (không tăng nhanh hơn), Ω là chặn dưới (không tăng chậm hơn), Θ là chặn chặt khi cả trên lẫn dưới đều là cùng một hàm. Merge Sort có best case và worst case đều là n log n nên Θ(n log n) là mô tả chính xác; linear search thì best case Ω(1) còn worst case O(n) nên không có Θ đơn giản. Dev dùng O gần như mọi lúc vì kỹ thuật quan tâm worst case — đó mới là con số đặt SLA được. Ngoài ra O an toàn hơn khi cam kết: nói "không tệ hơn O(n log n)" vẫn đúng kể cả khi best case tốt hơn, còn nói Θ là buộc phải chứng minh cả chặn dưới.

Bốn tính chất: deterministic (cùng input luôn cùng output), nhanh cỡ O(1), phân phối đều để không bucket nào thành điểm nóng, và avalanche — đổi 1 bit input thì khoảng 50% bit output đổi theo. Phân phối đều giữ chiều dài mỗi chain là hằng số; avalanche khiến các key "gần nhau" không dồn vào cùng bucket, vì nhiều hash chuỗi có entropy tập trung ở bit cao trong khi bucket index chỉ lấy vài bit thấp. Đó là lý do nhiều Map trộn thêm một bước supplemental hash — XOR h với chính h dịch phải 16 bit — trước khi tính h AND (capacity - 1). Hai thứ hash table KHÔNG cần là one-way và collision-resistant: đó là yêu cầu của hash mật mã như SHA-256, còn ở đây va chạm chỉ cần hiếm là đủ.

Contract bắt buộc là một chiều: nếu a.equals(b) đúng thì a.hashCode() phải bằng b.hashCode(); chiều ngược lại không bắt buộc vì va chạm hash là chuyện bình thường. Map định vị bucket bằng hashCode rồi mới dùng equals để xác nhận đúng key, nên hai object "bằng nhau" mà hash khác nhau sẽ nằm ở hai bucket khác nhau và không bao giờ gặp nhau. Khi override equals mà quên hashCode, object rơi về identity hash gắn với từng instance, nên set.add(u1) rồi set.contains(u2) trả false dù u1.equals(u2) là true. Bug im lặng vì không có exception nào được ném: contains trả false, get trả null, đều là giá trị hợp lệ — test dùng lại đúng một reference vẫn pass, chỉ vỡ khi object được tạo mới từ JSON hoặc database.

O(1) chỉ đúng dưới giả định hàm hash phân phối đều: mỗi bucket chứa số entry là hằng số, không phụ thuộc n. Nếu hàm hash tệ hoặc bị tấn công có chủ đích, cả n key rơi vào cùng một bucket và lookup thoái hoá thành duyệt một chain dài n, đúng O(n). Thư viện hiện đại chặn đáy bằng treeify: bucket có chain dài vượt ngưỡng (từ 8 node trở lên) được chuyển thành cây đỏ-đen, worst case còn O(log n). Cộng thêm resize — khi vượt load factor, bảng phải rehash toàn bộ với chi phí O(n), nhưng vì hiếm nên trung bình mỗi thao tác vẫn là O(1).

Vì O(1) ở đây là amortized: tính tổng chi phí của cả dãy n lần add rồi chia cho n, chứ không phải chi phí của một lần riêng lẻ. Với chiến lược nhân đôi, tổng chi phí sao chép qua mọi lần resize là 1 + 2 + 4 + ... + n/2 — một chuỗi hình học bằng n - 1. Cộng thêm n lần ghi phần tử, tổng dưới 2n; chia cho n ra hằng số 2, tức O(1) mỗi thao tác. Điểm mấu chốt là mỗi lần resize đắt được trả trước bởi rất nhiều lần add rẻ trước đó, nên chi phí đắt bị rải mỏng thay vì cộng dồn.

Không — điều kiện thật sự là predicate đơn điệu: tồn tại một điểm chuyển tiếp sao cho không gian tìm kiếm có dạng [F F F T T T], không có T nào đứng trước F. Mảng sorted chỉ là trường hợp đặc biệt khi predicate là A[i] >= target. Nhờ vậy binary search chạy được cả trên không gian không phải mảng, ví dụ tìm capacity nhỏ nhất để ship hết hàng trong D ngày: capacity lớn hơn thì số ngày cần ít hơn, nên predicate đơn điệu. Đó là pattern search-on-answer, đưa brute force xuống O(N log(hi - lo)) mà không cần dữ liệu sắp xếp sẵn.

Khi n nhỏ và khi memory layout chi phối, vì cả hai đều nằm trong phần hằng số mà ký hiệu Big-O cố tình bỏ đi. Ví dụ thứ nhất: Insertion Sort là O(n²) nhưng in-place và cache-friendly nên với n dưới 32 nó nhanh hơn Merge Sort O(n log n) — chính vì thế TimSort dùng Insertion Sort cho các đoạn nhỏ. Ví dụ thứ hai: duyệt mảng số nguyên và duyệt danh sách liên kết cùng là O(n) nhưng chênh nhau khoảng 25 lần, vì mảng nạp một cache line 64 byte được 16 phần tử và hardware prefetcher đoán trước, còn đuổi theo con trỏ thì mỗi node là một cache miss phải đợi khoảng 100ns. Nguyên tắc: Big-O dự đoán tương đối ở n lớn, còn ở n nhỏ hoặc trong hot path thì phải đo thay vì suy luận từ ký hiệu.

Worst case per operation là chi phí của một lần gọi trong tình huống tệ nhất — với add của mảng động là O(n) đúng lúc resize. Average case là trung bình trên input ngẫu nhiên theo một phân phối giả định, nên giả định sai thì con số vô nghĩa. Amortized là trung bình trên một dãy thao tác xấu nhất liên tiếp, không cần giả định gì về phân phối input — vì thế nó là đảm bảo mạnh hơn average. QuickSort minh hoạ rõ ranh giới: nó có average O(n log n) nhưng không có amortized O(n log n), vì luôn tồn tại dãy input đẩy nó về O(n²). Ngược lại mảng động thực sự có amortized O(1) chứng minh được, còn "amortized O(1)" của hash table thực chất là average case dựa trên giả định hàm hash tốt.

Khi workload ép thao tác đắt xảy ra liên tiếp: cứ insert đến đúng ngưỡng resize rồi remove, rồi insert lại, thì mỗi vòng đều trigger một lần sao chép O(n) mà không tích được đủ "credit" từ các thao tác rẻ. Trường hợp thứ hai không phải sụp đổ về tổng chi phí mà về độ trễ: amortized nói về trung bình, nhưng lần tệ nhất vẫn là O(n) và nó chắc chắn sẽ xảy ra. Với render loop, audio buffer hay hot path nhạy latency, một spike lúc resize là đủ để drop frame hoặc vỡ stream — lúc đó worst case per operation mới là con số phải cam kết. Cách xử lý là pre-allocate với capacity biết trước để loại bỏ resize hoàn toàn; amortized tốt cho throughput, không tốt cho jitter.

Chaining để mỗi bucket trỏ ra một danh sách bên ngoài, còn open addressing đặt toàn bộ entry thẳng trong một mảng duy nhất và khi va chạm thì probe sang ô kế tiếp theo quy tắc linear, quadratic hoặc double hashing. Open addressing thắng về cache locality (một mảng liên tục, thay vì đuổi con trỏ qua các node rải rác trên heap) và tốn ít memory hơn vì không có node object, nhưng buộc load factor phải dưới 1 và delete thì phức tạp vì cần tombstone. Java giữ chaining không phải vì nó vượt trội kỹ thuật, mà vì lý do lịch sử và kiến trúc: thiết kế từ 1998 khi cache chưa là ưu tiên, LinkedHashMap extends HashMap dựa vào node có con trỏ before/after, treeify của Java 8 là biện pháp phòng thủ hợp với chaining, và backward compatibility với Map.Entry. Python, Go và Rust ra đời sau nên ưu tiên cache locality và tận dụng được SIMD — SwissTable mà Rust dùng so sánh 16 control byte trong một instruction.

Load factor là tỷ lệ số entry trên capacity; vượt ngưỡng thì bảng cấp phát mảng lớn hơn và rehash lại toàn bộ, chi phí O(n) nhưng vì hiếm nên amortized vẫn O(1) mỗi thao tác. Chaining chịu được load factor cao hơn (0.75 là mặc định quen thuộc) vì va chạm ở một bucket chỉ kéo dài chain của chính bucket đó, không làm chậm các bucket khác. Open addressing thì bắt buộc dưới 1 — không còn ô trống nào là probe lặp vô hạn — và thực tế giữ dưới 0.7 vì probe length tăng phi tuyến. Theo công thức Knuth cho linear probing, số probe kỳ vọng của một lần tìm hụt là khoảng 2.5 ở load factor 0.5, khoảng 6 ở 0.7 và lên tới khoảng 50 ở 0.9 — vẫn là amortized O(1) về lý thuyết nhưng hằng số lớn tới mức thực tế gần O(n). Ngoài ra open addressing còn tích tụ tombstone sau nhiều lần delete, nên cần rehash định kỳ để dọn chứ không chỉ để mở rộng.

Ba lỗi hay gặp nhất là tràn số ở mid = (lo + hi) / 2, off-by-one do trộn hai convention khoảng, và vòng lặp vô hạn khi gán lo = mid trong khoảng đóng đúng lúc lo bằng hi - 1. Tràn số fix bằng mid = lo + (hi - lo) / 2; đây chính là bug từng sống trong Arrays.binarySearch của JDK suốt 1998 đến 2006 cho tới khi Joshua Bloch phát hiện. Invariant gọn nhất là nửa mở [lo, hi): khởi tạo lo = 0, hi = n, lặp while lo < hi, predicate đúng thì hi = mid, sai thì lo = mid + 1, và khi lo bằng hi thì đó chính là điểm chuyển tiếp. Mỗi nhánh đều thu hẹp khoảng ít nhất 1 nên không có trường hợp đứng yên, và lower bound với upper bound chỉ khác nhau đúng một ký tự so sánh: >= cho lower, > cho upper. Với số thực thì bỏ hẳn điều kiện hội tụ, chạy số vòng lặp cố định khoảng 100 lần để tránh không dừng do float precision.