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
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
3
Kh
Kh
á
á
i ni
i ni
ệ
ệ
m
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
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
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
5
Xây d
Xây d
ự
ự
ng h
ng h

à
à
m băm
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
6
Xây d
Xây d
ự
ự
ng h
ng h
à
à

m băm
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
7
Xây d
Xây d
ự
ự
ng h
ng h
à
à
m băm
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 * 32
2
+4*32
1
+24*32
0
= 10392
Do đó, chỉ

số

của khóa AKEY trong bảng
là:

10392 % 101 = 90
8
Xây d
Xây d
ự
ự

ng h
ng h
à
à
m băm
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 * 32
2
+4*32
1
+24*32
0
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
9
Xây d
Xây d
ự
ự
ng h
ng h
à
à
m băm
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 = (((a

n
x+a
n-1
)x + a
n-2
)x +
+a
0
)
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
Xây d
ự
ự
ng h
ng h
à
à
m băm
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
X
ử
ử
lý đ
lý đ
ụ
ụ
ng đ
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
X
ử
ử
lý đ
lý đ
ụ
ụ
ng đ
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
X
ử
ử
lý đ
lý đ
ụ
ụ
ng đ
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
X
ử
ử
lý đ
lý đ
ụ
ụ

ng đ
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à:
i
0
= H(k)
i

j
=(i
0
+j)%M (với j = 1, 2, . . , M-1)
15
X
X
ử
ử
lý đ
lý đ
ụ
ụ
ng đ
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à
i
0
= H(k)
i
j
=(i
0
+j
2
)%M (j>0)
16
X
X
ử
ử
lý đ
lý đ
ụ
ụ
ng đ
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
X
ử
ử
lý đ

lý đ
ụ
ụ
ng đ
ng đ
ộ
ộ
18
X
X
ử
ử
lý đ
lý đ
ụ
ụ
ng đ
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
X
ử
ử
lý đ
lý đ
ụ
ụ
ng đ
ng đ
ộ
ộ
void init() {
for(int i = 0; i < M; i++)
{
heads[i]= new Node;
heads[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
X
ử
ử
lý đ

lý đ
ụ
ụ
ng đ
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
X

ử
ử
lý đ
lý đ
ụ
ụ
ng đ
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
X
ử
ử
lý đ
lý đ
ụ
ụ
ng đ
ng đ
ộ
ộ
– Ví


dụ, với M = 7 và

các khoá như sau:
Khóa k:
30 15 17 11 8 16
H(k):
2 1 3 4 1 2
23
X
X
ử
ử
lý đ
lý đ
ụ
ụ
ng đ
ng đ
ộ
ộ
–Khai báo:
#include <iostream.h>
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
X
ử
ử
lý đ
lý đ
ụ
ụ
ng đ
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
X
ử
ử
lý đ
lý đ
ụ
ụ
ng đ
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ụ)