Bài giảng Cấu trúc dữ liệu nâng cao - Chương 2: Bảng băm

 chỉ này.
Khi tìm môt nút có khóa key trong bảng băm thì xét nút tại
địa chỉ i=f(key), nếu chưa tìm thấy thì xét nút cách i 
12,22,…,quá trình cứ thế cho đến khi tìm được khóa(trường
hợp tìm thấy) hoặc rơi vào địa chỉ trống(trường hợp không
tìm thấy).
13-Dec-05 Trương Hải Bằng-Câu trúc dữ liệu 2 42
Phương pháp dò bậc hai (3)
Hàm băm lại của phương pháp dò bậc hai là truy
xuất các địa chỉ cách bậc 2.
Hàm băm lại hàm fi được biểu diễn bằng công thức
sau:
fi(key)=( f(key) + i2 ) % M với f(key) là hàm băm
chính của bảng băm.
Nếu đã dò đến cuối bảng thì trở về dò lại từ đầu
bảng.
Bảng băm với phương pháp do bậc hai nên chọn số
địa chỉ M là số nguyên tố.
13-Dec-05 Trương Hải Bằng-Câu trúc dữ liệu 2 43
0 10 0 10 0 10 0 10 0 10
1 NULL 1 20 1 20 1 20 1 20
2 NULL 2 NULL 2 NULL 2 NULL 2 36
3 NULL 3 NULL 3 NULL 3 NULL 3 NULL
4 NULL 4 NULL 4 30 4 30 4 30
5 15 5 15 5 15 5 15 5 15
6 16 6 16 6 16 6 16 6 16
7 NULL 7 NULL 7 NULL 7 26 7 26
8 NULL 8 NULL 8 NULL 8 NULL 8 NULL
9 NULL 9 NULL 9 25 9 25 9 25
Thêm vào các khóa 10, 15, 16, 20, 30, 25, ,26, 36
13-Dec-05 Trương Hải Bằng-Câu trúc dữ liệu 2 44
Phương pháp dò bậc hai (tt)
//Khai bao nut cua bang bam
typedef struct
{
int key; //Khoa cua nut tren bang 
bam
}NODE;
//Khai bao bang bam co M nut
NODE HASHTABLE[M];
int N;
//Bien toan cuc chi so nut hien co tren bang bam
13-Dec-05 Trương Hải Bằng-Câu trúc dữ liệu 2 45
Phương pháp dò bậc hai (tt)
Hàm băm:
Giả sử chúng ta chọn hàm băm dạng%: f(key)=key %10.
Tương tự các hàm băm nói trên
Chúng ta có thể dùng một hàm băm bất kì tahy cho hàm băm dạng % 
trên.
Phép toán initialize
Gán tất cả các phần tử trên bảng có trường key là NULLKEY.
Gán biến toàn cục N=0.
void initialize()
{
int i;
for(i=0; i<M;i++)
HASHTABLE[i].key = NULLKEY;
N=0; //so nut hien co khoi dong bang 0
} 
13-Dec-05 Trương Hải Bằng-Câu trúc dữ liệu 2 46
Phương pháp dò bậc hai (tt)
Phép toán search:
Tìm phần tử có khóa k trên bảng băm,nếu không tìm thấy hàm này trả về trị M, 
nếu tìm thấy hàm này trả về địa chỉ tìm thấy.
int search(int k)
{
int i, d;
i = hashfuns(k);
d = 1;
while(HASHTABLE[i].key!=k&&HASHTABLE[i].key!=NULLKEY)
{
//Bam lai (theo phuong phap bac hai)
i = (i+d) % M;
d = d+2;
}
if(HASHTABLE[i].key ==k) 
return i;
retiurn M;
13-Dec-05 Trương Hải Bằng-Câu trúc dữ liệu 2 47
Phương pháp dò bậc hai (tt)
Phép toán insert:
Thêm phần tử có khoá k vào bảng băm.
int insert(int k)
{ 
int i, d;
i = hashfuns(k);
d = 1;
if(search(K)<M) return M;//Trùng khoá
if(full( ))
{
printf(“\n Bang bam bi day khong them nut co 
khoa %d duoc”,k);
return;
}
13-Dec-05 Trương Hải Bằng-Câu trúc dữ liệu 2 48
Phương pháp dò bậc hai (tt)
i=HF(k);
while(HASHTABLE[i].key !=NULLKEY)
{
//Bam lai (theo phuong phap bac hai)
i = (i+d) % M;
d = d+2;
}
HASHTABLE[i].key=k;
N=N+1;
return(i);
}
13-Dec-05 Trương Hải Bằng-Câu trúc dữ liệu 2 49
Phương pháp dò bậc hai (tt)
Nhận xét bảng băm dùng phương pháp dò
bậc hai:
Nên chọn số địa chỉ M là số nguyên tố. Khi khởi động bảng
băm thì tất cả M trường key được gán NULL, biến toàn cục
N được gán 0.
Bảng băm đầy khi N = M-1, và nên dành ít nhất một phần
tử trống trên bảng băm.
Bảng băm này tối ưu hơn bảng băm dùng phương pháp dò
tuyến tính do rải rác phần tử đều hơn, nếu bảng băm chưa
đầy thì tốc độ truy xuất có bậc 0(1). Trường hợp xấu nhất
là bảng băm đầy vì lúc đó tốc độ truy xuất chậm do phải
thực hiện nhiều lần so sánh.
13-Dec-05 Trương Hải Bằng-Câu trúc dữ liệu 2 50
Phương pháp băm kép
Mô tả:
- Cấu trúc dữ liệu: Bảng băm này dùng hai hàm
băm khác nhau với mục đích để rải rác đều các
phần tử trên bảng băm.
Chúng ta có thể dùng hai hàm băm bất kì, ví dụ
chọn hai hàm băm như sau:
f1(key)= key %M.
f2(key) =(M-2)-key %(M-2).
bảng băm trong trường hợp này được cài đặt bằng
danh sách kề có M phần tử, mỗi phần tử của bảng
băm là một mẫu tin có một trường key để lưu khoá
các phần tử.
13-Dec-05 Trương Hải Bằng-Câu trúc dữ liệu 2 51
Phương pháp băm kép (tt)
- Khi khởi động bảng băm,tất cả trường kay được
gán NULL.
- Khi thêm phần tử có khoá key vào bảng băm, thì
i=f1(key) và j=f2(key) sẽ xác định địa chỉ i và j 
trong khoảng từ 0 đến M-1:
Nếu chưa bị xung đột thì thêm phần tử mới tại địa
chỉ i này.
Nếu bị xung đột thì hàm băm lại lần 1 f1 sẽ xét địa
chỉ mới i+j, nếu lại bị xung đột thì hàm băm lại lần
2 là f2 sẽ xét địa chỉ i+2j, …, quá trình cứ thế cho
đến khi nào tìm được địa chỉ trống và thêm phần tử
vào địa chi này.
13-Dec-05 Trương Hải Bằng-Câu trúc dữ liệu 2 52
0 10 0 10 0 10 0 10 0 10
1 NULL 1 NULL 1 NULL 1 20 1 20
2 NULL 2 NULL 2 30 2 30 2 26
3 NULL 3 NULL 3 NULL 3 NULL 3 36
4 NULL 4 20 4 NULL 4 NULL 4 20
5 15 5 15 5 15 5 15 5 15
6 16 6 16 6 16 6 16 6 16
7 NULL 7 NULL 7 NULL 7 NULL 7 NULL
8 NULL 8 NULL 8 NULL 8 26 8 NULL
9 NULL 9 NULL 9 25 9 25 9 25
Băm kép
Thêm vào các khóa 10, 15, 16, 20, 30, 25, 26, 36 :
13-Dec-05 Trương Hải Bằng-Câu trúc dữ liệu 2 53
Phương pháp băm kép (tt)
- Khi tìm kiếm một phần tử có khoá key 
trong bảng băm, hàm băm i=f1(key) và
j=f2(key) sẽ xác định địa chỉ i và j trong
khoảng từ 0 đến M-1. Xét phần tử tại địa chỉ
i, nếu chưa tìm thấy thì xét tiếp phần tử
i+ji+2j, …, quá trình cứ thế cho đến khi nào
tìm được khoá (trường hợp tìm thấy) hoặc bị
rơi vào địa chỉ trống (trường hợp không tìm
thấy).
13-Dec-05 Trương Hải Bằng-Câu trúc dữ liệu 2 54
Phương pháp băm kép (tt)
//Khai bao phan tu cua bang bam
typedef struct
{
int key; //khoa cua nut tren bang bam
}NODE;
//khai bao bang bam co M nut
struct node HASHTABLE[M];
int N;
//bien toan cuc chi so nut hien co tren bang bam
13-Dec-05 Trương Hải Bằng-Câu trúc dữ liệu 2 55
Phương pháp băm kép (tt)
Hàm băm:
Giả sử chúng ta chọn hai hàm băm dạng %:
f1(key0=key %M va f2(key) =M-2-key%(M-2).
//Ham bam thu nhat
int HF(int key)
{
return(key%M);
}
//Ham bam thu hai
int HF2(int key)
{
return(M-2 – key%(M-2));
}
13-Dec-05 Trương Hải Bằng-Câu trúc dữ liệu 2 56
Phương pháp băm kép (tt)
Phép toán initialize :
Khởi động bảng băm.
Gán tất cả các phần tử trên bảng có trường key là NULL.
Gán biến toàn cục N = 0.
void initialize()
{
int i;
for (i = 0 ; i<M ; i++ )
HASHTABLE [i].key = NULLKEY;
N = 0;// so nut hien co khoi dong bang 0
}
13-Dec-05 Trương Hải Bằng-Câu trúc dữ liệu 2 57
Phương pháp băm kép (tt)
Phép toán empty :
Kiểm tra bảng băm có rỗng không.
int empty() .
{
return (N == 0 ? TRUE : FALSE) ;
}
Phép toán full :
Kiểm tra bảng băm đã đầy chưa.
int full() .
{
return (N == M-1 ? TRUE : FALSE) ;
}
Lưu ý bảng băm đầy khi N=M-1, chúng ta nên dành ít nhất một phần tử
trống trên bảng băm.
13-Dec-05 Trương Hải Bằng-Câu trúc dữ liệu 2 58
Phương pháp băm kép (tt)
Phép toán search :
int search(int k)
{
int i, j ;
i = HF (k);
j = HF2 (k);
While (HASHTABLE [i].key!=k &&HASHTABLE [i] .key ! = 
NULLKEY)
i = (i+j) % M ; //bam lai (theo phuong phap bam kep)
if (HASHTABLE [i]).key == k) // tim thay
return (i) ;
else // khong tim thay
return (M) ;
}
13-Dec-05 Trương Hải Bằng-Câu trúc dữ liệu 2 59
Phương pháp băm kép (tt)
Phép toán insert :
Thêm phần tử có khoá k vào bảng băm.
int insert(int k)
{
int i, j;
if(search(k)<M) return M;//trùng khóa
if (full () )
{
printf (“Bang bam bi day”) ;
return (M) ;
}
13-Dec-05 Trương Hải Bằng-Câu trúc dữ liệu 2 60
Phương pháp băm kép (tt)
if (search (k) < M)
{
printf (“Da co khoa nay trong bang bam”) ;
return (M) ;
}
i = HF (k) ;
j = HF 2 (k) ;
while (HASHTABLE [i].key ! = NULLEY)
// Bam lai (theo phuong phap bam kep)
i = (i + j) % M;
HASHTABLE [i].key = k ;
N = N+1;
return (i) ;
}
13-Dec-05 Trương Hải Bằng-Câu trúc dữ liệu 2 61
Tóm tắt về bảng băm
Bảng băm đặt cơ sở trên mảng.
Phạm vi các giá trị khóa thường lớn hơn kích thước của
mảng.
Một giá trị khóa được băm thành một chỉ mục của mảng
bằng hàm băm.
Việc băm một khóa vào vào một ô đã có dữ liệu trong mảng
gọi là sự đụng độ.
Sự đụng độ có thể được giải quyết bằng hai phương pháp
chính: Phương pháp nối kết và phương pháp băm lại.
13-Dec-05 Trương Hải Bằng-Câu trúc dữ liệu 2 62
Tóm tắt về bảng băm (tt)
Trong phương pháp băm lại, các mục dữ liệu được băm vào
các ô đã có dữ liệu sẽ được đưa vào ô khác trong mảng.
Trong phương pháp nối kết, mỗi phần tử trong mảng có một
danh sách liên kết. Các mục dữ liệu được băm vào các ô sẽ
được đưa vào danh sách ở ô đó.
Vấn đề Hàm băm
a. Hàm băm dùng phương pháp chia: h(k) = k mod m
m là kích thước bảng băm, k là khóa.
b. Hàm băm dùng phương pháp nhân: h(k) = ⎣m(k A mod 1)⎦
Knuth đề nghị A = 0.6180339887
13-Dec-05 Trương Hải Bằng-Câu trúc dữ liệu 2 63
Tóm tắt về bảng băm (tt)
Kích thöôùc baûng baêm PP chia PP Nhaân
200 698 699
512 470 466
997 309 288
1024 301 292
Theo bảng trên kết qủa cho thấy kích thước bảng
băm tỷ lệ nghịch với số lần đụng độ. Số đụng độ còn
phụ thuộc vào phương pháp sử dụng hàm băm.
Hệ số tải là tỉ số giữa các mục dữ liệu trong một bảng
băm với kích thước của mảng.
Hệ số tải cực đại trong phương pháp băm lại khoảng
0,5. Đối với băm kép ở Hệ số tải này (0,5), các phép
tìm kiếm sẽ có chiều dài thăm dò trung bình là 2.
13-Dec-05 Trương Hải Bằng-Câu trúc dữ liệu 2 64
Tóm tắt về bảng băm (tt)
Trong phương pháp băm lại , thời gian tìm
kiếm sẽ là vô cực khi hệ so tải đạt đến 1.
Điều quan trọng trong phương pháp băm lại
là bảng băm không bao giờ được quá đầy.
Phương pháp nối kết thích hợp với hệ so tải
là 1.
Với hệ số tải này, chiều dài thăm dò trung
bình là 1,5 khi phép tìm thành công, và là
2.0 khi phép tìm thất bại.
13-Dec-05 Trương Hải Bằng-Câu trúc dữ liệu 2 65
Tóm tắt về bảng băm (tt)
Chiều dài thăm dò trong phương pháp
nối kết tăng tuyến tính theo hệ số tải.
Kích thước của bảng băm thường là số
nguyên tố. Điều này đặc biệt quan
trọng trong thăm dò bậc hai và trong
phương pháp nối kết.
Các bảng băm có thể dùng cách lưu trữ
ngoại. Một cách để thực hiện việc này là
cho các phần tử trong bảng băm chứa
số lượng các khối của tập tin trên đĩa