Cấu trúc dữ liệu và giải thuật - Bảng băm (hash table)

Nội dung text: Cấu trúc dữ liệu và giải thuật - Bảng băm (hash table)

1. Bảng băm (hash table) Nguyễn Mạnh Hiển Khoa Công nghệ thông tin hiennm@tlu.edu.vn
2. 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
3. Ví dụ bảng băm
4. 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)
5. 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
6. 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
7. 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
8. 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)
9. 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
10. 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)
11. 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
12. 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
13. Ví dụ Chèn 89, 18, 49, 58, 69 (hash(x) = x % 10)
14. Thăm dò bậc hai (quadratic probing) 2 hi(x) = [hash(x) + f(i)] % tableSize, f(i) = i
15. 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)
16. Ví dụ tổ chức lại bảng băm Bảng băm ban đầu Sau khi tổ chức lại Sau khi chèn 23