TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật: Bảng băm - Nguyễn Mạnh Hiển (HKI năm 2020-2021)

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 .

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Bài giảng Cấu trúc dữ liệu
• Bảng băm
• Giải quyết đụng độ bằng kết nối
• Định nghĩa bảng băm
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp