1
B
BẢ
ẢNG BĂM
NG BĂM
(Hashing Table)
(Hashing Table)
Chương 5
2
Kh
Khá
ái ni
i niệ
ệm
m
zGiảsửta có 100 sốnguyên có giá trịbất kỳ
nằm trong khoảng từ0. . 999
zNếu sửdụng mảng agồ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
zTuy nhiên, chỉcó 1/10 bộnhớ được sử
dụng, dẫn đến lãng phí bộnhớ
zPhé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
3
Kh
Khá
ái ni
i niệ
ệm
m
zPhé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ớ
zTổ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
4
Kh
Khá
ái ni
i niệ
ệm
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
zVấ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
zYê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
zCó 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
5
Xây d
Xây dự
ựng h
ng hà
àm băm
m băm
zPhươ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