Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 9 Bảng băm cung cấp cho người học những kiến thức như: giới thiệu về bảng băm; hàm băm; xung đột; bài tập về bảng băm. Mời các bạn cùng tham khảo! | GIỚI THIỆU Tổ chức lưu trữ thông tin 100 nhân viên của một công ty ABC mỗi nhân viên có mã số riêng EMP_ID trong phạm vi 0 99 Ta có thể dùng mảng để lưu trữ với EMP_ID là chỉ mục tương ứng trong mảng. Dữ liệu An Bình Minh Ngọc EMP_ID 0 1 2 99 3 KHOA CÔNG NGHỆ THÔNG TIN GIỚI THIỆU Tổ chức lưu trữ thông tin 100 nhân viên của một công ty ABC mỗi nhân viên có mã số riêng EMP_ID trong phạm vi 00000 99999 Ta cần một mảng có 100 000 phần tử để lưu trữ với EMP_ID là chỉ mục tương ứng trong mảng. Dữ liệu An Bình Minh Ngọc EMP_ID 00000 00001 00002 99 99999 Tốn nhiều không gian lưu trữ 4 KHOA CÔNG NGHỆ THÔNG TIN GIỚI THIỆU Cần giải pháp khác để lưu trữ 100 nhân viên với EMP_ID có phạm vi 00000 99999 Cần có hàm chuyển EMP_ID có 5 số về EMP_ID có 2 số hàm băm Cần có mảng ánh xạ mỗi khóa EMP_ID 5 số tới vị trí trong mảng EMP_ID 2 số. Bảng băm 5 KHOA CÔNG NGHỆ THÔNG TIN BẢNG BĂM Bảng băm là một cấu trúc dữ liệu mà các khóa được ánh xạ đến các vị trí trong mảng thông qua một hàm băm. Trong bảng băm một phần tử có khóa k được lưu tại chỉ mục có hàm băm h k chứ không phải vị trí k. Quá trình ánh xạ các khóa vào vị trí phù hợp trong bảng băm gọi là hashing. Khi hai khóa có cùng vị trí trong bảng băm gọi là xung đột collision 6 KHOA CÔNG NGHỆ THÔNG TIN BẢNG BĂM Bảng băm là một cấu trúc dữ liệu mà các khóa được ánh xạ đến các vị trí trong mảng thông qua một hàm băm. 7 KHOA CÔNG NGHỆ THÔNG TIN HÀM BĂM Hàm băm là một công thức toán học khi áp dụng ánh xạ cho khóa k sẽ tạo ra một số nguyên dùng làm chỉ mục trong bảng băm. Một hàm băm tốt thỏa mãn các điều kiện sau 1. Tính toán nhanh 2. Các khóa được phân bố đều trong bảng 3. Ít xảy ra xung đột 4. Xử lý các loại khóa có kiểu dữ liệu khác nhau 8 KHOA CÔNG NGHỆ THÔNG TIN CÁC PHƯƠNG PHÁP TẠO HÀM BĂM 1. Phương pháp chia h x x M VD tính giá trị băm cho các khóa 1234 5462 2362 M 10 chọn số chẵn kích thước bảng h 1234 1234 10 4 h 5462 5462 10 2 Xung đột h 2362 2362 10 2 9 KHOA CÔNG NGHỆ THÔNG TIN CÁC PHƯƠNG PHÁP TẠO HÀM BĂM 1. Phương pháp chia h
