Phần 1
Cấu trúc của bản băm
1. Cấu trúc dữ liệu bảng băm.
- Tương tự như trong trường hợp cài đặt bằng phương phỏp nối
kết hợp nhất và các phương pháp khác.
- Phép băm ở đây cũng dựa trên ý tưởng chung: biến đổi giỏ trị
khúa thành một số (xử lý băm) và sử dụng số này để đỏnh chỉ cho bảng
dữ liệu.
- Cách xây dựng bảng băm và các phộp toỏn trờn bảng băm khác
với các cấu trúc trước đây, như: mảng, danh sách, cây nhị phân, … phần
lớn được thực hiện bằng cỏch so sỏnh giá trị của các phần tử của cấu
trúc, vì vậy thời gian truy xuất khụng nhanh và phụ thuộc vào kớch thước
của cấu trỳc. Đặc biệt khi cần phải xử lý cỏc bài toỏn cú dữ liệu lớn và
được lưu trữ ở bộ nhớ ngoài.
- Để khắc phục nhược điểm đó, cấu trúc của bảng băm tổng quát
sẽ giải quyết thông qua: tập khoá, tập địa chỉ, hàm băm.
Tập khoá K Hàm băm Tập địa chỉ M
K: Tập cỏc khoỏ (set of keys)
M: Tập cỏc dịa chỉ (set of addresses).
h(k): Hàm băm dựng để ỏnh xạ một khoỏ k từ tập cỏc khoỏ
K
thành một địa chỉ tương ứng trong tập M.
1
*
*
*
*
•
•
•
•

h(k)
ã Nếu bị xung đột thỡ hàm băm lại lần 1, hàm h1 sẽ xột địa chỉ kế
tiếp, nếu lại bị xung đột thỡ hàm băm thỡ hàm băm lại lần 2, hàm h2 sẽ
xột địa chỉ kế tiếp nữa, …, và quỏ trỡnh cứ thế cho đến khi nào tỡm được
địa chỉ trống và thờm phần tử mới vào địa chỉ này.
* Bảng băm với phương phỏp kết nối hợp nhất.
Bảng băm này được cài đặt bằng danh sỏch kề, mỗi phần tử cú hai
trường: trường key chứa khúa của phần tử và trường next chỉ phần tử kế
bị xung đột. Cỏc phần tử bị xung đột được kết nối nhau qua trường kết
nối next
* Bảng băm với phương phỏp dũ bậc hai.
Khi thờm phần tử vào bảng băm này, nếu băm lần đầu bị xung đột thỡ sẽ
dũ đến địa chi mới, ở lần dũ thứ i sẽ xột phần tử cỏch i
2
cho đến khi gặp
địa chỉ trống đầu tiờn thỡ thờm phần tử vào địa chỉ này.
* Bảng băm với phương phỏp băm kộp.
Bảng băm này dựng hai hàm băm khỏc nhau, băm lần đầu với hàm băm
thứ nhất nếu bị xung đột thỡ xột địa chỉ khỏc bằng hàm băm thứ hai.
* Bảng băm với phương pháp kết nối trực tiếp
4. Bảng băm với phương pháp kết nối trực tiếp
(Direct c haining Method)
a. ý tưởng:
1. Biến đổi giỏ trị khúa thành một số (xử lý băm) và sử
dụng số này để đỏnh chỉ cho
bảng dữ liệu.
2. Bảng băm được cài đặt bằng cỏc danh sỏch liờn kết,
cỏc phần tử trờn bảng băm được “băm” thành M danh
sỏch liờn kết (từ danh sỏch 0 đến danh sỏch M–1).
3. Các giá trị khoá được phân vào từng cụm (bucket) là

