Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 5: Bảng băm (Hashtable) - Đỗ Ngọc Như Loan

Bảng băm (Hashtable) 
GV: Đỗ Ngọc Như Loan 
Khái niệm 
Bảng băm là một cấu trúc dữ liệu có thể lưu trữ một tập các đối tượng có số phần tử tùy ý 
Các thao tác tìm kiếm, chèn, xoá trên bảng băm rất hiệu quả 
Phần tử có khoá k (nguyên) được lưu trữ trong slot h(k), trong đó h là hàm băm (hash function) từ tập U các khóa đến tập các slot của bảng băm T[0..m-1] 
Khái niệm 
Hàm băm có dạng h: U → {0,1,..., m-1}, m là kích thước của bảng băm 
h(k) là giá trị băm (hash value) của khoá k hay còn nói phần tử có khoá k băm slot h(k) 
Với hàm băm chỉ cần xử lý m giá trị thay vì |U| giá trị 
Bảng băm 
Có thể có sự dụng độ (collision) lưu trữ các khóa, ví dụ k2 dụng độ k5, nghĩa là h(k2)= h(k5) 
Các phương pháp giải quyết đụng độ 
Thiết kế hàm băm h(U) phân bố đều trên T (không triệt để) 
Giải quyết dụng độ bằng danh sách liên kết c ollision resolution by chaining) 
Giải quyết dụng độ bằng địa chỉ mở (open addressing) 
GiẢI QUYẾT ĐỤNG ĐỘ BẰNG KẾT NỐI 
Đặt tất cả các phần tử có cùng giá trị hàm băm vào một danh sách liên kết 
Slot j chứa pointer chỉ đến đầu của danh sách liên kết của tất cả các phần tử được lưu trữ có hàm băm là j 
Nếu không có khóa k để h(k)=j thì thì slot j trỏ đến N UL L 
ĐỊNH NGHĨA BẢNG BĂM 
Định nghĩa bảng băm trong C++, các khóa là số nguyên 
typedef struct CELL *LIST; 
struct CELL { 
	int key; 
	LIST next; 
}; 
typedef LIST TABLE[MAX]; 
TABLE T; 
int m; //Kích thước bảng băm 
CÁC THAO TÁC 
HashInitialize(T): Khởi tạo bảng băm 
HashInsert(T, k): Chèn một phần tử có khóa k vào bảng băm T 
HashSearch(T, k): Tìm một phần tử có khoá k trong T 
HashDelete(T, k): Xoá một phần tử có khóa k khỏi T 
HashInitialize 
void HashInitialize(TABLE &T,int &m) // m là kích thước 
{ 	 // bảng băm 
	for(int i=0; i<m;i++) 
	T[i]=NULL; 
} 
HashInsert 
void HashInsert(TABLE &T, int m, int k) 
{ 
	ListInsert(T[Hash(k, m)], k); 
} 
int Hash(int k, int m) //hàm băm 
{ 
	return k%m; 
} 
HashSearch 
LIST HashSearch(TABLE T, int k, int m) 
{ 
	return ListSearch(T[Hash(k,m)], k); 
} 
HashDelete 
void HashDelete(TABLE & T, int m, int k) 
{ 
	ListDelete(T[Hash(k,m)], k); 
} 
ĐỘ PHỨC TẠP 
HashInsert(T, k) có T(n) = O(1) 
HashSearch(T, k) và HashDelete(T, k) có độ phức tạp trung bình T(n) = O(n/m), trong đó m là kích thước bảng băm 
HÀM BĂM 
Một hàm băm là tốt nếu h(k) có thể là bất kỳ slot nào trên bảng băm 
Trong ứng dụng cần tìm các hàm băm thích hợp 
Luôn giả sử mỗi khoá là một số tự nhiên 
Có một số cách xây dựng hàm băm như: phương pháp chia (division method), phương pháp nhân (multiplication method) v.v 
HÀM BĂM 
Với phương pháp chia, tạo hàm băm bằng cách đặt tương ứng mỗi khoá k với số dư trong phép chia k cho số slot m 
Vậy h(k) = k mod m 
Tập các khoá được chia thành m lớp 
Nên chọn m là số nguyên tố không quá gần với lũy thừa của 2 
HÀM BĂM 
Phương pháp nhân, hàm băm có dạng: 
	 h(k) = ,A là hằng thỏa 0 < A <1 
	 Với k A mod 1 = kA- 
Phương pháp này không hạn chế việc chọn m 
Ví dụ A = 	 0.61803 và k =123456, m =10000, 
Thì 
h(k) = 
= 
= 
= 41 
Yêu cầu: Cho dãy số nguyên dương gồm n số đôi một khác nhau và số k . Hãy kiểm tra xem có giá trị k trong dãy không? 
Input: Dữ liệu vào từ file HASH .INP gồm 2 dòng: 
+ Dòng 1: Gồm 2 số nguyên n và k (n<=1000) 
+ Dòng 2 chứa dãy số nguyên n phần tử 
Output: Xuất ra file HASH .OUT , g ồm 1 dòng chứa YES nếu tìm được, NO nếu không tìm được. 
Ví dụ: 
HASH. INP 
8 19 
1 5 8 1 1 3 4 22 19 30 
HASH .OUT 
YES 
Giải bài toán này bằng cách sử dụng BẢNG BĂM (có thể dùng số slot m = 11)