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 độ. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
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) Chương 7. Bảng băm (Hash Table)TrầnMinhTháiEmail:minhthai@huflit.edu.vnWebsite:www.minhthai.edu.vn 1Nội dung1. Khái niệm2. Đặc điểm và cấu trúc3. Một số phương pháp4. Giải quyết đụng độ 2Truy 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? 3Truy xuất trực tiếp• Tạo một mảng T[0..m-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? 4Tuy 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: 1. Bảng sẽ có kích thước 232 (hơn 4 tỉ ô) 2. 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ừ 0...p-1 Hash Table 5Bảng băm (Hash Table) 6Thà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 7Cá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) 8Vấ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()? 9Vấn đề Bảng băm U 0 (universe of keys) h(k1) k1 h(k4) K k4(actual k5 h(k2) h(k2) keys) h(k5) k2 h(k3) k3 p1 10Cá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 11Hàm băm?Hàm biến đổi giá trị khoá (số, chuỗi…) thành địa chỉ, chỉ mụctrong bảng băm Hash value Giátrị Hàm Địachỉ khoá băm hoặcchỉmục 12Hàm bămVí dụ : hàm băm biến đổi khoá dạng chuỗi gồm n kí tự thành 1địa chỉ (số nguyên)int HashFunc(String s){ int n = s.Length, i=0; int sum = 0; while( n-- ) sum = sum + s[i++]; return sum % 256;}Tính địa chỉ của khoá “AB” : hashfunc(“AB”)  131Tính địa chỉ của khoá “BA” : hashfunc(“BA”)  131Khi hàm băm 2 khoá vào cùng 1 địa chỉ thì gọi là đụng độ(Collision) 13Yêu cầu của hàm băm• Tính toán nhanh• Các khoá được phân bố đều trong bảng• Ít xảy ra đụng độ 14Hàm băm dạng bảng tra Khoá Địa chỉ Khóa Địa chỉ Khóa Địa chỉ Khóa Địa chỉ a 0 h 7 o 14 v 21 b 1 I 8 p 15 w 22 c 2 j 9 q 16 x 23 d 3 k 10 r 17 y 24 e 4 l 11 s 18 z 25 f 5 m 12 t 19 / / g 6 n 13 u 20 / / 15Hàm băm sử dụng phương pháp chia• Dùng số dư: h(k) = |k| mod m• Với k là khoá, m là kích thước của bảngChọn giá trị m? m là nguyên tố m=100 m=97 (nguyên tố) Khoá Địa chỉ Khoá Địa chỉ 325 25 325 34 125 25 125 28 147 47 147 50 16Hàm băm sử dụng phương pháp nhân h(k) = m(kA - kA )• Với k là khóa, m là kích thước ...