Nội dung

Bài 10: Bảng băm Giảng viên: Hoàng Thị Điệp Khoa Công nghệ Thông tin – Đại học Công Nghệ Cấu trúc dữ liệu và giải thuật HKI, 2013-2014 Kiểm tra viết, 15 phút (Sinh viên có thể sử dụng tài liệu.) 1. Nêu 2 hàm băm 2. Nêu 2 phương pháp giải quyết va chạm trong bảng băm nói tới trong Chương 9 Giáo trình. 2 diepht@vnu Nội dung chính  Giới thiệu phương pháp băm  Hashing  Các hàm băm  Hash function  Các chiến lược giải quyết va chạm  Collision resolution 3 diepht@vnu KDLTT từ điển  Trường hợp riêng của tập động khi ta chỉ quan tâm tới tìm kiếm, xen, loại  Là tập hợp trong đó mỗi phần tử là một cặp (khóa, dữ liệu)  Có thể tìm kiếm theo khóa  Được sắp hoặc không được sắp  Các phần tử có thể có cùng khóa*  Dictionary vs. Map  Ứng dụng  Từ vựng – nghĩa  Tên miền – địa chỉ IP  Mã sinh viên – hồ sơ SV 4  Các phép toán  find(k) trả về 1 phần tử có       khóa k. Nếu không thấy trả về NULL. findAll(k) insert(k, v) thêm phần tử (k, v) và trả về con trỏ tới nó erase(k) loại bỏ phần tử bất kì có khóa bằng k erase(p) loại bỏ phần tử trỏ bởi p size() trả về số lượng phần tử empty() kiểm tra xem từ điển rỗng hay không diepht@vnu Phương án cài KDLTT từ điển  Mảng được sắp / không được sắp  DSLK đơn/kép được sắp / không được sắp  Cây tìm kiếm nhị phân 5 diepht@vnu Cài KDLTT từ điển bằng mảng  Nếu khoá của dữ liệu là số nguyên không âm và nằm trong khoảng [0..SIZE-1]  có thể sử dụng một mảng data có cỡ SIZE  dữ liệu có khoá k sẽ được lưu trong data[k]  tìm kiếm, xen, loại đều thực hiện trong thời gian O(1)  Thực tế không khả thi vì  số phần tử dữ liệu có thể rất nhỏ so với SIZE  khoá có thể không phải là số nguyên  Ta muốn lợi dụng tính ưu việt của phép truy cập trực tiếp của mảng 6 diepht@vnu Phương pháp băm  Lưu tập dữ liệu trong mảng T với cỡ là SIZE  Hàm băm: là hàm ứng với mỗi giá trị khoá k của dữ liệu với một chỉ số i (0 <= i <= SIZE-1)  Dữ liệu này sẽ được lưu trong T[i]  h : K  {0,1,…,SIZE-1} 0 1 Tính địa chỉ … i Tập các giá trị khoá Hàm băm h … SIZE-1 7 Mảng T diepht@vnu 8 diepht@vnu Sự va chạm  Nếu  có k1 ≠ k2 thì h(k1) ≠ h(k2), và  việc tính chỉ số h(k) ứng với mỗi khoá k chỉ đòi hỏi thời gian hằng thì các phép toán tìm kiếm, xen, loại chỉ cần thời gian O(1)  Va chạm  Trong thực tế k1 ≠ k2 có thể cho h(k1) = h(k2)  Giải quyết va chạm như thế nào? 9 diepht@vnu Hàm băm  Hàm băm tốt  tính nhanh và dễ dàng  đảm bảo ít va chạm  Một số hàm băm  Khóa là số nguyên không âm  Phương pháp chia  Phương pháp nhân  Khóa là xâu ký tự: đổi xâu thành số nguyên không âm 10 diepht@vnu