Bài giảng Thiết kế và đánh giá thuật toán - Bảng băm - Lê Nguyên Khôi

Thiết Kế & Đánh Giá Thuật Toán
Bảng Băm
TS. Lê Nguyên Khôi
Trường Đại Học Công Nghệ - ĐHQGHN
Nội Dung

 Phương pháp băm

 Hàm băm

 Giải quyết va chạm
1
Bài Toán Từ Điển

 Dùng tập động cài đặt từ điển

 Mỗi phần tử là cặp (khóa, dữ liệu)

 Có thể tìm theo khóa

 Được sắp xếp hoặc không

 Chỉ quan tâm tới

 Tìm kiếm SEARCH (, )

 Chèn INSERT (, )

 Xóa DELETE (, )

 Tổ chức cấu trúc dữ liệu  như thế nào?
2
Bài Toán Từ Điển

 Nếu khóa của dữ liệu là số nguyên không âm
trong khoảng 0	 − 1 , phân biệt

 Có thể sử dụng mảng cỡ 	

 Dữ liệu khóa  lưu tại  

 Tìm kiếm, chèn, xóa trong thời gian (1)

 Thực tế không khả thi

 Số phần tử dữ liệu có thể rất nhỏ so với 	

số 64-bit thể hiện 2 (18 × 10) khóa khác nhau

Xâu ký tự thậm chí còn lớn hơn

 Khóa có thể không phải số nguyên

 Tận dụng phép truy cập trực tiếp của mảng
3
Phương Pháp Băm

 Lưu dữ liệu trong mảng  0 − 1

 Hàm băm ℎ: ánh xạ mỗi giá trị khóa  của dữ
liệu tới một chỉ số  (0 ≤  < )

 Dữ liệu sẽ được lưu trong []

 ℎ:  → {0, 1,  , − 1}
4
0
1
i
 − 1
Tính
địa chỉ
Tập các giá trị khoá
Hàm băm ℎ
Mảng 
Phương Pháp Băm

 Nếu có  ≠ " thì ℎ() ≠ ℎ("), và tính
chỉ số ℎ() trong thời gian (1)

 thì các phép toán tìm kiếm, chèn, xóa cũng
trong thời gian (1)

 Tuy nhiên, thường xảy ra va chạm

 Chèn khóa vào vị trí đã có khóa khác

 Thực tế  ≠ " có thể cho ℎ  = ℎ(")
5
Hàm Băm

 Khó xác định phương pháp băm đồng đều
đơn giản.

 Hàm băm tốt

 Phân bố khóa đồng đều vào các vị trí

 Tính nhanh & dễ dàng

 Đảm bảo ít va chạm

 Khóa là số nguyên không âm

 Phương pháp chia

 Phương pháp nhân

 Khóa là xâu ký tự

 Đổi xâu thành số nguyên không âm
6
Hàm Băm – Phương Pháp Chia
ℎ  = 		mod	

 Nhạy cảm với cỡ của bảng băm ()

 Chọn  để hạn chế xảy ra va chạm

 Không chọn  có ước số nhỏ

 Số nguyên tố có dạng đặc biết, ví dụ 4) + 3

 Ví dụ: nếu  = 2,, hàm băm không phụ
thuộc vào tất cả các bit của 

  = 1011000111-..-.-" và / = 6, thì
ℎ  = -..-.-"
7
Hàm Băm – Phương Pháp Nhân
 = 2,, với máy tính 1-bit. Hàm băm: 
ℎ() 	= 	 (2 · 	mod	24)	rsh	(1– /)

 rsh là toán tử “bitwise right-shift”

 Toán tử rsh nhanh

 2 là số lẻ trong khoảng 249 < 2 < 24

 Không chọn 2 quá gần 249 hoặc 24

 Phép nhân và phép chia dư 24 nhanh
hơn phép chia
8
Hàm Băm – Phương Pháp Nhân
ℎ() 	= 	 (2 · 	mod	24)	rsh	(1– /)	

 : = 2, = 8 = 2; với máy tính 1 = 7-bit
