Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 6: Các chiến lược tìm kiếm (Tiếp theo)

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 6: Các chiến lược tìm kiếm (Tiếp theo)

1. 31 Hash Table Cấu trúc dữ liệu và giải thuật – HCMUS 2011 32  Vấn đề: Cho trước 1 tập S gồm các phần tử được đặc trưng bởi giá trị khóa. Trên giá trị các khóa này có quan hệ thứ tự. Tổ chức S như thế nào để tìm kiếm 1 phần tử có khóa k cho trước có độ phức tạp ít nhất trong giới hạn bộ nhớ cho phép?  Ý tưởng: Biến đổi khóa k thành một số (bằng hàm hash) và sử dụng số này như là địa chỉ để tìm kiếm trên bảng dữ liệu. Cấu trúc dữ liệu và giải thuật – HCMUS 2011 © FIT-HCMUS 2011 1
2. 33 ĐNĐTiến +84.95.8345678 VCNam +84.91.2345678 NTHNhung +84.90.9345678 Cấu trúc dữ liệu và giải thuật – HCMUS 2011 34  Chi phí tìm kiếm trung bình: O(1)  Chi phí tìm kiếm trong trường hợp xấu nhất: O(n) (rất ít gặp). Cấu trúc dữ liệu và giải thuật – HCMUS 2011 © FIT-HCMUS 2011 2
3. 35  Định nghĩa: là hàm biến đổi khóa k của phần tử thành địa chỉ trong bảng băm. Ví dụ: H(k) = k mod M.  Tổng quát về phép biến đổi khóa: Là 1 ánh xạ thích hợp từ tập các khóa U vào tập các địa chỉ A. H: U A k a = h(k) Cấu trúc dữ liệu và giải thuật – HCMUS 2011 36  Tập các giá trị khóa (U) có thể lớn hơn rất nhiều so với số khóa thực tế (K) rất nhiều.  Ví dụ: Quản lý danh sách 1000 sinh viên, mã sinh viên gồm 7 chữ số. Có U = 107 khóa so với K = 1000. Cấu trúc dữ liệu và giải thuật – HCMUS 2011 © FIT-HCMUS 2011 3
4. 37 T 1 Key Data 2 3 3 Tập U 2 1 . . 4 4 5 6 . . 5 4. 3 6 Tập K . 7 10 8 8 . . 8 9 . 7 . 9 10 10 Cấu trúc dữ liệu và giải thuật – HCMUS 2011 38  k1, k2 K: k1 ≠ k2, H(k1) = H(k2) T H(3) 9 Tập U 7 1. . . H(4) 5 6 . . 4. 3 . Tập K 10 8 . . H(2) = H(8) 2 . H(10) Cấu trúc dữ liệu và giải thuật – HCMUS 2011 © FIT-HCMUS 2011 4
5. 39 Ít xảy ra Tính đụng toán độ. nhanh. Các khóa phân bố đều. Cấu trúc dữ liệu và giải thuật – HCMUS 2011 40  Xét lại ví dụ về danh sách sinh viên: Với kích thước bảng là M = 1000, ta có thể chọn hàm băm như sau: H(k) = k mod M.  Khóa này thỏa mãn yêu cầu tính toán nhanh và trải đều trên bảng. Cấu trúc dữ liệu và giải thuật – HCMUS 2011 © FIT-HCMUS 2011 5
6. 41  Phương pháp nối kết (chaining)  Phương pháp địa chỉ mở (Open-addressing) Cấu trúc dữ liệu và giải thuật – HCMUS 2011 42  Ứng với mỗi địa chỉ của bảng, ta có một danh sách liên kết chứa các phần tử có khóa khác nhau mà có cùng địa chỉ đó.  Ta sẽ có danh sách (bảng băm) gồm M phần tử chứa địa chỉ đầu của các danh sách liên kết. Cấu trúc dữ liệu và giải thuật – HCMUS 2011 © FIT-HCMUS 2011 6
7. 43 ĐNĐTiến +84.95.8345678 VCNam +84.91.2345678 ĐTMHậu +84.95.6543210 NTHNhung +84.90.9345678 Cấu trúc dữ liệu và giải thuật – HCMUS 2011 44  Tên gọi khác:  Phương pháp dò  Phương pháp thử  Ý tưởng:  Khi đụng độ xảy ra, ta sẽ thử tìm đến vị trị kế tiếp nào đó trong bảng cho đến khi tìm thấy vị trí nào còn trống. Cấu trúc dữ liệu và giải thuật – HCMUS 2011 © FIT-HCMUS 2011 7
8. 45  Phương pháp dò tuyến tính (Linear probing)  Phương pháp dò bậc 2 (Quadratic probing)  Phương pháp băm kép (Double hashing) Cấu trúc dữ liệu và giải thuật – HCMUS 2011 46  Ý tưởng: H(k, i) = (h(k) + i) mod M 1 2 ĐNĐTiến +84.95.8345678 405 406 VCNam +84.91.2345678 407 ĐTMHậu +84.95.6543210 999 NTHNhung +84.90.9345678 1000 Cấu trúc dữ liệu và giải thuật – HCMUS 2011 © FIT-HCMUS 2011 8
9. 47  Phương pháp dò bậc 2: H(k, i) = (h(k) + i2) mod M  Phương pháp băm kép: H(k, i) = (h1(k) + i*h2(k)) mod M Cấu trúc dữ liệu và giải thuật – HCMUS 2011 48  Đơn giản khi cài đặt.  Sử dụng cấu trúc dữ liệu cơ bản.  Phương pháp địa chỉ mở giải quyết được đụng độ nhưng lại có thể gây ra đụng độ mới.  Phương pháp nối kết không bị ảnh hưởng về tốc độ khi mảng gần đầy.  Ít tốn bộ nhớ khi mảng thưa (ít phần tử). Cấu trúc dữ liệu và giải thuật – HCMUS 2011 © FIT-HCMUS 2011 9
10. 49 1. Cho bảng băm có kích thước M = 11. Hàm băm: h(k) = k mod M. Dùng phương pháp địa chỉ mở. Cho biết kết quả sau khi thêm vào bảng băm các khóa 10, 22, 31, 4, 15, 28, 17, 88, 59, với 3 phương pháp xử lý đụng độ: a. Dò tuyến tính. b. Dò bậc 2. c. Băm kép h2(k) = (k mod 19)+1. Cấu trúc dữ liệu và giải thuật – HCMUS 2011 50 2. Cho từ điển Anh – Việt có 15.000 từ, hãy tổ chức cấu trúc dữ liệu bảng băm và cho biết hàm băm thích hợp giúp cho việc tra từ hiệu quả nhất. Cấu trúc dữ liệu và giải thuật – HCMUS 2011 © FIT-HCMUS 2011 10
11. 51 Cấu trúc dữ liệu và giải thuật – HCMUS 2011 © FIT-HCMUS 2011 11