Bài giảng "Cấu trúc dữ liệu và giải thuật: Bảng băm" rình bày các khái niệm về bảng băm, giải quyết đụng độ bằng kết nối, định nghĩa bảng băm, các thao tác, độ phức tạp, . | Bảng băm Hash Tables Nguyễn Mạnh Hiển hiennm@ Bảng băm Các phần tử dưới dạng cặp khóa-giá trị key-value . Mỗi phần tử được lưu trữ vào một ô nào đó trong mảng tùy theo khóa của nó là gì. Thực hiện các phép tìm chèn xóa trong thời gian O 1 . Không hiệu quả với các thao tác đòi hỏi thông tin thứ tự VD Tìm phần tử lớn nhất và nhỏ nhất. Ví dụ bảng băm Mỗi phần tử là một cặp khóa-giá trị - Tên là khóa - Thu nhập là giá trị So sánh các cấu trúc dữ liệu So sánh thời gian tìm kiếm Vector và danh sách liên kết O n Cây AVL O log n Bảng băm O 1 Hàm băm hash function Ánh xạ khóa sang số nguyên vị trí trong bảng băm . Nếu nhiều khóa ánh xạ sang cùng một số nguyên cùng vị trí trong bảng băm thì sẽ dẫn đến đụng độ Đụng độ sẽ giảm nếu các khóa phân bố đồng đều hơn trên bảng băm. Khi đụng độ xảy ra phải tìm cách phân giải sao cho các phần tử không ghi đè lên nhau. Một hàm băm đơn giản Gọi key Khóa có giá trị nguyên. tableSize Kích thước bảng băm. Một hàm băm đơn giản dùng phép chia lấy phần dư hash key key tableSize Giả sử key 24 48 51 78 15 tableSize 10 Thế thì key tableSize 4 8 1 8 5 Để giảm đụng độ ta thường chọn kích thước bảng là một số nguyên tố. Một hàm băm cho các xâu ký tự int hash const string amp key int tableSize int hashVal 0 for int i 0 i lt i hashVal key i return hashVal tableSize Ví dụ tableSize 100 key quot ABC quot mã ASCII của A B C là 65 66 67 hashVal 65 66 67 100 198 100 98 Nếu key quot CBA quot thì hashVal Một hàm băm tốt hơn cho xâu ký tự key như sau hash key x0 ak 1 x1 ak 2 xk 2 a xk 1 tableSize Nếu xâu ký tự là từ tiếng Anh có thể chọn a 33 37 39 hoặc 41. Thiết kế bảng băm 1. Hàm băm Ánh xạ khóa sang một vị trí trong bảng băm. VD hash key key tableSize 2. Phân giải đụng độ Giải quyết trường hợp nhiều khóa ánh xạ đến cùng một vị trí. Hai giải pháp thường gặp Dây chuyền separate chaining Thăm dò probing Giải pháp dây chuyền Mỗi ô trong mảng giữ một danh sách liên kết các phần tử dây chuyền . Các phần tử có khóa ánh xạ tới .
