Bài giảng Cấu trúc dữ liệu và giải thuật: Bảng băm (Hash Table) - Nguyễn Tri Tuấn

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật: Bảng băm (Hash Table) - Nguyễn Tri Tuấn

1. Data Structure & Algorithm Bảng băm (Hash Table) Nguyễn Tri Tuấn Khoa CNTT – ĐH.KHTN.Tp.HCM Email: nttuan@ fit.hcmuns.edu.vn Hash table Giới thiệu Hàm băm Các phương pháp xử lý đụng độ Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM2 1
2. Giới thiệu ª Các thuật ngữ thường dùng: Hash table Hash map Hash function Collision resolution Chaining Open addressing Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM3 Giới thiệu (tt) ªTổng quát: Cho 1 tập S các phần tử được đặc trưng bởi giátrị khóa Trên các giátrị khóa đóxác định 1 quan hệ thứ tự ªYêu cầu: Tổ chức S như thế nào để việc tìm kiếm 1 phần tử có khóa k cho trước tốn ít công sức nhất trong giới hạn bộ nhớ cho phép Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM4 2
3. Giới thiệu (tt) ªPhép băm được đề xuất vàthực hiện trên máy tính từ những năm 1950 ªÝ tưởng: Biến đổi khóa k thành 1 số (bằng cách dùng hash function –hàm băm) 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 dùng trong kĩ thuật này thường là danh sách đặc: mảng hay file Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM5 Giới thiệu (tt) Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM6 3
4. Giới thiệu (tt) ªPhép biến đổi khóa (key transformation): để biến đổi số học những khóa, từ đócó được địa chỉ tương ứng của những phần tử trong mảng ªCác bước thực hiện việc biến đổi khóa: Bước 1: tìm hàm băm H để biến đổi khóa k thành địa chỉ trong bảng Bước 2: giải quyết sự đụng độ (collision-resolution process) Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM7 Giới thiệu (tt) ªThao tác cơ bản nhất được cung cấp bởi Hash- table là “tìm kiếm” (lookup) ªChi phítìm kiếm trung bình làO(1), bất kể số lượng phần tử của mảng ªChi phítìm kiếm xấu nhất (ít gặp) cóthể làO(n) Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM8 4
5. Hash table Giới thiệu Hàm băm Các phương pháp xử lý đụng độ Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM9 Hàm băm (Hash function) ªĐị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 K vào tập các địa chỉ A: H : K A ka = H(k) Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM10 5
6. Hàm băm (Hash function) (tt) ªKhó khăn đặt ra: Tập các giátrị khóa cóthể lớn hơn kích thước mảng rất nhiều Vídụ: quản lý danh sách sinh viên gồm 1000 SV, mã SV gồm 7 chữ số Có107 khóa được ánh xạ lên 1000 chỉ số của mảng à H làhàm nhiều -một (many-to-one function) ªSự đụng độ (Collision): $k1, k2 Î K: k1 ≠ k2, H(k1) = H(k2) Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM11 Hàm băm (Hash function) (tt) ªNhững yêu cầu đối với hàm băm: Tính toán nhanh Các khóa được phân bố đều trong bảng Ít xảy ra đụng độ Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM12 6
7. Hàm băm (Hash function) (tt) ªVídụ1 hàm băm: Xét lại vídụdanh sách sinh viên: Với kích thước mảng làM=1000, ta cóthể chọn hàm hàm băm như sau: H(k) = k mod M Hàm này thỏa mãn yêu cầu tính toán nhanh vàtrải đều trên bảng Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM13 Hash table Giới thiệu Hàm băm Các phương pháp xử lý đụng độ Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM14 7
8. Các phương pháp xử lý đụng độ ªPhương pháp nối kết (Chaining) ªPhương pháp địa chỉ mở (Open-addressing) Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM15 Phương pháp nối kết ªỨng với mỗi địa chỉ của bảng, ta có1 danh sách liên kết chứa các phần tử cókhóa khác nhau mà cócùng 1 địa chỉ đó ªVậy ta sẽ có1 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 Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM16 8
9. Phương pháp nối kết (tt) 0 1 2 . . . z M-2 M-1 Cấu trúc 1 bảng băm theo phương pháp nối kết, sử dụng danh sách liên kết đơn Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM17 Phương pháp nối kết (tt) Giải quyết đụng độ bằng phương pháp Chaining Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM18 9
10. Phương pháp nối kết (tt) ªCó3 cấu trúc dữ liệu thường dùng với phương pháp nối kết: Danh sách liên kết đơn Mảng cấp phát động Cây cân bằng Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM19 Phương pháp địa chỉ mở ª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. Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM20 10
11. Phương pháp địa chỉ mở (tt) ªCó3 cách thực hiện Open addressing: 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) Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM21 Phương pháp địa chỉ mở (tt) Giải quyết đụng độ bằng phương pháp Linear probing (Open addressing) Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM22 11
12. Linear probing ªÝ tưởng: h(k, i) = (H(k) + stepsize) mod M i: thứ tự của lần thử (i = 0,1,2, ) H(k): hàm băm stepsize: khoảng cách bước thử (stepsize cóthể là1 hoặc lài) M: số phần tử của bảng băm Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM23 Quadratic probing ªÝ tưởng: h(k, i) = (H(k) + i2) mod M i: thứ tự của lần thử (i = 0,1,2, ) H(k): hàm băm M: số phần tử của bảng băm Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM24 12
13. Double hashing ªÝ tưởng: h(k, i) = (H1(k) + i*H2(k)) mod M i: thứ tự của lần thử (i = 0,1,2, ) H1(k) vàH2(k) : hàm băm M: số phần tử của bảng băm Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM25 Các ưu thế của Chaining so với Open-addressing ªĐơn giản khi cài đặt ªSử dụng các cấu trức dữ liệu cơ bản ªOpen-addressing giải quyết được đụng độ nhưng lại cóthể gây ra những đụng độ mới ªChaining không bịảnh hưởng về tốc độ khi bảng gần đầy ªÍt tốn bộ nhớ khi bảng thưa (chứa ít phần tử) Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM26 13
14. Thank you for your attention Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM27 QQ && AA Winter 2006Data Structure & Algorithm -Hashing Table -Nguyen Tri Tuan, DH.KHTN Tp.HCM28 14