TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 7 - Trần Minh Thái (2016)

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 7: Bảng băm" cung cấp cho người học các kiến thức: Khái niệm bảng băm, đặc điểm và cấu trúc, một số phương pháp, giải quyết đụng độ. nội dung chi tiết. | Chương 7. Bảng băm (Hash Table) Trần Minh Thái Email: minhthai@ Website: 1 Nội dung Khái niệm Đặc điểm và cấu trúc Một số phương pháp Giải quyết đụng độ 2 2 Truy xuất trực tiếp Giả sử cần lưu trữ thông tin có các đặc điểm nhau: Dữ liệu có các khóa (key) trong phạm vi 0 m-1 Các khóa này là riêng biệt (không trùng nhau) Giải pháp? 3 Truy xuất trực tiếp Tạo một mảng T[0m-1] trong đó T[i] = x nếu x T và key[x] = i T[i] = NULL cho trường hợp ngược lại Cấu trúc này được gọi là bảng truy xuất trực tiếp (direct-address table) Độ phức tạp truy xuất: O(1) Tuy nhiên? 4 Tuy xuất trực tiếp Chỉ thích hợp cho miền giá trị m của các khóa tương đối nhỏ Giả sử khoá là số nguyên 32-bit: Bảng sẽ có kích thước 232 (hơn 4 tỉ ô) Giả sử không có rào cản về bộ nhớ thì cũng mất thời gian để khởi tạo giá trị NULL Giải pháp: ánh xạ những khoá này thành miền nhỏ hơn từ Hash Table 5 Bảng băm (Hash Table) 6 Thành phần dữ liệu K: tập các khoá (set of keys) A: tập các địa chỉ (set of addresses) 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 A 7 Các thao tác Khởi tạo (Initialize) Kiểm tra rỗng (Empty) Lấy kích thước của bảng băm (Size) Tìm kiếm (Search) Thêm mới phần tử (Insert) Loại bỏ (Remove) Sao chép (Copy) Duyệt (Traverse) 8 Vấn đề Bảng băm O(1) cho tất cả các thao tác Khóa không phải là một chỉ số mảng trực tiếp mà chỉ số thông qua hàm h(key) – hàm băm Ví dụ: myArray[h(key)] Vấn đề: h()? 9 Vấn đề Bảng băm 10 h(k2) 0 p - 1 h(k1) h(k4) h(k2) h(k3) k4 k2 k3 k1 k5 U (universe of keys) K (actual keys) h(k5) Các loại Bảng băm Bảng băm đóng: mỗi khóa ứng với một địa chỉ, thời gian truy xuất là hằng số Bảng băm mở: một số khóa có cùng địa chỉ, mỗi mục địa chỉ sẽ là một DSLK các phần tử có cùng địa chỉ, thời gian truy xuất có thể bị suy giảm 11 Hàm băm? Hàm biến đổi giá trị khoá (số, chuỗi ) thành địa chỉ, chỉ mục trong bảng băm 12 Giá trị khoá Hàm băm Địa chỉ hoặc chỉ mục Hash value Hàm băm Ví dụ :

• Cơ sở dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu
• Bảng băm
• Giải quyết đụng độ
• Phương pháp 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
• 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 giảng 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
• Ngôn ngữ diễn đạt giải thuật
• Thiết kế và phân tích giải thuật
• Giải thuật đệ quy
• 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
• Tổng quan về giải thuật
• Kiểu dữ liệu
• Các tiêu chuẩn đánh giá dữ liệu
• phân tích thiết kế
• thiết kế hướng đối tượng
• Cách diễn đạt giải thuật
• Phân tích giải thuật
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp