Nội dung: - Bảng băm - Định nghĩa hàm băm - Phương pháp xây dựng hàm băm - Phương pháp giải quyết đụng độ | Bảng băm (Hash table) Chương 5 Phương pháp giải quyết đụng độ 4 Bảng băm 1 Định nghĩa hàm băm 2 Phương pháp xây dựng hàm băm 3 Nội dung Chương 5 Bảng băm Các thuật toán tìm kiếm đều dựa vào việc so sánh giá trị khoá (Key) Phụ thuộc kích thước của tập các phần tử Thời gian tìm kiếm không nhanh do phải thực hiện nhiều phép so sánh có thể không cần thiết ( O(n), O(logn), ) => Có phương pháp lưu trữ nào cho phép thực hiện tìm kiếm với hiệu suất cao hơn không ( độ phức tạp hằng số)? Bảng băm (Hash Table) 5/13/2020 10:11:40 PM Chương 5 Bảng băm Bảng gồm m phần tử được lưu trữ dưới dạng bảng chỉ mục Phần tử có giá trị khoá k được lưu trữ tương ứng tại vị trí thứ k Tìm kiếm bằng cách tra trong bảng chỉ mục Thời gian tìm kiếm là O(1) Đây là dạng bảng băm cơ bản Bảng truy xuất trực tiếp 5/13/2020 10:11:40 PM Chương 5 Bảng băm K: tập các giá trị khoá (set of keys) cần lưu trữ A: tập các địa chỉ (set of addresses) trong bảng băm | Bảng băm (Hash table) Chương 5 Phương pháp giải quyết đụng độ 4 Bảng băm 1 Định nghĩa hàm băm 2 Phương pháp xây dựng hàm băm 3 Nội dung Chương 5 Bảng băm Các thuật toán tìm kiếm đều dựa vào việc so sánh giá trị khoá (Key) Phụ thuộc kích thước của tập các phần tử Thời gian tìm kiếm không nhanh do phải thực hiện nhiều phép so sánh có thể không cần thiết ( O(n), O(logn), ) => Có phương pháp lưu trữ nào cho phép thực hiện tìm kiếm với hiệu suất cao hơn không ( độ phức tạp hằng số)? Bảng băm (Hash Table) 5/13/2020 10:27:04 PM Chương 5 Bảng băm Bảng gồm m phần tử được lưu trữ dưới dạng bảng chỉ mục Phần tử có giá trị khoá k được lưu trữ tương ứng tại vị trí thứ k Tìm kiếm bằng cách tra trong bảng chỉ mục Thời gian tìm kiếm là O(1) Đây là dạng bảng băm cơ bản Bảng truy xuất trực tiếp 5/13/2020 10:27:04 PM Chương 5 Bảng băm K: tập các giá trị khoá (set of keys) cần lưu trữ A: tập các địa chỉ (set of addresses) trong bảng băm HF(k): hàm băm dùng để ánh xạ một khoá k từ tập các khoá K thành một địa chỉ tương ứng trong tập các địa chỉ A Cấu trúc bảng băm 5/13/2020 10:27:04 PM Chương 5 Bảng băm Bảng băm đóng : Số phần tử cố định Mỗi khóa ứng với một địa chỉ Không thể thực hiện các thao tác thêm, xóa trên bảng băm thời gian truy xuất là hằng số Bảng băm mở : Số phần tử không cố định Một số khóa có thể có cùng địa chỉ Có thể thực hiện các thao tác thêm, xóa phần tử Thời gian truy xuất có thể bị suy giảm đôi chút Phân loại bảng băm 5/13/2020 10:27:04 PM Chương 5 Bảng băm Là hàm biến đổi giá trị khoá (số, chuỗi ) thành địa chỉ, chỉ mục trong bảng băm Ví dụ : hàm băm biến đổi khóa chuỗi thành 1 địa chỉ (số nguyên) int hashfunc( char *s, int n ) { int sum = 0; while( n-- ) sum = sum + *s++; return sum % 256; } Tính địa chỉ của khoá “AB” : hashfunc(“AB”,2) 131 Tính địa chỉ của khoá “BA” : hashfunc(“BA”,2) 131 Khi hàm băm 2 khoá vào .
