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 những khoá để có được địa chỉ tương ứng của những phần tử ở trong bảng
25 trang |
Chia sẻ: haohao89 | Lượt xem: 2776 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Bài giảng chương 5: Bảng băm (hashing table), để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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ụ)