Bảng băm hay còn gọi là bản đồ băm là cấu trúc dữ liệu dùng để lưu trữ dữ liệu theo cách kết hợp. Nó là một loại cấu trúc dữ liệu sử dụng hàm băm để ánh xạ các khóa thành các giá trị. Hàm băm tạo ra một chỉ mục hoặc “mã băm”, được sử dụng để lưu trữ hoặc truy xuất một giá trị tương ứng. Trong khoa học máy tính, bảng băm hoặc bản đồ băm là cấu trúc dữ liệu ánh xạ các khóa tới các giá trị để tra cứu hiệu quả.
Bảng băm sử dụng hàm băm để tạo chỉ mục từ đó dữ liệu mong muốn có thể được truy xuất nhanh chóng. Bảng băm bao gồm hai thành phần chính, hàm băm và mảng các nhóm hoặc vị trí. Hàm băm lấy khóa đầu vào và tạo chỉ mục cho mảng nhóm và mảng nhóm là nơi lưu trữ các giá trị liên quan đến khóa đầu vào. Mỗi khóa được ánh xạ tới một nhóm chứa giá trị liên quan.
Hàm băm được sử dụng để xác định vị trí mỗi phần tử sẽ được lưu trữ trong bảng băm. Nói chung, hàm băm sẽ có đầu vào và mang lại đầu ra số nguyên, đóng vai trò là chỉ mục trong mảng nhóm. Tùy thuộc vào loại dữ liệu được lưu trữ, có thể sử dụng nhiều loại hàm băm khác nhau để giảm thiểu xung đột khi lưu trữ nhiều phần tử bằng cùng một khóa.
Bảng băm cung cấp quyền truy cập nhanh vào các phần tử được lưu trữ trong đó. Việc chèn và tra cứu mất khoảng thời gian không đổi vì chúng không phụ thuộc vào số lượng phần tử được lưu trữ mà chỉ phụ thuộc vào kích thước của mảng nhóm. Do đó, bảng băm rất hiệu quả khi tra cứu, chèn và xóa về mặt độ phức tạp về thời gian.
Bảng băm được sử dụng rộng rãi trong lập trình máy tính, lập chỉ mục cơ sở dữ liệu, đồ họa máy tính, mật mã và nhiều lĩnh vực khác. Chúng đã trở nên cực kỳ phổ biến do độ phức tạp về thời gian hiệu quả và khả năng lưu trữ bất kỳ loại dữ liệu nào với sự va chạm tối thiểu. Bảng băm cũng được sử dụng để triển khai bộ đệm, quản lý bộ nhớ, lập chỉ mục cơ sở dữ liệu và nhiều ứng dụng khác.
