Chương 5: Bảng băm (Hash table)

Nội dung:- Bảng băm- Định nghĩa hàm băm- Phương pháp xây dựng hàm băm- Phương pháp giải quyết đụng độ
Nội dung trích xuất từ tài liệu:
Chương 5: Bảng băm (Hash table) Chương5 Bangbăm(Hashtable) ̉ Nộidung1 Bảng băm2 Định nghĩa hàm băm3 Phương pháp xây dựng hàm băm4 Phương pháp giải quyết đụng độ Chương 5 Bang băm ̉ ̉ Bang băm (Hash Table) Các thuật toán tìm kiếm đều dựa vào việc so sánh giá trị khoá (Key)  Phụ thuộc kích thước của tập các phần tử  Thời gian tìm kiếm không nhanh do phải thực hiện nhiều phép so sánh có thể không cần thiết ( O(n), O(logn), …)=> Có phương pháp lưu trữ nào cho phép thực hiện tìm kiếm với hiệu suất cao hơn không ( độ phức tạp hằng số)?12/04/09 www.lhu.edu.vn Chương 5 Bang băm ̉ Bang truy xuât trực tiêp ̉ ́ ́ Bang gôm m phân tử được ̉ ̀ ̀ lưu trữ dưới dang bang chỉ ̣ ̉ muc ̣  Phần tử có giá trị khoá k được lưu trữ tương ứng tại vị trí thứ k ̀ ́ ̀ ́  Tim kiêm băng cach tra trong bang chỉ muc ̉ ̣  Thời gian tim kiêm là O(1) ̀ ́ Đây là dạng bảng băm cơ bản12/04/09 www.lhu.edu.vn Chương 5 Bang băm ̉ ́ ́ ̉ Câu truc bang băm K: tập các giá trị khoá (set of keys) cân lưu trữ ̀ A: tập các địa chỉ (set of ̉ addresses) trong bang băm 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 cac đia chỉ A ́ ̣12/04/09 www.lhu.edu.vn Chương 5 Bang băm ̉ ̣ ̉ Phân loai bang băm Bảng băm đóng :  Số phân tử cố đinh ̀ ̣  Môi khoa ứng với môt đia chỉ ̃ ́ ̣ ̣  Không thể thực hiên cac thao tac thêm, xoa trên bang băm ̣ ́ ́ ́ ̉  thời gian truy xuất là hằng số Bảng băm mở :  Số phân tử không cố đinh ̀ ̣  Một số khóa có thể có cùng địa chỉ  Có thể thực hiên cac thao tac thêm, xoa phân tử ̣ ́ ́ ́ ̀  Thời gian truy xuất có thể bị suy giảm đôi chút12/04/09 www.lhu.edu.vn Chương 5 Bang băm ̉ ̀ Ham băm (Hash function) Là hàm biến đổi giá trị khoá (số, chuỗi…) thành địa chỉ, chỉ mục trong bảng băm Giá trị Hàm băm Địa chỉ, chỉ mục khoáVí dụ : hàm băm biến đổi khóa chuỗi thành 1 địa chỉ (số nguyên) inthashfunc(char*s,intn) { intsum=0; while(n)sum=sum+*s++; returnsum%256; } Tính địa chỉ của khoá “AB” : hashfunc(“AB”,2)  131 Tính địa chỉ của khoá “BA” : hashfunc(“BA”,2)  131 Khi hàm băm 2 khoá vào cùng 1 địa chỉ gọi là đụng độ (Collision)12/04/09 www.lhu.edu.vn Chương 5 Bang băm ̉ ̀ Ham băm (Hash function) Tiêu chuân đanh giá ham băm ̉ ́ ̀  Tính toán nhanh.  Các khoá được phân bố đều trong bảng.  Ít xảy ra đụng độ .12/04/09 www.lhu.edu.vn Chương 5 Bang băm ̉ Phương phap xây dựng ham băm ́ ̀ Hàm băm dạng bảng tra Hàm băm dùng phương pháp chia Hàm băm dùng phương pháp nhân12/04/09 www.lhu.edu.vn Chương 5 Bang băm ̉ Phương phap xây dựng ham băm ́ ̀ ̀ ̣ ̉ Ham băm dang bang tra Khoá Địa Khóa Địa chỉ Khóa Địa Khóa Địa chỉ chỉ 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 ...