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

ng băm Chương 5 B5 Bảảng băm Chương

(cid:67)(cid:104)(cid:432)(cid:417)(cid:110)(cid:103) (cid:53)

BảBảng băm

(Hash Table) ng băm (Hash Table)

(cid:40)(cid:72)(cid:97)(cid:115)(cid:104)(cid:32)(cid:116)(cid:97)(cid:98)(cid:108)(cid:101)(cid:41) (cid:110)(cid:103)(cid:32)(cid:98)(cid:259)(cid:109) (cid:40)(cid:72)(cid:97)(cid:115)(cid:104)(cid:32)(cid:116)(cid:97)(cid:98)(cid:108)(cid:101)(cid:41) (cid:66)(cid:7843)(cid:66)(cid:7843)(cid:110)(cid:103)(cid:32)(cid:98)(cid:259)(cid:109) (cid:66)(cid:7843)(cid:110)(cid:103)(cid:32)(cid:98)(cid:259)(cid:109) (cid:40)(cid:72)(cid:97)(cid:115)(cid:104)(cid:32)(cid:116)(cid:97)(cid:98)(cid:108)(cid:101)(cid:41)

(cid:61607) Các thuật toán tìm kiếm đều dựa vào việc

i dung NNộội dung Nội dung

1

Bảng băm

2

Định nghĩa hàm băm

so sánh giá trị khoá (Key) (cid:61607) Phụ thuộc kích thước của tập các phần tử (cid:61607) 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

3

Phương pháp xây dựng hàm băm

4

Phương pháp giải quyết đụng độ

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

3/11/2010

www.lhu.edu.vn

ng băm Chương 5 B5 Bảảng băm Chương

BảBảng truy xu

ng truy xuấất trt trựực tic tiếếpp

ng băm CCấấu tu trúrúc bc bảảng băm

(cid:61607) K: tập các giá trị khoá (set

of keys) cần lưu trữ

(cid:61607) Bảng gồm m phần tử được lưu trữ dưới dạng bảng chỉ mục (cid:61607) Phần tử có giá trị khoá k được lưu trữ tương ứng tại vị trí thứ k

(cid:61607) Tìm kiếm bằng cách tra trong

bảng chỉ mục

(cid:61607) A: tập các địa chỉ (set of addresses) trong bảng băm (cid:61607) 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 các địa chỉ A

(cid:61607) Thời gian tìm kiếm là O(1) (cid:61672) Đây là dạng bảng băm cơ bản

3/11/2010

www.lhu.edu.vn

ng băm Chương 5 B5 Bảảng băm Chương

(Hash function) HàHàm bămm băm (Hash function)

ng băm Phân loạại bi bảảng băm Phân lo

(cid:61607) Là hàm biến đổi giá trị khoá (số, chuỗi…) thành địa chỉ, chỉ mục

trong 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)

(cid:61607) Bảng băm đóng : (cid:61607) Số phần tử cố định (cid:61607) Mỗi khóa ứng với một địa chỉ (cid:61607) Không thể thực hiện các thao tác thêm, xóa trên bảng băm (cid:61607) thời gian truy xuất là hằng số

int hashfunc( char *s, int n ) {

(cid:61607) Bảng băm mở :

int sum = 0; while( n-- ) sum = sum + *s++; return sum % 256;

}

Hàm băm Giá trị khoá Địa chỉ, chỉ mục

(cid:61607) Số phần tử không cố định (cid:61607) Một số khóa có thể có cùng địa chỉ (cid:61607) Có thể thực hiện các thao tác thêm, xóa phần tử (cid:61607) Thời gian truy xuất có thể bị suy giảm đôi chút

(cid:61607) Tính địa chỉ của khoá “AB” : hashfunc(“AB”,2) (cid:61664) 131 (cid:61607) Tính địa chỉ của khoá “BA” : hashfunc(“BA”,2) (cid:61664) 131 (cid:61672) 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

ng băm Chương 5 B5 Bảảng băm Chương

(Hash function) HàHàm bămm băm (Hash function)

Phương phápháp xây d Phương

p xây dựựng hng hààm bămm băm

(cid:61607) Tiêu chuẩn đánh giá hàm băm

(cid:61607) Tính toán nhanh. (cid:61607) Các khoá được phân bố đều trong bảng. (cid:61607) Ít xảy ra đụng độ .

