Nội dung của bài giảng Cấu trúc dữ liệu và giải thuật - Chương 6 trình bày về Hash table. Trong chương này người học có thể hiểu được một số kiến thức sau: Mô tả, hàm băm, bảng băm kết nối trực tiếp, bảng băm kết nối hợp nhất, bảng băm dò tìm tuyến tính. . | Hash Table Nguyễn Hà Giang 1 Nội dung (giới thiệu 1-2 tiết) • • • • • • Giới thiệu Mô tả Hàm băm Bảng băm kết nối trực tiếp Bảng băm kết nối hợp nhất Bảng băm dò tìm tuyến tính 2 Giới thiệu Tất cả các thao tác phải so sánh khoá!!! Khắc phục? 3 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óa • Tìm cách thức thực hiện một cách hiệu quả? 4 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) – Tìm kiếm: tuần tự chậm .
