Bài giảng Cấu trúc dữ liệu: Chương 8 - Nguyễn Xuân Vinh

Bài giảng Cấu trúc dữ liệu - Chương 8: Hash table trình bày các vấn đề cơ bản với arrays list, linked list, bảng băm "hoàn hảo", hàm băm hoàn hảo, phương pháp xây dựng hàm băm, ưu điểm của bảng băm, các cách giải quyết xung đột, các bảng băm phổ biến,...
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu: Chương 8 - Nguyễn Xuân VinhGV: NGUYỄN XUÂN VINH CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] HASH TABLEMÔN: CẤU TRÚC DỮ LIỆU Nguyễn Xuân Vinh nguyenxuanvinh@hcmuaf.edu.6/12/14 vn/XX1GV: NGUYỄN XUÂN VINH Nội dung • Giới thiệu • Các vấn đề cơ bản với ArrayList, Linked List • Bảng băm “hoàn hảo” • Hàm băm hoàn hảoMÔN: CẤU TRÚC DỮ LIỆU • Phương pháp xây dựng hàm băm • Ưu điểm của bảng băm • Các cách giải quyết xung đột (collision) • Các bảng băm phổ biến (đọc them) • Java Map Interface • Map implementations in Java HashMap example6/12/14 •/XX 22GV: NGUYỄN XUÂN VINH Giới thiệuMÔN: CẤU TRÚC DỮ LIỆU Tất cả các thao tác phải so sánh khoá!!!6/12/14 Khắc/XX 3 phục?3GV: NGUYỄN XUÂN VINH Vấn đề cơ bản • Bài toán: cần lưu trữ các mẫu tin và thực hiện các thao tác – Thêm mẫu tin – Xoá mẫu tin – Tìm mẫu tin theo khóaMÔN: CẤU TRÚC DỮ LIỆU • Tìm cách thức thực hiện một cách hiệu quả?6/12/14/XX 44GV: NGUYỄN XUÂN VINH Vấn đề cơ bản • Unsorted array – Sử dụng mảng để lưu mẫu tin, không có thứ tự – Thêm: thêm cuối nhanh O(1) – Xoá: chậm do tìm rồi xoá O(n)MÔN: CẤU TRÚC DỮ LIỆU – Tìm kiếm: tuần tự chậm O(n)6/12/14/XX 55GV: NGUYỄN XUÂN VINH Vấn đề cơ bản • Sorted array – Sử dụng mảng lưu trữ mẫu tin, có thứ tự – Thêm: chèn vào đúng vị trí, chậm O(n) – Xoá: phải dời các phần tử phía sau, chậm O(n)MÔN: CẤU TRÚC DỮ LIỆU – Tìm: nhị phân, nhanh O(logn)6/12/14/XX 66GV: NGUYỄN XUÂN VINH Vấn đề cơ bản • Linked list – Lưu trữ mẫu tin trong danh sách liên kết – Thêm: nhanh, O(1) – Xoá: nhanh khi xoá nút, chậm khi tìm O(n)MÔN: CẤU TRÚC DỮ LIỆU – Tìm kiếm: tìm kiếm tuần tự O(n)6/12/14/XX 77GV: NGUYỄN XUÂN VINH Vấn đề cơ bản • Cấu trúc dữ liệu phức tạp hơn, nhưng thực thi tốt hơn – Tree BST – Hash tableMÔN: CẤU TRÚC DỮ LIỆU6/12/14/XX 88GV: NGUYỄN XUÂN VINH Array as table ...