Hash table là gì?

Trong cấu trúc dữ liệu (data structure), bảng băm (hash table) còn được gọi là bản đồ băm (hash map) là một cấu trúc dữ liệu triển khai (implement) một kiểu dữ liệu trừu tượng (abstract data type) tập hợp (set), một cấu trúc dữ liệu có thể ánh xạ các khóa (key) thành các giá trị (value). Bảng băm (hash table) sử dụng hàm băm (hash function) để tính chỉ mục (index), còn được gọi là mã băm (hash code) vào một mảng các bucket hoặc slot từ đó có thể tìm thấy giá trị mong muốn. Trong quá trình tra cứu, khóa được băm và kết quả băm cho biết giá trị tương ứng được lưu trữ ở đâu.

Lý tưởng nhất là hàm băm sẽ gán mỗi khóa cho một bucket duy nhất, nhưng hầu hết các thiết kế bảng băm sử dụng một hàm băm không hoàn hảo (imperfect hash function), điều này có thể gây ra xung đột hàm băm (hash collision) trong đó hàm băm tạo ra cùng một chỉ mục cho nhiều hơn một khóa. Những xung ddoojt như vậy thường được điều chỉnh theo một cách nào đó.

Trong bảng băm có kích thước tốt, độ phức tạp thời gian trung bình (average time complexity) cho mỗi lần tra cứu độc lập với số phần tử (element) được lưu trữ trong bảng. Nhiều thiết kế bảng băm cũng cho phép chèn và xóa các cặp khóa-giá trị (key-value paris) tùy ý, với chi phí (cost) trung bình không đổi được phân bổ cho mỗi hoạt động (operation).

Băm (hashing) là một ví dụ về sự đánh đổi giữa không gian và thời gian (space-time tradeoff). Nếu bộ nhớ là vô hạn, toàn bộ khóa có thể được sử dụng trực tiếp làm chỉ mục để định vị giá trị của nó với một lần truy cập bộ nhớ. Mặt khác, nếu thời gian là vô hạn các giá trị có thể được lưu trữ bất kể khóa của chúng và tìm kiếm nhị phân (binary search) hoặc tìm kiếm tuyến tính (linear search ) có thể được sử dụng để truy xuất phần tử.