Hash Collision (Xung đột mã băm) là gì trong Hash Tables và các kỹ thuật phổ biến nào được các ngôn ngữ lập trình hiện đại sử dụng để giải quyết vấn đề này?

Question

Accepted Answer

1. Bản chất Hash Collision
Hash Collision xảy ra khi hàm băm (Hash Function) ánh xạ hai khóa (keys) khác nhau vào cùng một vị trí (index) trong bảng băm. Do không gian khóa là vô hạn trong khi kích thước mảng băm là hữu hạn, xung đột là điều chắc chắn xảy ra theo nguyên lý chuồng bồ câu.
2. Các kỹ thuật giải quyết phổ biến

Chaining (Nối kết riêng phần): Mỗi ô trong mảng băm chứa một cấu trúc dữ liệu phụ, thường là Linked List hoặc Red-Black Tree. Khi xảy ra xung đột, phần tử mới sẽ được nối tiếp vào danh sách tại ô đó.
Open Addressing (Định địa chỉ mở):
Linear Probing: Khi ô bị chiếm, tìm kiếm tuần tự ô trống tiếp theo (index + 1, index + 2...).
Quadratic Probing: Tìm kiếm theo bước nhảy bậc hai (index + 1^2, index + 2^2...).
Double Hashing: Sử dụng hàm băm thứ hai để tính bước nhảy khi xảy ra xung đột.

3. Giải pháp trong Enterprise
Phần lớn các ngôn ngữ Enterprise hiện đại (như Java với HashMap từ phiên bản 8 trở lên) sử dụng kết hợp Chaining với Linked List, nhưng khi số lượng phần tử trong một bucket vượt ngưỡng (ví dụ 8 phần tử), Linked List sẽ tự động chuyển đổi thành Red-Black Tree để giảm độ phức tạp tìm kiếm từ O(N) xuống O(log N), ngăn chặn các cuộc tấn công khai thác lỗ hổng Hash DoS.

Hash Collision (Xung đột mã băm) là gì trong Hash Tables và các kỹ thuật phổ biến nào được các ngôn ngữ lập trình hiện đại sử dụng để giải quyết vấn đề này?

1. Bản chất Hash Collision

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 data structures liên quan cùng chủ đề