Bài giảng chương 5: Bảng băm (hashing table)

1BẢNG BĂM (Hashing Table) Chương 5 2Khái niệm z Giả sử ta có 100 số nguyên có giá trị bất kỳ nằm trong khoảng từ 0 . . 999 z Nếu sử dụng mảng a gồm 1000 phần tử để lưu trữ các số nguyên này sao cho a[i] = i thì số lần tìm kiếm số nguyên bất kỳ trong 100 số này là 1 lần z Tuy nhiên, chỉ có 1/10 bộ nhớ được sử dụng, dẫn đến lãng phí bộ nhớ z Phép biến đổi khóa là phương pháp tham khảo trực tiếp các phần tử trong một bảng (bảng băm) thông qua việc biến đổi số học trên những khoá để có được địa chỉ tương ứng của những phần tử ở trong bảng 3Khái niệm z Phép biến đổi khoá là một phương pháp giải quyết tốt về thời gian và vùng nhớ z Tổ chức dữ liệu được dùng cho phép biến đổi khoá là cấu trúc bảng (bảng băm) z Để thực hiện phép biến đổi khoá ta cần hai bước: 1. Bước 1: Tính toán việc biến đổi số học (hàm H() nào đó) để biến đổi khoá cần tìm thành địa chỉ trong bảng. Trong bước này, có thể có hai hay nhiều khoá khác nhau thông qua hàm H() sẽ cho cùng một địa chỉ trong bảng 4Khái niệm 2. Bước 2: Là quá trình giải quyết sự đụng độ cho những khoá khác nhau có cùng một địa chỉ trong bảng z Vấn đề trước tiên là phải chọn hàm biến đổi khoá (hàm băm) để biến đổi các khóa thành các địa chỉ trong bảng z Yêu cầu của hàm băm là phải đơn giản, dễ tính, phải là hàm phân bố đều tập khoá k trên tập địa chỉ để việc đụng độ ít xảy ra z Có một số phương pháp để xây dựng hàm băm như phương pháp chia, nhân, phân đoạn. Tuy nhiên, phương pháp chia modulo thường được sử dụng 5Xây dựng hàm băm z Phương pháp chia modulo: – Gọi M là kích thước bảng băm (thường chọn M là số nguyên tố để ít có bội số - xem trang 8), K là khóa và H(k) là hàm băm, thì: H(k) = k % M – Hàm băm sẽ biến đổi các khoá (là số nguyên, chữ cái hay chuỗi) thành các số nguyên tương ứng trong đoạn [0 ... M - 1] – Nếu khoá là số nguyên thì hàm băm H(k) là: H(k) = k % M 6Xây dựng hàm băm – Nếu khoá là chữ cái từ A đến Z thì giá trị của k sẽ là giá trị của các chữ cái được mã hoá từ 0 đến 25: Ký tự Nhị phân Thập phân A 00000 0 B 00001 1 c 00010 2 ... Z 11001 25 7Xây dựng hàm băm – Nếu khoá là chuỗi ký tự thì giá trị k sẽ là giá trị của sự kết hợp các chữ cái trong chuỗi. Ví dụ, kích thước bảng băm là 101 và cần phải tính địa chỉ của một khóa 4 ký tự là AKEY. Nếu mỗi chữ cái được mã hóa bằng số nhị phân 5 bit như trên thì A K E Y k = 00000 01010 00100 11000 = 10 * 322 + 4 * 321 + 24 * 320 = 10392 Do đó, chỉ số của khóa AKEY trong bảng là: 10392 % 101 = 90 8Xây dựng hàm băm z Tại sao kích thước M của bảng phải là số nguyên tố? z Để trả lời câu hỏi này, giả sử ta chọn M bằng 32 không phải là số nguyên tố, và khóa là chuỗi AKEY như trên, thì: k = 10 * 322 + 4 * 321 + 24 * 320 chỉ phụ thuộc vào ký tự cuối cùng Y. Nghĩa là sẽ có nhiều khóa khác nhau có cùng chỉ số trong bảng nếu các khóa này có cùng ký tự cuối là Y 9Xây dựng hàm băm z Trong trường hợp các khoá dài thì phải tính hàm băm sao cho không bị tràn số. Khi này có thể sử dụng công thức Horner để tính giá trị của hàm băm k = (((an x + an-1 )x + an-2)x + ...+ a0) Trong đó, x là cơ số (ví dụ, 5 bit sẽ có cơ số là 32) và M là kích thước của bảng. Trong ví dụ trên, có thể viết lại bằng công thức Horner là: k = (10 * 32 + 4) * 32 + 24 10 Xây dựng hàm băm z Giải thuật Horner để tính hàm băm như sau: h = key[0]; for(int i = 1; i < keysize; i++) h = ((h * 32) + key[i]) % M; Trong đó, h (= H(k)) là giá trị băm (chỉ số trong bảng băm), key[i] là giá trị của ký tự thứ i của khóa và keysize là chiều dài của khóa. Ví dụ, khóa VERYLONGKEY và M =101 thì khóa này sẽ có chỉ số là 72 11 Xử lý đụng độ z Sự đụng độ là hiện tượng các khóa khác nhau, nhưng qua hàm băm chúng có cùng địa chỉ trên bảng băm. Vấn đề đặt ra là phải lưu trữ chúng như thế nào trong bảng z Xét ba phương pháp: Thử tuyến tính, móc nối ngoài và móc nối trong: 1. Phương pháp thử tuyến tính (linear probing): – Trong phương pháp này khi có sự đụng độ xảy ra thì tìm kiếm vị trí trống từ kế sau phần tử bị đụng độ cho đến cuối bảng thì quay về đầu bảng 12 Xử lý đụng độ – Khai báo: const int M = 11; struct Node { int key; }; Node table[M]; int n; // số phần tử hiện có – Khởi tạo: Giả sử khóa là các số dương, khi khởi tạo ta cho trường key của các phần tử trong bảng một giá trị không thuộc tập khóa, chẳng hạn là –1 và gán số phần tử hiện có trong bảng bằng 0 13 Xử lý đụng độ void init(){ for(int i = 0; i < M; i++)table[i].key = -1;n = 0;} – Thêm một khóa vào bảng: Hàm insert() thêm một phần tử có khóa k vào bảng. Giá trị trả về của hàm là vị trí của phần tử mới thêm hoặc –1 nếu bảng bị đầy (xem ví dụ) 14 Xử lý đụng độ – Ví dụ, với M = 11 và các khóa như sau: Khóa k: 16 28 25 6 27 19 41 35 H(k): 5 6 3 6 5 8 8 2 – Như vậy, nếu gọi i là chỉ số trong bảng. Giá trị của hàm băm lại lần j trong phương pháp này là: i0 = H(k)ij = (i0 + j) % M (với j = 1, 2, . . , M - 1) 15 Xử lý đụng độ – Tìm một khóa trong bảng băm: Hàm search() tìm một khóa trong bảng băm. Trả về vị trí của khóa này nếu tìm thấy hoặc trả về –1 nếu không tìm thấy (xem ví dụ) – Nhược điểm của phương pháp này là xảy ra hiện tượng hội tụ xung quanh các địa chỉ không bị đụng độ, làm cho các khóa được băm với địa chỉ này không thể được thêm vào, dẫn đến tốc độ xử lý chậm vì phải tìm vị trí trống còn lại khi bảng gần đầy – Để khắc phục nhược điểm này, người ta sử dụng công thức tính địa chỉ là i0 = H(k)ij = (i0 + j2) % M (j > 0) 16 Xử lý đụng độ – Phương pháp trên được gọi là phương pháp thử bậc hai (quadratic probing 2. Phương pháp móc nối ngoài: – Trong phương pháp này thì mỗi vị trí trong bảng băm trỏ đến đầu danh sách liên kết của các phần tử có cùng địa chỉ trong bảng – Ví dụ, với M = 7 và các khoá như sau: Khóa k: 30 15 17 11 8 8 16 3 11 18 H(k): 2 1 3 4 1 1 2 3 4 4 17 Xử lý đụng độ 18 Xử lý đụng độ – Khai báo: const int M = 7;struct Node{ int key;Node *next;};Node *heads[M]; – Khởi tạo: Cho mảng heads chứa các phần tử mà vùng liên kết next của nó trỏ đến đầu danh sách liên kết. Lúc đầu, các vùng liên kết này trỏ đến NULL 19 Xử lý đụng độ void init() {for(int i = 0; i next = NULL;} } – Thêm một khóa vào bảng: Hàm insert() thêm phần tử có khóa k vào DSLK của bảng băm. Mỗi DSLK là một dãy các phần tử đã có thứ tự (tăng dần). Mục đích là để tìm kiếm nhanh. Nếu có nhiều khóa giống nhau thì phần tử mới thêm được chèn vào đầu DSLK (xem ví dụ) 20 Xử lý đụng độ – Tìm một khóa trong bảng: Hàm search() tìm một khóa trong bảng băm. Nếu tìm thấy, nó trả về vị trí của DSLK chứa khoá đó trong mảng heads. Ngược lại, trả về trị là –1 (xem ví dụ) – Ưu điểm của phương pháp này là xử lý đụng độ đơn giản và hiệu quả; kích thước bảng băm không cần lớn hơn các khóa được thêm vào bảng và cuối cùng là thao tác xóa một phần tử trong bảng cũng dễ dàng. Nhược điểm là cần thêm vùng nhớ cho phần liên kết của mỗi phần tử 21 Xử lý đụng độ 3. Phương pháp móc nối trong: – Để tiết kiệm vùng nhớ, một phương pháp khác là không sử dụng danh sách liên kết bên ngoài bảng băm – Bảng băm được tổ chức bởi một mảng các phần tử. Mỗi phần tử có hai vùng: Một vùng chứa khóa và một vùng chứa chỉ số (vị trí) của phần tử kế tiếp khi có sự đụng độ xảy ra – Giả sử tập khóa là dương nên ta có thể cho hai trường đó đều có giá trị là –1. Khi có sự đụng độ xảy ra, tìm vị trí trống đầu tiên trong bảng theo hướng từ cuối bảng về đầu bảng 22 Xử lý đụng độ – Ví dụ, với M = 7 và các khoá như sau: Khóa k: 30 15 17 11 8 16H(k): 2 1 3 4 1 2 23 Xử lý đụng độ –Khai báo: #include const int M = 7;struct Node{ int key;int next;};Node table[M]; int n; // chỉ số phần tử trống đầu tiên// tính từ cuối bảng 24 Xử lý đụng độ – Khởi tạo: Gán giá trị các trường key bởi một giá trị không thuộc tập khóa và các trường next bởi một giá trị không thuộc tập chỉ số của bảng. Giả sử cho các trường này được gán giá trị là –1 void init() { for(int i = 0; i < M; i++)table[i].key =table[i].next = -1;n = M - 1;} 25 Xử lý đụng độ – Thêm một khóa vào bảng băm: Hàm insert() thêm một phần tử có khóa k vào bảng. Giá trị trả về của hàm là vị trí của phần tử mới thêm vào hoặc –1 nếu bảng bị đầy. Lưu ý là nếu lần theo dây xích liên kết thì các khóa bị đụng độ sẽ không có thứ tự (xem ví dụ) – Tìm một khóa trong bảng băm: Hàm search() tìm một khóa trong bảng băm. Nếu tìm thấy, nó trả về vị trí của khóa đó. Ngược lại, trả về trị là –1 (xem ví dụ)