(cid:61607) Hàm băm dạng bảng tra (cid:61607) Hàm băm dùng phương pháp chia (cid:61607) Hàm băm dùng phương pháp nhân

3/11/2010

www.lhu.edu.vn

ng băm Chương 5 B5 Bảảng băm Chương

Phương phápháp xây d Phương

p xây dựựng hng hààm bămm băm

Phương phápháp xây d Phương

p xây dựựng hng hààm bămm băm

(cid:61607) Hàm băm dạng bảng tra

(cid:61607) Hàm băm dùng phương pháp chia (cid:61607) Sử dụng số dư của phép chia để làm địa chỉ:

Khoá Địa chỉ Khóa Địa chỉ Khóa Địa chỉ Khóa Địa chỉ a 0 h 7 o 14 v 21

h(k) = k mod m

b 1 i 8 p 15 w 22 c 2 j 9 q 16 x 23 d 3 k 10 r 17 y 24

k là khoá, m là kích thước (số địa chỉ) của bảng. (cid:61672) vấn đề chọn giá trị m (cid:61607) Nếu chọn m= 2n , h(k) = k mod 2n sẽ dùng n bits thấp

của k để làm địa chỉ

(cid:61607) Nếu chọn m= 10n , h(k) = k mod 10n sẽ dùng n số cuối

của k để làm địa chỉ

e 4 l 11 s 18 z 25 f 5 m 12 t 19 / / g 6 n 13 u 20 / /

(cid:61664) nên chọn m là nguyên tố gần với 2n hoặc 10n

3/11/2010

www.lhu.edu.vn

ng băm Chương 5 B5 Bảảng băm Chương

Phương phápháp xây d Phương

p xây dựựng hng hààm bămm băm

Phương phápháp xây d Phương

p xây dựựng hng hààm bămm băm

(cid:61607) Hàm băm dùng phương pháp nhân (cid:61607) Sử dụng công thức:

(cid:61607) Ví dụ: Ta có tập khoá là các giá trị số gồm 3 chữ số, và vùng nhớ cho bảng địa chỉ có khoảng 100 mục, như vậy ta sẽ lấy hai số cuối của khoá để làm địa chỉ theo phép chia dư cho 100. Vd: 325 Mod 100 = 25, 125 Mod 100=25...

h(k) = floor(m (k A mod 1)) với k là khóa, m là kích thước bảng A là hằng số: 0 < A < 1

M=100

(cid:61607) Vấn đề chọn m và A

(cid:61607) Ta thường chọn m = 2n hoặc m = 10n (cid:61607) Theo Knuth chọn A = 1/2(sqrt(5) -1) (cid:61627) 0.618033987

được xem là tốt

3/11/2010

www.lhu.edu.vn

Khoá 325 Địa chỉ 25 M=97 (nguyên tố) Địa chỉ Khoá 34 325 125 25 125 28 147 47 147 50

ng băm Chương 5 B5 Bảảng băm Chương

Phương phápháp xây d Phương

p xây dựựng hng hààm bămm băm

CCáác thao t

c thao táác trên b

ng băm c trên bảảng băm

(cid:61607) Ví dụ: Ta có tập khoá là các giá trị số gồm 3 chữ số, và vùng nhớ cho bảng địa chỉ có khoảng 100 mục, chọn hằng số A=0.61803

(cid:61664)Tính địa chỉ cho khóa 325

h(325) = floor(100 (325*0.61803 mod 1))=86

M=100, A=0.61803 M=100, A=0.52173 Khoá Khoá 325 Địa chỉ 86 325 Địa chỉ 56 125 25 125 21

(cid:61607) Khởi tạo (Initialize) (cid:61607) Kiểm tra rỗng (Empty) (cid:61607) Lấy kích thước của bảng băm (Size) (cid:61607) Tìm kiếm (Search) (cid:61607) Thêm mới phần tử (Insert) (cid:61607) Loại bỏ (Remove) (cid:61607) Sao chép (Copy) (cid:61607) Duyệt (Traverse)

3/11/2010

www.lhu.edu.vn

147 85 147 69

ng băm Chương 5 B5 Bảảng băm Chương

CCáác phương

c phương phápháp gip giảải quy

i quyếết đt đụụng đng độộ

CCáác phương

