BẢNG BĂM (Hashing Table)

Giả sử ta có 100 số nguyên có giá trị bất kỳ nằm trong khoảng từ 0 . . 999 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 Tuy nhiên, chỉ có 1/10 bộ nhớ được sử dụng, dẫn đến lãng phí bộ nhớ 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...
Nội dung trích xuất từ tài liệu:
BẢNG BĂM (Hashing Table)BẢNG BĂM(Hashing Table) Chương 5 1Khái niệmGiả sử ta có 100 số nguyên có giá trị bất kỳnằm trong khoảng từ 0 . . 999Nế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] = ithì số lần tìm kiếm số nguyên bất kỳ trong100 số này là 1 lầnTuy nhiên, chỉ có 1/10 bộ nhớ được sửdụng, dẫn đến lãng phí bộ nhớPhép biến đổi khóa là phương pháp thamkhả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ọctrên những khoá để có được địa chỉ tươngứng của những phần tử ở trong bảng 2Khái niệm 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ớ 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) Để 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 3Khá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 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 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 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 4Xây dựng hàm băm 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 5Xâ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 6Xâ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 7Xây dựng hàm băm Tại sao kích thước M của bảng phải là số nguyên tố? Để 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 8Xây dựng hàm băm 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 = (((anx + 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 9Xây dựng hàm băm 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 10Xử lý đụng độ 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 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 11Xử 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 ...