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

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

1. Bài 10: Bảng băm Giảng viên: Hoàng Thị Điệp Khoa Công nghệ Thông tin – Đại học Công Nghệ Cấu trúc dữ liệu và giải thuật HKI, 2013-2014
2. Kiểm tra viết, 15 phút (Sinh viên có thể sử dụng tài liệu.) 1. Nêu 2 hàm băm 2. Nêu 2 phương pháp giải quyết va chạm trong bảng băm nói tới trong Chương 9 Giáo trình. 2 diepht@vnu
3. Nội dung chính  Giới thiệu phương pháp băm  Hashing  Các hàm băm  Hash function  Các chiến lược giải quyết va chạm  Collision resolution 3 diepht@vnu
4. KDLTT từ điển  Trường hợp riêng của tập  Các phép toán động khi ta chỉ quan tâm tới  find(k) trả về 1 phần tử có tìm kiếm, xen, loại khóa k. Nếu không thấy trả  Là tập hợp trong đó mỗi phần về NULL. tử là một cặp (khóa, dữ liệu)  findAll(k)  Có thể tìm kiếm theo khóa  insert(k, v) thêm phần tử (k,  Được sắp hoặc không được v) và trả về con trỏ tới nó sắp  erase(k) loại bỏ phần tử bất  Các phần tử có thể có cùng kì có khóa bằng k khóa*  erase(p) loại bỏ phần tử trỏ bởi p  Dictionary vs. Map  size() trả về số lượng phần tử  Ứng dụng  empty() kiểm tra xem từ điển  Từ vựng – nghĩa rỗng hay không  Tên miền – địa chỉ IP  Mã sinh viên – hồ sơ SV 4 diepht@vnu
5. Phương án cài KDLTT từ điển  Mảng được sắp / không được sắp  DSLK đơn/kép được sắp / không được sắp  Cây tìm kiếm nhị phân 5 diepht@vnu
6. Cài KDLTT từ điển bằng mảng  Nếu khoá của dữ liệu là số nguyên không âm và nằm trong khoảng [0 SIZE-1]  có thể sử dụng một mảng data có cỡ SIZE  dữ liệu có khoá k sẽ được lưu trong data[k]  tìm kiếm, xen, loại đều thực hiện trong thời gian O(1)  Thực tế không khả thi vì  số phần tử dữ liệu có thể rất nhỏ so với SIZE  khoá có thể không phải là số nguyên  Ta muốn lợi dụng tính ưu việt của phép truy cập trực tiếp của mảng 6 diepht@vnu
7. Phương pháp băm  Lưu tập dữ liệu trong mảng T với cỡ là SIZE  Hàm băm: là hàm ứng với mỗi giá trị khoá k của dữ liệu với một chỉ số i (0 <= i <= SIZE-1)  Dữ liệu này sẽ được lưu trong T[i]  h : K {0,1, ,SIZE-1} 0 1 Tính địa chỉ i Hàm băm h Tập các giá trị khoá SIZE-1 7 Mảng T diepht@vnu
8. 8 diepht@vnu
9. Sự va chạm  Nếu  có k1 ≠ k2 thì h(k1) ≠ h(k2), và  việc tính chỉ số h(k) ứng với mỗi khoá k chỉ đòi hỏi thời gian hằng thì các phép toán tìm kiếm, xen, loại chỉ cần thời gian O(1)  Va chạm  Trong thực tế k1 ≠ k2 có thể cho h(k1) = h(k2)  Giải quyết va chạm như thế nào? 9 diepht@vnu
10. Hàm băm  Hàm băm tốt  tính nhanh và dễ dàng  đảm bảo ít va chạm  Một số hàm bă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 10 diepht@vnu
11. Khóa là số nguyên không âm  Phương pháp chia  Phương pháp nhân  h(k) = k mod SIZE  h(k) = (αk - αk) . SIZE  nhạy cảm với cỡ của bảng  Ký hiệu x chỉ phần nguyên băm của số thực x  chọn SIZE để hạn chế xảy ra  Thực tế thường chọn va chạm  số nguyên tố có dạng đặc α = Φ −1 ≈ 0,61803399 biệt, chẳng hạn có dạng 4k+3 11 diepht@vnu
12. Khoá là xâu ký tự  Trước tiên, đổi các xâu ký tự thành các số nguyên, dùng bảng mã ASCII  Xâu ký tự có thể xem như một số trong hệ đếm cơ số 128  Sau đó chuyển sang hệ đếm cơ số 10  Ví dụ “NOTE” ‘N’.1283 + ‘O’.1282 + ‘T’.128 + ‘E’ = = 78.1283 + 79.1282 + 84.128 + 69  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 và 10 chữ số, và một vài ký tự khác. Thay 128 bởi 37  Tính số nguyên ứng với xâu ký tự theo luật Horner  Ví dụ “NOTE” 78.373 + 79.372 + 84.37 + 69= = ((78.37 + 79).37 +84).37 +69 12 diepht@vnu
13. Giải quyết va chạm  Dữ liệu d1 với khoá k1 đã được lưu trong T[i], h(k1)=i. Ta cần thêm dữ liệu d2 với khoá k2  nếu h(k2) = i thì dữ liệu d2 cần được đặt vào vị trí nào?  Các phương pháp  Phương pháp định địa chỉ mở (open addressing/probing)  mỗi khi xảy ra va chạm, tiến hành thăm dò để tìm một vị trí còn trống trong bảng và đặt dữ liệu mới vào đó  Phương pháp tạo dây chuyền (separate chaining)  tạo ra một CTDL lưu giữ tất cả các dữ liệu có cùng vị trí i và “gắn” CTDL này vào vị trí đó trong bảng 13 diepht@vnu
14. Phương pháp định địa chỉ mở  Giả sử vị trí ứng với khoá k là i, i=h(k)  Từ vị trí này, lần lượt xem xét các vị trí i0, i1 , i2 , , im ,  Trong đó i0 = i, im là vị trí thăm dò lần thứ m.  Dãy này được gọi là dãy thăm dò.  Xác định dãy thăm dò  Thăm dò tuyến tính (linear probing)  Dãy thăm dò là i , i+1, i+2 ,  Thăm dò bình phương (quadratic probing)  Dãy thăm dò là i , i + 12, i + 22, , i + m2,  Băm kép (double hashing)  Dãy thăm dò là h1(k) + m h2(k), với m = 0, 1, 2, 14 diepht@vnu
15. Các phép toán  Tìm kiếm? Xen? Loại?  insert(47) => T[3] => T[4] => T[5] => T[6]  Minh họa  find(47)  SIZE = 11  remove(926)  Thăm dò tuyến tính  find(47)  insert(388) => T[3]  remove(388), find(926)  insert(130) => T[9] {không có data,  insert(13) => T[2] data bị xóa,  insert(14) => T[3] => T[4] có data}  insert(926) => T[2] => T[3] => T[4] => T[5] 0 1 2 3 4 5 6 7 8 9 10 15 diepht@vnu
16. Nhận xét (1/2)  Thăm dò tuyến tính  Ưu điểm: cho phép xét tất cả các vị trí trong mảng  phép insert 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 16 diepht@vnu
17. Nhận xét (2/2)  Thăm dò bình phương  Ưu điểm: tránh được nhược điểm của thăm dò tuyến tính  Nhược điểm: không cho phép ta tìm đến tất cả các vị trí trong mảng  phép insert có thể không thực hiện được  nếu cỡ của mảng là số nguyên tố, thì thăm dò bình phương cho phép ta tìm đến một nửa số vị trí trong mảng  Băm kép  nếu cỡ của mảng và bước thăm dò h2(k) nguyên tố cùng nhau thì phương pháp băm kép cho phép tìm đến tất cả các vị trí trong mảng 17 diepht@vnu
18. Phương pháp tạo dây chuyền Hàm băm h T  Ưu điểm  số dữ liệu được lưu không phụ thuộc vào cỡ của mảng  Các phép toán  Tìm kiếm?  Xen?  Loại? 18 diepht@vnu
19. Hiệu quả của phương pháp băm N α =  Tham số α SIZE  Băm đ/c mở: mức độ đầy (load factor)  α tăng thì khả năng va chạm tăng  Khi thiết kế, cần đánh giá max của N để lựa chọn SIZE  α không nên vượt quá 2/3  Băm dây chuyền: độ dài trung bình của một dây chuyền Băm đ/c mở, Băm đ/c mở, Băm dây chuyền Thăm dò tuyến tính Thăm dò bình phương 1  1  − ( −α ) 1 Thời gian Tìm kiếm 1+  ln 1 1+ trung thành công 2  1−α  α α bình Tìm kiếm 1  1   +  1 2  1 thất bại 2  (1−α )  α 1−α 19 diepht@vnu
20. 20 diepht@vnu
21. Chuẩn bị tuần tới  Lý thuyết: Đọc chương 10 (Hàng ưu tiên)  Thực hành: Cài đặt bảng băm 21 diepht@vnu