1011001 = 2
1101011 = 
10010100110011
ℎ  = 011
9
Hàm Băm – Xâu Ký Tự

 Đổi ký tự thành số nguyên (bảng ASCII)

 Khi đó xâu ký tự là số trong hệ cơ số 128

 Chuyển sang hệ 10

 Nhược điểm: xâu dài cho kết quả vượt quá
khả năng biểu diễn của máy tính

 Cải tiến:

 Xâu ký tự thường được tạo thành từ 26 chữ
cái, 10 chữ số, và một số ký tự khác

 Thay 128 thành 37
10
Giải Quyết Va Chạm

 Nếu dữ liệu = với khóa  đã được lưu tại  
với ℎ  = . Cần thêm dữ liệu =" với khóa "

 Nếu ℎ " = , xảy ra va chạm, =" lưu ở đâu?

 Các phương pháp

 Dây chuyền

Tạo một danh sách lưu tất cả dữ liệu có cùng
vị trí 

 Địa chỉ mở

Tìm vị trí khác còn trống trong bảng và cho dữ
liệu mới vào đó
11
Giải Quyết Va Chạm – Dây Chuyền

 Tại mỗi vị trí trong bảng băm  là một danh
sách liên kết các dữ liệu có cùng giá trị băm 

 Ưu điểm:

 Số dữ liệu lưu không phụ thuộc vào cỡ của mảng

 Thời gian các phép toán tìm kiếm, chèn, xóa?
12

Hàm
băm
Dây Chuyền – Phân Tích Thời Gian

 Trường hợp xấu nhất:

 Tất cả các khóa được băm vào cùng vị trí

 Thời gian tìm kiếm > ?

 Trường hợp trung bình:

Mỗi khóa  có thể được băm vào bất cứ vị trí
nào trong , độc lập với việc các khóa khác
được băm như thế nào
13
Dây Chuyền – Phân Tích Trung Bình

 Trường hợp trung bình: băm đồng đều
? số lượng khóa trong bảng
 độ lớn của bảng
Hệ số tải của bảng băm 
@ =
A
B
= số lượng khóa trung bình tại mỗi
vị trí trong bảng băm 
14
Dây Chuyền – Tìm Kiếm Trung Bình
Thời gian tìm kiếm không thành công
= > 1 + @
Thời gian tìm kiếm là > 1 nếu @ = > 1
Thời gian tìm kiếm thành công có tiệm cận
tương tự
15
Hàm băm
Truy cập vị trí
Tìm kiếm
danh sách
Giải Quyết Va Chạm – Địa Chỉ Mở

 Khi xảy ra va chạm, tìm vị trí khác còn trống
trong bảng và cho dữ liệu mới vào đó

 Dãy các vị trí được tìm gọi là dãy thăm dò

 Bảng băm có thể bị đầy

 Xác định dãy thăm dò

 Tuyến tính

Dãy thăm dò: ,  + 1,  + 2, 

 Bình phương

Dãy thăm dò: ,  + 1",  + 2", 

 Băm kép

Dãy thăm dò: ℎ() + :ℎ"() với : = 0,1,2,
16
Bài Tập
 = 11, Phương pháp chia, Thăm dò tuyến tính
insert(388) search(47) 
insert(130) delete(926)..
insert(13) search(47)
insert(14) delete(388)
insert(926) search(926)
insert(47)
17
Thăm Dò – Nhận Xét

 Tuyến tính

 Ưu điểm: xét tất cả các vị trí trong mảng

 Phép chèn luôn thực hiện được, trừ khi mảng đầy

 Nhược điểm:

 Dữ liệu tập trung thành các đoạn

 Tìm kiếm tuần tự trong từng đoạn

 Bình phương

 Ưu điểm: tránh nhược điểm thăm dò tuyến tính

 Nhược điểm: không xét tất cả các vị trí trong mảng

 Phép chèn có thể không thực hiện được

 Băm kép

 Nếu cỡ của mảng và bước thăm dò ℎ"() nguyên tố
cùng nhau thì cho phép tìm đến tất cả các vị trí trong
mảng
18