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

Bài 10: Bảng băm<br /> Giảng viên: Hoàng Thị Điệp<br /> Khoa Công nghệ Thông tin – Đại học Công Nghệ<br /> <br /> Cấu trúc dữ liệu và giải thuật<br /> <br /> HKI, 2013-2014<br /> <br /> Kiểm tra viết, 15 phút<br /> (Sinh viên có thể sử dụng tài liệu.)<br /> 1. Nêu 2 hàm băm<br /> 2. Nêu 2 phương pháp giải quyết va chạm trong bảng<br /> băm<br /> nói tới trong Chương 9 Giáo trình.<br /> <br /> 2<br /> <br /> diepht@vnu<br /> <br /> Nội dung chính<br />  Giới thiệu phương pháp băm<br />  Hashing<br /> <br />  Các hàm băm<br />  Hash function<br /> <br />  Các chiến lược giải quyết va chạm<br />  Collision resolution<br /> <br /> 3<br /> <br /> diepht@vnu<br /> <br /> KDLTT từ điển<br />  Trường hợp riêng của tập<br /> <br /> động khi ta chỉ quan tâm tới<br /> tìm kiếm, xen, loại<br />  Là tập hợp trong đó mỗi phần<br /> tử là một cặp (khóa, dữ liệu)<br />  Có thể tìm kiếm theo khóa<br />  Được sắp hoặc không được<br /> <br /> sắp<br /> <br />  Các phần tử có thể có cùng<br /> <br /> khóa*<br /> <br />  Dictionary vs. Map<br /> <br />  Ứng dụng<br />  Từ vựng – nghĩa<br />  Tên miền – địa chỉ IP<br />  Mã sinh viên – hồ sơ SV<br /> <br /> 4<br /> <br />  Các phép toán<br />  find(k) trả về 1 phần tử có<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> khóa k. Nếu không thấy trả<br /> về NULL.<br /> findAll(k)<br /> insert(k, v) thêm phần tử (k,<br /> v) và trả về con trỏ tới nó<br /> erase(k) loại bỏ phần tử bất<br /> kì có khóa bằng k<br /> erase(p) loại bỏ phần tử trỏ<br /> bởi p<br /> size() trả về số lượng phần tử<br /> empty() kiểm tra xem từ điển<br /> rỗng hay không<br /> <br /> diepht@vnu<br /> <br /> Phương án cài KDLTT từ điển<br />  Mảng được sắp / không được sắp<br />  DSLK đơn/kép được sắp / không được sắp<br />  Cây tìm kiếm nhị phân<br /> <br /> 5<br /> <br /> diepht@vnu<br /> <br />