Quá trình Rehashing diễn ra như thế nào khi Hash Table đạt đến ngưỡng Load Factor và tại sao thao tác này có thể gây ra độ trễ đột ngột trong ứng dụng?

Question

Accepted Answer

Quá trình Rehashing diễn ra như thế nào?
Khi số lượng phần tử trong Hash Table vượt quá tích của dung lượng hiện tại nhân với Load Factor ngưỡng (ví dụ: 16 * 0.75 = 12 phần tử), bảng băm sẽ thực hiện tiến trình tự động mở rộng (Resizing & Rehashing):

Cấp phát bộ nhớ mới: Tạo ra một mảng bucket mới với dung lượng lớn hơn gấp đôi mảng cũ (capacity * 2).
Quét lại dữ liệu (Rehashing): Duyệt qua toàn bộ các phần tử có trong mảng cũ, tính toán lại giá trị băm (hash code) dựa trên kích thước mảng mới và chuyển dời chúng vào các vị trí bucket tương ứng trong mảng mới.
Giải phóng: Giải phóng mảng cũ.

Tại sao gây ra độ trễ đột ngột (Latency Spike)?

Thao tác Rehashing đòi hỏi phải duyệt qua toàn bộ N phần tử hiện tại và thực hiện tính toán lại hàm băm.
Độ phức tạp thời gian của một lần Rehash là O(N).
Trong các ứng dụng Enterprise đòi hỏi độ trễ cực thấp (Low-latency, High-frequency trading, Real-time gaming), khi bảng băm đạt kích thước lớn hàng triệu phần tử, tiến trình Rehash này sẽ chặn luồng chính (blocking), gây ra hiện tượng giật lag hoặc độ trễ đột ngột (Stop-the-world / Latency Spike).

Giải pháp tối ưu thực tế

Nếu biết trước số lượng phần tử cần lưu trữ, hãy khởi tạo Hash Table với dung lượng ban đầu (initial capacity) phù hợp để tránh hoàn toàn việc phải resize liên tục.
Sử dụng các cấu trúc dữ liệu hỗ trợ incremental rehashing (băm tăng dần) trong các hệ thống phân tán hoặc các ngôn ngữ lập trình chuyên biệt.

Quá trình Rehashing diễn ra như thế nào khi Hash Table đạt đến ngưỡng Load Factor và tại sao thao tác này có thể gây ra độ trễ đột ngột trong ứng dụng?

Quá trình Rehashing diễn ra như thế nào?

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi hash tables liên quan cùng chủ đề