ta làm như trên rất thuận lợi cho tìm kiếm sau này nếu cần.
Danh sách liên kết được sắp xếp theo giá trị các khoá tăng
dần.). Con trỏ liên kết next cũng được cập nhật lại sao cho cỏc
phần tử bị xung đột hỡnh thành một danh sỏch liờn kết.
+ Khi tỡm một phần tử cú khúa k trong bảng băm, hàm băm f(k)
cũng sẽ xỏc định địa chỉ i trong khoảng từ 0 đến M-1 ứng với danh sỏch
liờn kết i cú thể chứa phần tử này. Như vậy, việc tỡm kiếm phần tử trờn
bảng băm sẽ được qui về bài toỏn tỡm kiếm một phần tử trờn danh sỏch
liờn kết.
+ Khi xoá một phần tử cú khúa k vào bảng băm, hàm băm f(k)
cũng sẽ xỏc định địa chỉ i trong
khoảng từ 0 đến M-1 ứng với danh sỏch liờn kết i cú thể chứa phần tử
này. Như vậy, việc xoá phần tử trờn bảng băm sẽ được qui về bài toỏn
xoá một phần tử trờn danh sỏch liờn kết.
+ éể minh họa ta xột bảng băm cú cấu trỳc như sau:
- Tập khúa K: tập số tự nhiờn
- Tập địa chỉ M: gồm 10 địa chỉ (M={0, 1, …, 9}
- Hàm băm h(key) = key % 10. Chi tiết:
Ta có tập các khoá k: 10,21,70,52,22,63,33,44,91,15,26,25,47,48,39, …
5
0
M-1
Tập địa chỉ M=10 được đánh số từ 0 đến M-1 (Từ 0 đến 9), ta được 10
danh sách liên kết khác nhau.
Bảng băm đó "băm" các phần tử trong tập khoỏ K theo 10 danh sỏch liờn
kết khỏc nhau, mỗi danh sỏch liờn kết gọi là một bucket.
Hàm băm h(k)=k mod M. Ta chèn được các giá trị khoá k tương ứng với

1
2
4
2
4
7
1
3
4
2
3
5
2
3
5
6
8
6
8
6
9
6
9
7
9
7
8
1
M = 0
M = 9

+ i=h(k)
+ kiểm tra bucket [i]: nếu rỗng => cung cấp nhớ cho bucket, gán
khoá k
thêm phần tử có khoá k vào ds theo thứ tự tăng
dần.
+ Phộp toỏn remove: Xúa phần tử cú khúa k trong bảng băm.
+ Phộp toỏn clear: Xúa tất cả cỏc phần tử trong bảng băm.
+ Phộp toỏn traversebucket: Xử lý tất cả cỏc phần tử trong bucket b.
+ Phộp toỏn traverse: Xử lý tất cả cỏc phần tử trong bảng băm.
7
+ Phộp toỏn search: Tỡm kiếm một phần tử trong bảng băm, nếu khụng
tỡm thấy hàm này trả về hàm NULL, nếu tỡm thấy hàm này trả về địa chỉ
của phần tử cú khúa k.
B1: Tỡm danh sỏch liờn kết cú thể chứa khúa k
b = h(k);
p = bucket[b];
B2: Tỡm khúa k trong danh sỏch liờn kết p.
5. Cài đặt bảng băm với phương pháp kết nối
trực tiếp
a. Khai báo cấu trúc bảng băm.

//kich thuoc cua bang bam
#define M 10
// M so nut co tren bang bam, du de chua cac nut nhap
vao bang bam
//dinh nghia cau truc cua mot nut bang bam
struct nodes
{
int key; //thanh phan 1 de luu khoa
struct nodes *next; //thanh phan thu hai con tro luu dia

for(i=0;i<M;i++)
bucket[i]=NULL;
}
* Phộp toỏn kiểm tra rỗng (empty):
Kiểm tra bucket cú rỗng khụng.
//kiem tra bucket b co bi rong hay khong
int emptybucket(int b)
{
if (bucket[b]==NULL)
return TRUE;
else
return FALSE;
}
Kiểm tra bảng băm cú rỗng khụng.
//kiem tra bang bam co rong hay khong?
int empty()
9
{
int b;
for(b=0;b<M;b++)
if (bucket[b]!=NULL)
return FALSE;
}
* Phộp toỏn chốn phần tử mới vào bảng băm
(insert):
Thờm phần tử cú khúa k vào bảng băm.
//phep toan insert
//them vao mot key moi
void insert(int k)
{

bucket[b]=p;
}
//Ham insafter them nut moi vao bucket sau nut p
void insafter(NODEPTR p,int k)
{
NODEPTR q;
if (p==NULL)
printf("Khong them nut moi duoc");
else
{
q=getnode();
q->key=k;
q->next=p->next;
p->next=q;
}
}
* Phộp toỏn tỡm kiếm (search):
Để tỡm một phần tử cú khúa k trong bảng băm, hàm băm
f(k) sẽ xỏc định địa chỉ i trong khoảng từ 0 đến M-1 ứng
với danh sỏch liờn kết i cú thể chứa phần tử này. Như vậy,
việc tỡm kiếm phần tử trờn bảng băm sẽ được qui về bài
toỏn tỡm kiếm một phần tử trờn danh sỏch liờn kết.
Nếu khụng tỡm thấy hàm này trả về hàm NULL, nếu tỡm
thấy hàm này trả về địa chỉ của phần tử cú khúa k.
int search(int k)
{
NODEPTR p;
11
int b;
b=hashfunc(k);

p=p->next;
}
if (p==NULL)
printf("\nKhong co nut co khoa %d",k);
12
else
if(p==bucket[b])
pop(b);
else
delafter(q);
}
Phần 2
Đánh giá độ phức tạp của thuật toán
Ta có bảng băm T với m vị trí (m bucket) để lưu trữ n giá trị.
Ta có hệ số phép tính trung bình về sự phân bố các giá trị là: α = n/m.
* Thủ tục chính:
Chained-Hash-Insert (T, x)
Insert x đầu mỗi danh sách T[h(key[x])].
Thời gian xấu nhất để hoàn thành là – O(1).
Chained-Hash-Delete (T, x)
Xoá x khỏi danh sách T[h(key[x])].
Thời gian xấu nhất để hoàn thành, phụ thuộc vào độ dài của
mỗi danh sách.
Nếu là danh sách móc nối kép (đồng nghĩa với việc ta chọn m=n)
thì sẽ là _ O(1)
Chained-Hash-Search (T, k)
Tìm khoá k trong danh sách T[h(k)].
Khoảng thời gian xấu nhất để hoàn thành, phụ thuộc vào độ dài của mỗi
danh sách.
13

