Bài giảng "Thiết kế và đánh giá thuật toán: Bảng băm" cung cấp cho người học các kiến thức: Phương pháp băm, hàm băm, giải quyết va chạm. nội dung chi tiết. | Thiết Kế & Đánh Giá Thuật Toán Bảng Băm TS. Lê Nguyên Khôi Trường Đại Học Công Nghệ - ĐHQGHN Nội Dung Phương pháp băm Hàm băm Giải quyết va chạm 1 Bài Toán Từ Điển Dùng tập động cài đặt từ điển Mỗi phần tử là cặp (khóa, dữ liệu) Có thể tìm theo khóa Được sắp xếp hoặc không Chỉ quan tâm tới Tìm kiếm SEARCH ( , ) Chèn INSERT ( , ) Xóa DELETE ( , ) Tổ chức cấu trúc dữ liệu như thế nào? 2 Bài Toán Từ Điển Nếu khóa của dữ liệu là số nguyên không âm trong khoảng 0 − 1 , phân biệt Có thể sử dụng mảng cỡ Dữ liệu khóa lưu tại Tìm kiếm, chèn, xóa trong thời gian (1) Thực tế không khả thi Số phần tử dữ liệu có thể rất nhỏ so với 64-bit thể hiện 2 (18 × 10 ) khóa khác nhau Xâu ký tự thậm chí còn lớn hơn số Khóa có thể không phải số nguyên Tận dụng phép truy cập trực tiếp của mảng 3 Phương Pháp Băm Lưu dữ liệu trong mảng 0 − 1 Hàm băm ℎ: ánh xạ mỗi giá trị khóa của dữ liệu tới một chỉ số (0 ≤ < ) Dữ liệu sẽ được lưu trong [ ] ℎ: → {0, 1, , − 1} 0 1 Tính địa chỉ Hàm băm ℎ i −1 Tập các giá trị khoá Mảng .
