tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Bài 9 - Hoàng Thị Điệp

Bài giảng "Cấu trúc dữ liệu và giải thuật - Bài 9: Bảng băm" cung cấp cho người học các kiến thức: Phương pháp băm, các hàm băm, các chiến lược giải quyết va trạm. nội dung chi tiết. | HK I, 2012-2013 Bài 9: 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ệ Mục tiêu bài học • Phương pháp băm • Các hàm băm – Hash function • Các chiến lược giải quyết va chạm – Collision resolution diepht@vnu INT2203/w10 2 Tập động và Từ điển • KDLTT tập động – – – – – – – find insert remove/erase max min next previous • KDLTT từ điển diepht@vnu INT2203/w10 3 Cài KDLTT từ điển bằng các CTDL đã học • 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 diepht@vnu INT2203/w10 5 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 [0SIZE-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 .