được lưu vào một danh sách liên kết.
X
ij
= i{h(k
i
) = h(k
j
)}, với mọi i, j.
X
ij:
Chỉ ra vị trí của các khoá k tại địa chỉ thứ i
trong cùng một danh sách liên kết thứ j,
(trong cùng bucket j, với j = 0, 1, 2, m-1)
+ Để đơn giản không giảm tính tổng quát với trường hợp này
ta có:
14
Pr{h(k
i
) = h(k
j
)} = 1/m

E[X
ij
] = 1/m
Vậy tổng thời gian tìm kiếm mất: 15
n

n
i
n
ij
ij
22
1
2
1
1
2
)1(1
1
1
1
)(
1
1
1
1
1
][1
1
1
1
2
1 1
1
1 1
1 1









+=














+
∑ ∑
∑
∑ ∑
∑ ∑
∑ ∑
= =















+
∑ ∑
= +=
n
i
n
ij
ij
X
n
E
1 1
1
1
+ Ta chọn M sao cho tương đối nhỏ vì không phải sử dụng
một vùng nhớ liên tục, nhưng giá trị của M cũng phải đủ lớn để tránh sự

truy xuất rất chậm.
Tài liệu tham khảo
1. Nguyễn Kim Anh. Nguyên lý của các hệ cơ sở dữ liệu, NXB éại
học Quốc gia HN, 2004.
2. Đào Thanh Tĩnh. Cấu trúc dữ liệu và giải thuật_Tài liệu ôn thi
cao học nghành Công nghệ thông tin, Học viện kỹ thuật quân sự,
2005.
3. éỗ Xuõn Lụi, Cấu trúc dữ liệu và giải thuật, NXB éại học Quốc
gia HN, 2005.
4. Nguyễn Trung Trực. Cấu trúc dữ liệu, Trường éại học bỏch khoa
TP. HCM, 1994.
5. Daniel F. Stubbs & Neil W. Webre. Data Structures with
Abstract Data types and Ada. PWS Publishing Company,
1993: 375-382.
A conceptual definition of Perfect Hashing Function
6. Edward M. Reingold & Wilfred J. Hansen. Data structures.
Little, Brown Computer series, 1983.
18
Comparisons of hashing by chaining with other
algorithms
7. Mitchell, L. Model. Data Abstraction, and Data Structures.
Prentice-Hall, Inc, 1994: 383-390.
An overview of chaining and Buckets
8. Adam Drozdek & Donald L. Simon. Data structure in C.
PWS Publishing Co.,1995: 376-399
An example of hashing application written in C
9. J. Pierprzyk Babak Sadeghiyan. Design of Hashing Algorithms.
Lecture Notes in Computer Science, G. Goos & J.
Hartmanis, Springer-Verlag, 1995.
An overview of hash functions.