Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 8: Bảng băm - Lê Nguyên Khôi

Thiết Kế & Đánh Giá Thuật Toán Bảng Băm TS. Lê Nguyên Khôi Trường Đại Học Công Nghệ - ĐHQGHN Nội Dung
Phương pháp băm
Hàm băm
Giải quyết va chạm 1 Bài Toán Từ Điển
Dùng tập động cài đặt từ điển
Mỗi phần tử là cặp (khóa, dữ liệu)
Có thể tìm theo khóa
Được sắp xếp hoặc không
Chỉ quan tâm tới
Tìm kiếm SEARCH (, )
Chèn INSERT (, )
Xóa DELETE (, )
Tổ chức cấu trúc dữ liệu  như thế nào? 2 Bài Toán Từ Điển
Nếu khóa của dữ liệu là số nguyên không âm trong khoảng 0 − 1 , phân biệt
Có thể sử dụng mảng cỡ
Dữ liệu khóa  lưu tại  
Tìm kiếm, chèn, xóa trong thời gian (1)
Thực tế không khả thi
Số phần tử dữ liệu có thể rất nhỏ so với
số 64-bit thể hiện 2 (18 × 10) khóa khác nhau
Xâu ký tự thậm chí còn lớn hơn
Khóa có thể không phải số nguyên
Tận dụng phép truy cập trực tiếp của mảng 3 Phương Pháp Băm
Lưu dữ liệu trong mảng  0 − 1
Hàm băm ℎ: ánh xạ mỗi giá trị khóa  của dữ liệu tới một chỉ số  (0 ≤  < )
Dữ liệu sẽ được lưu trong []
ℎ:  → {0, 1, , − 1} 4 0 1 i  − 1 Tính địa chỉ Tập các giá trị khoá Hàm băm ℎ Mảng  Phương Pháp Băm
Nếu có  ≠ " thì ℎ() ≠ ℎ("), và tính chỉ số ℎ() trong thời gian (1)
thì các phép toán tìm kiếm, chèn, xóa cũng trong thời gian (1)
Tuy nhiên, thường xảy ra va chạm
Chèn khóa vào vị trí đã có khóa khác
Thực tế  ≠ " có thể cho ℎ  = ℎ(") 5 Hàm Băm
Khó xác định phương pháp băm đồng đều đơn giản.
Hàm băm tốt
Phân bố khóa đồng đều vào các vị trí
Tính nhanh & dễ dàng
Đảm bảo ít va chạ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 6 Hàm Băm – Phương Pháp Chia ℎ  =  mod 
Nhạy cảm với cỡ của bảng băm ()
Chọn  để hạn chế xảy ra va chạm
Không chọn  có ước số nhỏ
Số nguyên tố có dạng đặc biết, ví dụ 4) + 3
Ví dụ: nếu  = 2,, hàm băm không phụ thuộc vào tất cả các bit của 
 = 1011000111-..-.-" và / = 6, thì ℎ  = -..-.-" 7 Hàm Băm – Phương Pháp Nhân  = 2,, với máy tính 1-bit. Hàm băm: ℎ() = (2 ·  mod 24) rsh (1– /)
rsh là toán tử “bitwise right-shift”
Toán tử rsh nhanh
2 là số lẻ trong khoảng 249 < 2 < 24
Không chọn 2 quá gần 249 hoặc 24
Phép nhân và phép chia dư 24 nhanh hơn phép chia 8 Hàm Băm – Phương Pháp Nhân ℎ() = (2 ·  mod 24) rsh (1– /)
: = 2, = 8 = 2; với máy tính 1 = 7-bit 1011001 = 2 1101011 =  10010100110011 ℎ  = 011 9 Hàm Băm – Xâu Ký Tự
Đổi ký tự thành số nguyên (bảng ASCII)
Khi đó xâu ký tự là số trong hệ cơ số 128
Chuyển sang hệ 10
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, 10 chữ số, và một số ký tự khác
Thay 128 thành 37 10 Giải Quyết Va Chạm
Nếu dữ liệu = với khóa  đã được lưu tại   với ℎ  = . Cần thêm dữ liệu =" với khóa "
Nếu ℎ " = , xảy ra va chạm, =" lưu ở đâu?
Các phương pháp
Dây chuyền
Tạo một danh sách lưu tất cả dữ liệu có cùng vị trí 
Địa chỉ mở
Tìm vị trí khác còn trống trong bảng và cho dữ liệu mới vào đó 11 Giải Quyết Va Chạm – Dây Chuyền
Tại mỗi vị trí trong bảng băm  là một danh sách liên kết các dữ liệu có cùng giá trị băm 
Ưu điểm:
Số dữ liệu lưu không phụ thuộc vào cỡ của mảng
Thời gian các phép toán tìm kiếm, chèn, xóa? 12  Hàm băm Dây Chuyền – Phân Tích Thời Gian
Trường hợp xấu nhất:
Tất cả các khóa được băm vào cùng vị trí
Thời gian tìm kiếm > ?
Trường hợp trung bình:
Mỗi khóa  có thể được băm vào bất cứ vị trí nào trong , độc lập với việc các khóa khác được băm như thế nào 13 Dây Chuyền – Phân Tích Trung Bình
Trường hợp trung bình: băm đồng đều ? số lượng khóa trong bảng  độ lớn của bảng Hệ số tải của bảng băm  @ = A B = số lượng khóa trung bình tại mỗi vị trí trong bảng băm  14 Dây Chuyền – Tìm Kiếm Trung Bình Thời gian tìm kiếm không thành công = > 1 + @ Thời gian tìm kiếm là > 1 nếu @ = > 1 Thời gian tìm kiếm thành công có tiệm cận tương tự 15 Hàm băm Truy cập vị trí Tìm kiếm danh sách Giải Quyết Va Chạm – Địa Chỉ Mở
Khi xảy ra va chạm, tìm vị trí khác còn trống trong bảng và cho dữ liệu mới vào đó
Dãy các vị trí được tìm gọi là dãy thăm dò
Bảng băm có thể bị đầy
Xác định dãy thăm dò
Tuyến tính
Dãy thăm dò: ,  + 1,  + 2,
Bình phương
Dãy thăm dò: ,  + 1",  + 2",
Băm kép
Dãy thăm dò: ℎ() + :ℎ"() với : = 0,1,2, 16 Bài Tập  = 11, Phương pháp chia, Thăm dò tuyến tính insert(388) search(47) insert(130) delete(926).. insert(13) search(47) insert(14) delete(388) insert(926) search(926) insert(47) 17 Thăm Dò – Nhận Xét
Tuyến tính
Ưu điểm: xét tất cả các vị trí trong mảng
Phép chèn 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
Bình phương
Ưu điểm: tránh nhược điểm thăm dò tuyến tính
Nhược điểm: không xét tất cả các vị trí trong mảng
Phép chèn có thể không thực hiện được
Băm kép
Nếu cỡ của mảng và bước thăm dò ℎ"() nguyên tố cùng nhau thì cho phép tìm đến tất cả các vị trí trong mảng 18