Bảng băm (hash table)
• Các phần tử dữ liệu được lưu trữ trong mảng có kích
thước cố định
• Tìm kiếm dựa vào khóa (mà là một phần của phần tử
dữ liệu)
• Thực hiện các phép chèn, xóa và tìm kiếm trong thời
gian hằng
• Không hiệu quả với các thao tác đòi hỏi thông tin thứ
tự:
− VD: findMin, findMax
16 trang
|
Chia sẻ: candy98
| Lượt xem: 346
| Lượt tải: 0
Bạn đang xem nội dung tài liệu Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 12: Bảng băm – Nguyễn Mạnh Hiển, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Bảng băm (hash table)
Nguyễn Mạnh Hiển
Khoa Công nghệ thông tin
[email protected]
Bảng băm (hash table)
• Các phần tử dữ liệu được lưu trữ trong mảng có kích
thước cố định
• Tìm kiếm dựa vào khóa (mà là một phần của phần tử
dữ liệu)
• Thực hiện các phép chèn, xóa và tìm kiếm trong thời
gian hằng
• Không hiệu quả với các thao tác đòi hỏi thông tin thứ
tự:
− VD: findMin, findMax
Ví dụ bảng băm
So sánh các cấu trúc dữ liệu
• So sánh thời gian tìm kiếm:
− Véc-tơ và danh sách liên kết: O(N)
− Cây AVL: O(logN)
− Bảng băm: O(1)
Hàm băm (hash function)
• Ánh xạ khóa sang số nguyên (mà sẽ dùng làm chỉ số)
− hash(key) = số nguyên
− Các giá trị băm cần được phân bố đều
• ngay cả khi các khóa đầu vào không được phân bố
đều
• Nếu nhiều khóa ánh xạ sang cùng một số nguyên
(cùng vị trí trong bảng băm) đụng độ (collision)
− Quản lý đụng độ (sẽ thảo luận sau)
− Đụng độ sẽ giảm nếu các khóa phân bố đồng đều
trên bảng băm
Một hàm băm đơn giản
• Gọi:
− key: khóa có giá trị nguyên
− tableSize: kích thước bảng băm
• Một hàm băm đơn giản là: key % tableSize (chia lấy phần dư)
• Giả sử:
− key = 24, 48, 51, 78, 15
− tableSize = 10
• Thế thì: key % tableSize = 4, 8, 1, 8, 5
Một hàm băm cho các xâu ký tự
int hash(const string & key, int tableSize) {
int hashVal = 0;
for (int i = 0; i != key.size(); i++) {
hashVal += key[i]
}
return hashVal % tableSize;
}
• Giả sử:
− tableSize = 100
− key = “ABC” (mã ASCII của A, B, C là 65, 66, 67)
− hashVal = (65 + 66 + 67) % 100 = 198 % 100 = 98
Thiết kế bảng băm
1. Hàm băm: Ánh xạ khóa sang một vị trí trong bảng băm
− VD: index = hash(key) = key % tableSize
2. Phân giải đụng độ:
− Xử lý trường hợp nhiều khóa ánh xạ đến cùng một
vị trí
− Hai giải pháp thường gặp:
• Xâu chuỗi tách rời (separate chaining)
• Thăm dò ô trống (probing)
Xâu chuỗi tách rời
• Mỗi ô chứa một danh sách các
phần tử
• Các phần tử có khóa ánh xạ tới
cùng một ô được giữ trong cùng
danh sách
• Ví dụ:
• hash(key) = key % 10
• chèn 10 số chính phương đầu
tiên vào bảng băm
Phân tích giải pháp xâu chuỗi tách rời
• Xét bảng băm có M ô và chứa N phần tử:
– Chèn không kiểm tra tính duy nhất: O(1)
• Tìm vị trí chèn, sau đó gọi push_back/front
– Tìm, xóa, chèn có kiểm tra tính duy nhất, trường hợp
tồi nhất: O(N)
– Tìm, xóa, chèn có kiểm tra tính duy nhất, tính trung
bình:
• 1 + O(N/M)
– Ta sẽ tăng kích thước bảng băm nếu N/M vượt
quá một hằng , gọi là hệ số tải (load factor)
– Thời gian trung bình = 1 + O() = O(1)
Bảng băm thăm dò (probing hash table)
• Bảng băm xâu chuỗi (chaining hash table) phức tạp
do phải duy trì một danh sách liên kết ở mỗi ô
• Giải pháp phân giải đụng độ khác: thăm dò ô trống
− Nếu đụng độ xảy ra, thử các ô khác trong bảng
băm
− Thử các ô h0(x), h1(x), h2(x), h3(x), một cách tuần
tự cho đến khi tìm được một ô trống
• hi(x) = [hash(x) + f(i)] % tableSize
• f(0) = 0
Thăm dò tuyến tính (linear probing)
• hi(x) = [hash(x) + f(i)] % tableSize, f(i) = i
• Phép chèn (giả sử các khóa không trùng nhau):
1. index = hash(key)
2. nếu table[index] rỗng, đặt phần tử mới (gồm khóa và các thông
tin khác) vào vị trí table[index]
3. nếu table[index] không rỗng:
– index++; index = index % tableSize
– quay lại bước 2
• Tìm kiếm:
1. index = hash(key)
2. nếu table[index] rỗng, return -1 (không tìm thấy)
3. nếu table[index].key == key, return index (tìm thấy)
4. index++; index = index % tableSize; quay lại bước 2
Ví dụ
Chèn 89, 18, 49, 58, 69 (hash(x) = x % 10)
Thăm dò bậc hai (quadratic probing)
hi(x) = [hash(x) + f(i)] % tableSize, f(i) = i
2
Tổ chức lại bảng băm (rehashing)
• Bảng băm có thể bị đầy
− Khi đó không thể chèn thêm được nữa
• Bảng băm có thể khá đầy (nhưng chưa đầy 100%)
− Chèn, xóa và tìm kiếm mất nhiều thời gian hơn
• Giải pháp: Tổ chức lại bảng băm
− Tạo bảng mới có kích thước lớn hơn (VD: gấp hai lần)
− Định nghĩa hàm băm mới
− Di chuyển các phần tử từ bảng cũ sang bảng mới
• Chi phí tổ chức lại bảng băm = O(N) (N là số phần tử)
− Khá tốn kém nhưng xảy ra không thường xuyên
− Chỉ xảy ra khi bảng băm khá đầy (đầy X%, trong đó X là
tham số điều chỉnh được)
Ví dụ tổ chức lại bảng băm
Sau khi tổ chức lại Bảng băm ban đầu
Sau khi chèn 23
