Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 7: Bảng băm" cung cấp cho người học các kiến thức: Khái niệm bảng băm, đặc điểm và cấu trúc, một số phương pháp, giải quyết đụng độ. Mời các bạn cùng tham khảo nội dung chi tiết.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 7 - Trần Minh Thái (2016)
- Chương 7. Bảng băm
(Hash Table)
Trần Minh Thái
Email: minhthai@huflit.edu.vn
Website: www.minhthai.edu.vn
1
- Nội dung
1. Khái niệm
2. Đặc điểm và cấu trúc
3. Một số phương pháp
4. Giải quyết đụng độ
2
- Truy xuất trực tiếp
•
Giả sử cần lưu trữ thông tin có các đặc điểm nhau:
• Dữ liệu có các khóa (key) trong phạm vi 0…m-1
• Các khóa này là riêng biệt (không trùng nhau)
Giải pháp?
3
- Truy xuất trực tiếp
•
Tạo một mảng T[0..m-1] trong đó
• T[i] = x nếu x T và key[x] = i
• T[i] = NULL cho trường hợp ngược lại
Cấu trúc này được gọi là bảng truy xuất trực tiếp (direct-
address table)
• Độ phức tạp truy xuất: O(1)
• Tuy nhiên?
4
- Tuy xuất trực tiếp
•
Chỉ thích hợp cho miền giá trị m của các khóa tương đối nhỏ
•
Giả sử khoá là số nguyên 32-bit:
1. Bảng sẽ có kích thước 232 (hơn 4 tỉ ô)
2. Giả sử không có rào cản về bộ nhớ thì cũng mất thời gian để khởi
tạo giá trị NULL
Giải pháp: ánh xạ những khoá này thành miền nhỏ hơn từ 0...p-1
Hash Table
5
- Bảng băm (Hash Table)
6
- Thành phần dữ liệu
•
K: tập các khoá (set of keys)
•
A: tập các địa chỉ (set of addresses)
•
HF(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 A
7
- Các thao tác
•
Khởi tạo (Initialize)
•
Kiểm tra rỗng (Empty)
•
Lấy kích thước của bảng băm (Size)
•
Tìm kiếm (Search)
•
Thêm mới phần tử (Insert)
•
Loại bỏ (Remove)
•
Sao chép (Copy)
•
Duyệt (Traverse)
8
- Vấn đề Bảng băm
•
O(1) cho tất cả các thao tác
•
Khóa không phải là một chỉ số mảng trực tiếp mà chỉ số thông
qua hàm h(key) – hàm băm
Ví dụ: myArray[h(key)]
•
Vấn đề: h()?
9
- Vấn đề Bảng băm
U 0
(universe of keys)
h(k1)
k1
h(k4)
K k4
(actual k5
h(k2)
h(k2)
keys)
h(k5)
k2 h(k3)
k3
p 1
10
- Các loại Bảng băm
•
Bảng băm đóng: mỗi khóa ứng với một địa chỉ, thời gian truy
xuất là hằng số
•
Bảng băm mở: một số khóa có cùng địa chỉ, mỗi mục địa chỉ sẽ
là một DSLK các phần tử có cùng địa chỉ, thời gian truy xuất có
thể bị suy giảm
11
- Hàm băm?
Hàm biến đổi giá trị khoá (số, chuỗi…) thành địa chỉ, chỉ mục
trong bảng băm
Hash value
Giá trị Hàm Địa chỉ
khoá băm hoặc chỉ mục
12
- Hàm băm
Ví dụ : hàm băm biến đổi khoá dạng chuỗi gồm n kí tự thành 1
địa chỉ (số nguyên)
int HashFunc(String s)
{
int n = s.Length, i=0;
int sum = 0;
while( n-- ) sum = sum + s[i++];
return sum % 256;
}
Tính địa chỉ của khoá “AB” : hashfunc(“AB”) 131
Tính địa chỉ của khoá “BA” : hashfunc(“BA”) 131
Khi hàm băm 2 khoá vào cùng 1 địa chỉ thì gọi là đụng độ
(Collision) 13
- Yêu cầu của hàm băm
•
Tính toán nhanh
•
Các khoá được phân bố đều trong bảng
•
Ít xảy ra đụng độ
14
- Hàm băm dạng bảng tra
Khoá Địa chỉ Khóa Địa chỉ Khóa Địa chỉ Khóa Địa chỉ
a 0 h 7 o 14 v 21
b 1 I 8 p 15 w 22
c 2 j 9 q 16 x 23
d 3 k 10 r 17 y 24
e 4 l 11 s 18 z 25
f 5 m 12 t 19 / /
g 6 n 13 u 20 / /
15
- Hàm băm sử dụng phương pháp chia
•
Dùng số dư:
h(k) = |k| mod m
•
Với k là khoá, m là kích thước của bảng
Chọn giá trị m?
m là nguyên tố
m=100 m=97 (nguyên tố)
Khoá Địa chỉ Khoá Địa chỉ
325 25 325 34
125 25 125 28
147 47 147 50
16
- Hàm băm sử dụng phương pháp nhân
h(k) = m(kA - kA )
•
Với k là khóa, m là kích thước bảng, A là hằng số: 0 < A < 1
Chọn m và A?
•
Thường chọn m = 2p
•
Knuth: A = ( 5 - 1)/2
0.618033987 được xem là tốt
17
- Hàm băm sử dụng phương pháp nhân
m=100, M=100,
A=0.61803 A=0.52173
Khoá Địa chỉ Khoá Địa chỉ
325 86 325 56
125 25 125 21
147 85 147 69
18
- Hàm băm phổ quát
•
Một tập các hàm băm H là phổ quát (universal )
nếu h H và 2 khoá k, ta có xác suất:
Pr{h(k) = h(l)}
- Đụng độ (collision) địa chỉ
•
Xảy ra khi h(x) ánh xạ hai khoá vào cùng vị trí
0
U
(universe of keys)
h(k1)
k1
collision
h(k4)
k4
K
k5
(actual
h(k2) = h(k5)
h(k2)
keys)
k2 h(k3)
k3
p 1
20
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
