tailieunhanh - 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,. | HASH TABLE Nguyễn Xuân Vinh nguyenxuanvinh@ CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] 2 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ả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 (collision) Các bảng băm phổ biến (đọc them) Java Map Interface Map implementations in Java HashMap example 3 Giới thiệu Tất cả các thao tác phải so sánh khoá!!! Khắc phục? 4 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ả? 5 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 O(n) 6 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) Tìm: nhị phân, nhanh O(logn) 7 Vấn đề cơ bản Linked list Lưu trữ | HASH TABLE Nguyễn Xuân Vinh nguyenxuanvinh@ CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] 2 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ả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 (collision) Các bảng băm phổ biến (đọc them) Java Map Interface Map implementations in Java HashMap example 3 Giới thiệu Tất cả các thao tác phải so sánh khoá!!! Khắc phục? 4 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ả? 5 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 O(n) 6 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) Tìm: nhị phân, nhanh O(logn) 7 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) Tìm kiếm: tìm kiếm tuần tự O(n) 8 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 table Array as table 9903030 9802020 9801010 0056789 0012345 0033333 Thao Minh Phuong Danh An Binh 90 9908080 Tung . . Vấn đề: lưu trữ 10,000,000 mẫu tin sinh viên và tìm kiếm theo mã số sinh viên. 10 Array as table : 33333 : 12345 0 : : Binh : An : : : : 56789 Danh : 9908080 : : : Tung : : : : : 9999999 Một cách “stupid” là lưu trữ mẫu tin trong mảng cực lớn 09999999 Index được sử dụng như là mã số sinh viên. Khi đó mẫu tin sv với ms 0012345 được lưu trữ ở A[12345]! 11 Array as table Dạng bảng băm với địa chỉ trực tiếp Mỗi vị trí tương ứng một khoá trong U Nếu 1 phần tử x có khoá k, thì T[k] chứa tham chiếu đến x Ngược lại T[k] = Ø được thể hiện là null U (universe of key) K (actual keys) 2 3 5 6 4 1 7 9 8 0 - - - - - - 0 1 2 3