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

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 7: Bảng băm - Trần Minh Thái

1. Chương 7. Bảng băm (Hash Table) Trần Minh Thái Email: [email protected] Website: www.minhthai.edu.vn 1
2. Nội dung 1. Khái niệm 2. Đặc điểm và cấu trúc 3. Một số phương pháp 4. Giải quyết đụng độ 2
3. 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
4. Truy 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? 4
5. 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: 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 5
6. Bảng băm (Hash Table) 6
7. 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
8. 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
9. 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
10. Vấn đề Bảng băm U 0 (universe of keys) h(k1) k1 h(k4) K k4 (actual k5 h(k ) keys) 2 h(k5) k2 h(k ) k3 3 p - 1 10
11. 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
12. 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 Hash value Giá trị Hàm Địa chỉ khoá băm hoặc chỉ mục 12
13. Hàm băm Ví 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”) → 131 Tính địa chỉ của khoá “BA” : hashfunc(“BA”) → 131 Khi hàm băm 2 khoá vào cùng 1 địa chỉ thì gọi là đụng độ (Collision) 13
14. Yê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 độ 14
15. Hà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 / / 15
16. Hà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ảng Chọ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 16
17. Hà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 bảng, A là hằng số: 0 < A < 1 Chọn m và A? ▪Thường chọn m = 2p ▪Knuth: A = (5 - 1)/2 0.618033987 được xem là tốt 17
18. Hàm băm sử dụng phương pháp nhân m=100, A=0.61803 M=100, A=0.52173 Khoá Địa chỉ Khoá Địa chỉ 325 86 325 56 125 25 125 21 147 85 147 69 18
19. Hàm băm phổ quát ▪Một tập các hàm băm H là phổ quát (universal ) nếu h H và 2 khoá k, ta có xác suất: Pr{h(k) = h(l)} <= 1/m với m là kích thước bảng ▪Để xác suất xảy ra đụng độ thấp, khởi tạo một tập các hàm băm H phổ quát và từ đó h được chọn ngẫu nhiên 19
20. Đụng độ (collision) địa chỉ ▪Xảy ra khi h(x) ánh xạ hai khoá vào cùng vị trí U 0 (universe of keys) collisionh(k1) k1 h(k4) K k4 (actual k5 h(k ) = h(k ) keys) 2 5 k2 h(k ) k3 3 p - 1 20
21. Ví dụ 0  1 • Sử dụng bảng băm có kích 025-612-0001 2 thước N = 10,000 981-101-0002 3  4 • Hàm băm 451-229-0004 h(x) = 4 chữ số cuối của x 9997  9998 200-751-9998 9999  21
22. Ví dụ 0  1 • Giả sử chèn thêm khóa 025-612-0001 2 176-354-9998 981-101-0002 3  4 → Giá trị băm trùng với 451-229-0004 khoá 200-751-9998 !!! 9997  9998 200-751-9998 9999  176-354-9998 22
23. Giải quyết đụng độ bằng phương pháp nối kết 23
24. Giải quyết đụng độ bằng cách băm lại ▪Phương pháp dò tuyến tính (Linear Probe) ▪Nếu băm lần đầu bị xung đột thì băm lại lần 1, lần 2, Quá trình băm lại diễn ra cho đến khi không còn xung đột nữa hi(key)=(h(key)+i) mode m với h(key) là hàm băm chính của bảng băm 24
25. Ví dụ • h(x) = x mod 13 • Chèn các khoá theo thứ tự 18, 41, 22, 44, 59, 32, 31, 73 0 1 2 3 4 5 6 7 8 9 10 11 12 41 18 44 59 32 22 31 73 0 1 2 3 4 5 6 7 8 9 10 11 12 25
26. Giải quyết đụng độ bằng cách băm lại ▪Phương pháp dò bậc hai (Quadratic Probing Method) 2 hi(key)=(h(key) + i ) mod m với h(key) là hàm băm chính của bảng băm ▪Nếu đã dò đến cuối bảng thì trở về dò lại từ đầu bảng ▪Nên chọn m là số nguyên tố 26
27. Bài tập ▪Cho dãy khóa: 23, 24, 27, 1, 8, 17, 28, 10, 25, 11, 30, 20, 12, 6, 2, 0 ▪Giả sử h(x) = x mod 17 ▪Hãy chèn các khóa trên theo thứ tự từ trái sang phải và dùng phương pháp dò bậc hai để giải quyết đụng độ 27