Hiện tượng Hash Collision (Xung đột băm) xảy ra khi nào và các chiến lược giải quyết xung đột phổ biến nào thường được áp dụng trong Hash Table?

Question

Accepted Answer

Hiện tượng Hash Collision là gì?
Hash Collision xảy ra khi hàm băm (Hash Function) tạo ra cùng một giá trị chỉ số (index) cho hai Key khác nhau. Vì kích thước mảng của Hash Table là hữu hạn trong khi tập hợp các Key có thể rất lớn (hoặc vô hạn theo nguyên lý chuồng bồ câu - Pigeonhole Principle), xung đột là điều chắc chắn sẽ xảy ra trong các hệ thống thực tế.
Các chiến lược giải quyết xung đột phổ biến

Separate Chaining (Định địa chỉ mở rộng bằng danh sách liên kết):

Mỗi bucket trong mảng không lưu trực tiếp một giá trị mà lưu phần đầu của một Linked List (hoặc Tree trong Java 8+ HashMap).
Khi xảy ra xung đột, phần tử mới sẽ được nối tiếp vào danh sách tại bucket đó.
Ưu điểm: Dễ cài đặt, không sợ tràn bảng khi vượt quá kích thước.
Nhược điểm: Tốn thêm bộ nhớ cho con trỏ, hiệu năng giảm nếu danh sách quá dài.

Open Addressing (Địa chỉ mở):

Tất cả dữ liệu được lưu trực tiếp bên trong mảng bucket.
Khi xảy ra xung đột, thuật toán sẽ tìm kiếm một ô trống khác trong mảng theo các phương pháp dò tìm:
Linear Probing: Dò tìm tuần tự sang ô tiếp theo (index + 1, index + 2,...).
Quadratic Probing: Dò tì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.

Ưu điểm: Tiết kiệm bộ nhớ do không dùng con trỏ phụ.
Nhược điểm: Dễ xảy ra hiện tượng gom tụ (clustering), việc xóa phần tử phức tạp hơn.

Lưu ý thực chiến cho Junior

Khi phỏng vấn, cần phân biệt rõ ràng hai trường hợp này vì chúng quyết định cách quản lý bộ nhớ và hiệu năng của bộ nhớ đệm (cache) trong CPU.

Hiện tượng Hash Collision (Xung đột băm) xảy ra khi nào và các chiến lược giải quyết xung đột phổ biến nào thường được áp dụng trong Hash Table?

Hiện tượng Hash Collision là gì?

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ủ đề