Chapter 5: Bảng băm (Hash Table)

Chia sẻ: Thanh Tran | Ngày: | Loại File: PDF | Số trang:9

Thêm vào BST

Báo xấu

90
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ố)?

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chapter 5: Bảng băm (Hash Table)

Chương 5 Bảng băm Bả Bảng băm (Hash Table) Bảng Các thuật toán tìm kiếm đều dựa vào việc Nội dung Nội so sánh giá trị khoá (Key) Phụ thuộc kích thước của tập các phần tử 1 Bảng băm 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), 2 Định nghĩa hàm băm O(logn), …) 3 Phương pháp xây dựng hàm băm => 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 4 Phương pháp giải quyết đụng độ không ( độ phức tạp hằng số)? 3/11/2010 www.lhu.edu.vn Chương 5 Bảng băm Bả Chương 5 Bảng băm Bả Bảng truy xuất trực tiếp Bảng xuấ trự tiế Cấu trúc bảng băm trúc bả Bảng gồm m phần tử được K: tập các giá trị khoá (set lưu trữ dưới dạng bảng chỉ of keys) cần lưu trữ mục A: tập các địa chỉ (set of addresses) trong bảng băm Phần tử có giá trị khoá k được lưu trữ tương ứng tại vị HF(k): hàm băm dùng để trí thứ k ánh xạ một khoá k từ tập các khoá K thành một địa Tìm kiếm bằng cách tra trong chỉ tương ứng trong tập bảng chỉ mục các địa chỉ A Thời gian tìm kiếm là O(1) Đây là dạng bảng băm cơ bản 3/11/2010 www.lhu.edu.vn 3/11/2010 www.lhu.edu.vn
Chương 5 Bảng băm Bả Chương 5 Bảng băm Bả Hàm băm (Hash function) Hàm Phân loại bảng băm loạ bả Là hàm biến đổi giá trị khoá (số, chuỗi…) thành địa chỉ, chỉ mục Bảng băm đóng : trong bảng băm Số phần tử cố định Giá trị khoá Hàm băm Địa chỉ, chỉ mục Mỗi khóa ứng với một địa chỉ Không thể thực hiện các thao tác thêm, xóa trên bảng băm Ví dụ : hàm băm biến đổi khóa chuỗi thành 1 địa chỉ (số nguyên) thời gian truy xuất là hằng số int hashfunc( char *s, int n ) Bảng băm mở : { int sum = 0; while( n-- ) sum = sum + *s++; Số phần tử không cố định return sum % 256; Một số khóa có thể có cùng địa chỉ } Có thể thực hiện các thao tác thêm, xóa phần tử Tính địa chỉ của khoá “AB” : hashfunc(“AB”,2) 131 Thời gian truy xuất có thể bị suy giảm đôi chút 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) 3/11/2010 www.lhu.edu.vn 3/11/2010 www.lhu.edu.vn Chương 5 Bảng băm Bả Chương 5 Bảng băm Bả Hàm băm (Hash function) Hàm Phương pháp xây dựng hàm băm pháp dự hà Tiêu chuẩn đánh giá hàm băm Tính toán nhanh. Hàm băm dạng bảng tra Các khoá được phân bố đều trong bảng. Hàm băm dùng phương pháp chia Ít xảy ra đụng độ . Hàm băm dùng phương pháp nhân 3/11/2010 www.lhu.edu.vn 3/11/2010 www.lhu.edu.vn
Chương 5 Bảng băm Bả Chương 5 Bảng băm Bả Phương pháp xây dựng hàm băm pháp dự hà Phương pháp xây dựng hàm băm pháp dự hà Hàm băm dạng bảng tra Hàm băm dùng phương pháp chia Khoá Địa chỉ Khóa Địa chỉ Khóa Địa chỉ Khóa Địa chỉ Sử dụng số dư của phép chia để làm địa chỉ: a 0 h 7 o 14 v 21 h(k) = k mod m b 1 i 8 p 15 w 22 k là khoá, m là kích thước (số địa chỉ) của bảng. c 2 j 9 q 16 x 23 vấn đề chọn giá trị m d 3 k 10 r 17 y 24 Nếu chọn m= 2n , h(k) = k mod 2n sẽ dùng n bits thấp e 4 l 11 s 18 z 25 của k để làm địa chỉ f 5 m 12 t 19 / / Nếu chọn m= 10n , h(k) = k mod 10n sẽ dùng n số cuối g 6 n 13 u 20 / / của k để làm địa chỉ nên chọn m là nguyên tố gần với 2n hoặc 10n 3/11/2010 www.lhu.edu.vn 3/11/2010 www.lhu.edu.vn Chương 5 Bảng băm Bả Chương 5 Bảng băm Bả Phương pháp xây dựng hàm băm pháp dự hà Phương pháp xây dựng hàm băm pháp dự hà Ví dụ: Ta có tập khoá là các giá trị số gồm 3 chữ Hàm băm dùng phương pháp nhân số, và vùng nhớ cho bảng địa chỉ có khoảng 100 Sử dụng công thức: mục, như vậy ta sẽ lấy hai số cuối của khoá để h(k) = floor(m (k A mod 1)) làm địa chỉ theo phép chia dư cho 100. với k là khóa, m là kích thước bảng Vd: 325 Mod 100 = 25, 125 Mod 100=25... A là hằng số: 0 < A < 1 M=100 M=97 (nguyên tố) Vấn đề chọn m và A Khoá Địa chỉ Khoá Địa chỉ 325 25 325 34 Ta thường chọn m = 2n hoặc m = 10n 125 25 125 28 Theo Knuth chọn A = 1/2(sqrt(5) -1) 0.618033987 147 47 147 50 được xem là tốt 3/11/2010 www.lhu.edu.vn 3/11/2010 www.lhu.edu.vn
Chương 5 Bảng băm Bả Chương 5 Bảng băm Bả Phương pháp xây dựng hàm băm pháp dự hà Các thao tác trên bảng băm tá bả Ví dụ: Ta có tập khoá là các giá trị số gồm 3 chữ Khởi tạo (Initialize) số, và vùng nhớ cho bảng địa chỉ có khoảng 100 Kiểm tra rỗng (Empty) mục, chọn hằng số A=0.61803 Lấy kích thước của bảng băm (Size) Tính địa chỉ cho khóa 325 Tìm kiếm (Search) h(325) = floor(100 (325*0.61803 mod 1))=86 Thêm mới phần tử (Insert) M=100, A=0.61803 M=100, A=0.52173 Loại bỏ (Remove) Khoá Địa chỉ Khoá Địa chỉ 325 86 325 56 Sao chép (Copy) 125 25 125 21 Duyệt (Traverse) 147 85 147 69 3/11/2010 www.lhu.edu.vn 3/11/2010 www.lhu.edu.vn Chương 5 Bảng băm Bả Chương 5 Bảng băm Bả Các phương pháp giải quyết đụng độ pháp giả quyế đụ độ Các phương pháp giải quyết đụng độ pháp giả quyế đụ độ Phương pháp nối kết phá nố kế Phương pháp nối kết Các phần tử bị đụng độ được gom thành một danh Phương pháp dò tuyến tính sách liên kết (gọi là một bucket). Phương pháp dò bậc hai Một Phương pháp dùng hàm băm kép Bucket 3/11/2010 www.lhu.edu.vn 3/11/2010 www.lhu.edu.vn
Chương 5 Bảng băm Bả Chương 5 Bảng băm Bả Cài đặt bảng băm phương pháp nối kết đặ bả phá nố kế Cài đặt bảng băm phương pháp nối kết đặ bả phá nố kế Khai báo cấu trúc bảng băm: Hàm băm int hashfunc (int key) #define M 100 { return (key % M); } struct node { int key; Phép toán khởi tạo (initbuckets) struct node *next; void initbuckets( ) }; { int b; for (b=0;bnext; } Phép toán chèn phần tử có khóa k vào bảng băm: if (p == NULL) void insert(int k) printf("\n khong co nut co khoa %d" ,k); { int b; else if (p==bucket[b]) pop(b); b=hashfunc(k); else delafter(q); //xoa nut place(b,k); //chen k vao danh sach lien ket } } 3/11/2010 www.lhu.edu.vn 3/11/2010 www.lhu.edu.vn
Chương 5 Bảng băm Bả Chương 5 Bảng băm Bả Cài đặt bảng băm phương pháp nối kết đặ bả phá nố kế Cài đặt bảng băm phương pháp nối kết đặ bả phá nố kế Phép toán xóa bucket trong bảng băm Phép toán xóa tất cả các phần tử trong bảng băm. void clear( ) void clearbucket (int b) { int b; { nodeptr p,q; for (b=0;bnext; while (p!=NULL) freenode(q); { printf("%5d", p->key); } p= p->next; bucket[b] = NULL; //khoi dong lai bucket b } } } 3/11/2010 www.lhu.edu.vn 3/11/2010 www.lhu.edu.vn Chương 5 Bảng băm Bả Chương 5 Bảng băm Bả Cài đặt bảng băm phương pháp nối kết đặ bả phá nố kế Cài đặt bảng băm phương pháp nối kết đặ bả phá nố kế Phép toán duyệt toàn bộ bảng băm: Phép toán tìm kiếm một phần tử trong bảng void traverse( ) nodeptr search(int k) { { int b; nodeptr p; for(b=0;bp->key && p!=NULL) p=p->next; } if (p==NULL || k!=p->key)// khong tim thay } return(NULL); else return(p); } 3/11/2010 www.lhu.edu.vn 3/11/2010 www.lhu.edu.vn
Chương 5 Bảng băm Bả Chương 5 Bảng băm Bả Các phương pháp giải quyết đụng độ pháp giả quyế đụ độ Phương pháp dò tuyến tính pháp tuyế tí Phương pháp dò tuyến tính Xét dọc theo bảng cho đến khi tìm thấy khóa Ý tưởng: Nếu vị trí hiện tại đã bị khóa khác đang xét hoặc tìm thấy một ô trống. chiếm, thử xét ô kế tiếp trong bảng: Ít tốn bộ nhớ hơn dùng danh sách kiên kết linear_probing_insert(K) (chaining) if (table is full) error Không phải lưu các liên kết probe = h(K) while (table[probe] occupied) Nhưng chậm hơn dùng danh sách kiên kết. probe = (probe + 1) mod M Có thể phải duyệt dọc theo bảng trên con đường dài table[probe] = K 3/11/2010 www.lhu.edu.vn 3/11/2010 www.lhu.edu.vn Chương 5 Bảng băm Bả Chương 5 Bảng băm Bả Phương pháp dò tuyến tính pháp tuyế tí Phương pháp dò tuyến tính pháp tuyế tí Khó khăn: Keáquaûlaø Keá quaû laø t : Các phần tử bị đụng độ có xu hướng bị dồn cục 18 41 22 44 59 32 31 73 Kích thước bảng bị giới hạn 5 2 9 5 7 6 5 8 Ví dụ h(K) = K mod 13 41 18 44 59 32 22 31 73 Lần lượt chèn các khóa sau vào bảng: 0 1 2 3 4 5 6 7 8 9 10 11 12 18 41 22 44 59 32 31 73 5 2 9 5 7 6 7 8 3/11/2010 www.lhu.edu.vn 3/11/2010 www.lhu.edu.vn
Chương 5 Bảng băm Bả Chương 5 Bảng băm Bả Cài đặt bảng băm phương pháp dò tuyến tính đặ bả phá tuyế tí Cài đặt bảng băm phương pháp dò tuyến tính đặ bả phá tuyế tí Khai báo cấu trúc bảng băm: Hàm băm int hashfunc (int key) #define NULLKEY –1 { return (key % M); } #define M 100 struct node Phép toán khởi tạo (initbuckets) { int key; void initialize( ) }; { int i; for(i=0;iM) i= i-M; } } hashtable[i].key=k; N=N+1; Lưu ý bảng băm đầy khi N=M-1, chúng ta nên dành ít return(i); nhất một phần tử trống trên bảng băm. } 3/11/2010 www.lhu.edu.vn 3/11/2010 www.lhu.edu.vn
Chương 5 Bảng băm Bả Cài đặt bảng băm phương pháp dò tuyến tính đặ bả phá tuyế tí Phép toán tìm kiếm một phần tử trong bảng int search(int k) { int i; i=hashfunc(k); while(hashtable[i].key!=k && hashtable[i].key !=NULKEY) {//bam lai (theo phuong phap do tuyen tinh: //fi(key)=f(key)+i) % M i=i+1; if(i>=M) i=i-M; } if(hashtable[i].key==k) //tim thay return(i); else //khong tim thay return(M); } 3/11/2010 www.lhu.edu.vn