Bài giảng Cấu trúc dữ liệu và giải thuật: Bảng băm - Nguyễn Mạnh Hiển

Bài giảng "Cấu trúc dữ liệu và giải thuật: Bảng băm" giới thiệu tới người đọc các kiến thức cơ bản về bảng băm, so sánh các cấu trúc dữ liệu, hàm băm, một hàm băm đơn giản, một hàm băm cho các xâu ký tự, thiết kế bảng băm, xâu chuỗi tách rời,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Bảng băm - Nguyễn Mạnh HiểnBảng băm (hash table)Nguyễn Mạnh HiểnKhoa Công nghệ thông tinhiennm@tlu.edu.vnBả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, findMaxVí dụ bảng bămSo 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ămMộ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 = 98Thiết kế bảng băm1. Hàm băm: Ánh xạ khóa sang một vị trí trong bảng băm − VD: index = hash(key) = key % tableSize2. 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ămPhâ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) = 0Thă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 2Ví 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) = i2Tổ 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 Bảng băm ban đầu Sau khi tổ chức lại Sau khi chèn 23 ...