c phương phápháp gip giảải quy

i quyếết đt đụụng đng độộ

(cid:61607)(cid:61607) Phương ph

Phương phááp np nốối ki kếếtt (cid:61607) Các phần tử bị đụng độ được gom thành một danh

sách liên kết (gọi là một bucket).

(cid:61607) Phương pháp nối kết (cid:61607) Phương pháp dò tuyến tính (cid:61607) Phương pháp dò bậc hai (cid:61607) Phương pháp dùng hàm băm kép

Một Bucket

3/11/2010

www.lhu.edu.vn

ng băm Chương 5 B5 Bảảng băm Chương

CCàài đi đặặt bt bảảng băm phương ph

ng băm phương phááp np nốối ki kếếtt

CCàài đi đặặt bt bảảng băm phương ph

ng băm phương phááp np nốối ki kếếtt

(cid:61607) Khai báo cấu trúc bảng băm:

(cid:61607) Hàm băm

int hashfunc (int key) return (key % M); } {

(cid:61607) Khai báo kiểu con trỏ chỉ nút

(cid:61607) Khai báo mảng bucket chứa M con trỏ đầu của M bucket

(cid:61607) Phép toán khởi tạo (initbuckets) #define M 100 struct node int key; { struct node *next; void initbuckets( ) { }; int b; for (b=0;b

3/11/2010

www.lhu.edu.vn

int isemptybucket (int b) { return(bucket[b] ==NULL ?TRUE :FALSE); } nodeptr bucket[M];

ng băm Chương 5 B5 Bảảng băm Chương

CCàài đi đặặt bt bảảng băm phương ph

ng băm phương phááp np nốối ki kếếtt

CCàài đi đặặt bt bảảng băm phương ph

ng băm phương phááp np nốối ki kếếtt

(cid:61607) Phép toán kiểm tra bảng băm rỗng isempty: (cid:61607) Phép toán hủy mục có khóa k trong bảng băm

void remove(int k) {

3/11/2010

www.lhu.edu.vn

p = bucket[b]; int isempty( ) int b; { for (b=0;bnext; q=p; } int b; nodeptr q, p; b = hashfunc(k); while(p!=NULL && p->key !=k) { if (p == NULL) (cid:61607) Phép toán chèn phần tử có khóa k vào bảng băm: printf("\n khong co nut co khoa %d" ,k); else if (p==bucket[b]) pop(b); void insert(int k) { else delafter(q); //xoa nut } int b; b=hashfunc(k); place(b,k); //chen k vao danh sach lien ket }

ng băm Chương 5 B5 Bảảng băm Chương

CCàài đi đặặt bt bảảng băm phương ph

ng băm phương phááp np nốối ki kếếtt

CCàài đi đặặt bt bảảng băm phương ph

ng băm phương phááp np nốối ki kếếtt

(cid:61607) Phép toán xóa bucket trong bảng băm (cid:61607) Phép toán xóa tất cả các phần tử trong bảng băm.

nodeptr p,q; void clear( ) int b; { for (b=0;b

(cid:61607) Phép toán duyệt các phần tử trong bucket b.

q = NULL; p = bucket[b]; while(p !=NULL) { void traversebucket (int b) p=bucket[b]; {

3/11/2010

www.lhu.edu.vn

q = p; p=p->next; freenode(q); nodeptr p; while (p!=NULL) { printf("%5d", p->key); p= p->next; } bucket[b] = NULL; //khoi dong lai bucket b } } }

ng băm Chương 5 B5 Bảảng băm Chương

CCàài đi đặặt bt bảảng băm phương ph

ng băm phương phááp np nốối ki kếếtt

CCàài đi đặặt bt bảảng băm phương ph

ng băm phương phááp np nốối ki kếếtt

(cid:61607) Phép toán duyệt toàn bộ bảng băm: (cid:61607) Phép toán tìm kiếm một phần tử trong bảng

void traverse( ) { nodeptr search(int k) {

int b; for(b=0;b

3/11/2010

www.lhu.edu.vn

printf("\nBucket thu %d:",b); traversebucket(b); } nodeptr p; int b; b = hashfunc (k); p = bucket[b]; while(k>p->key && p!=NULL) p=p->next; if (p==NULL || k!=p->key)// khong tim thay } return(NULL); else return(p); }