Bài giảng Cấu trúc dữ liệu và Giải thuật - Chương 7: Bảng băm - Trần Minh Thái

Chương 7. Bảng băm(Hash Table)Trần Minh TháiEmail: minhthai@huflit.edu.vnWebsite: www.minhthai.edu.vn1Nội dungKhái niệmĐặc điểm và cấu trúcMột số phương pháp Giải quyết đụng độ2Truy xuất trực tiếpGiả sử cần lưu trữ thông tin có các đặc điểm nhau: Dữ liệu có các khóa (key) trong phạm vi 0m-1 Các khóa này là riêng biệt (không trùng nhau) Giải pháp?3Truy xuất trực tiếp Tạo một mảng T[0..m-1] trong đó T[i] = x nếu x  T và key[x] = i T[i] = NULL cho trường hợp ngược lại Cấu trúc này được gọi là bảng truy xuất trực tiếp (direct-address table) Độ phức tạp truy xuất: O(1) Tuy nhiên?4Tuy xuất trực tiếp Chỉ thích hợp cho miền giá trị m của các khóa tương đối nhỏ Giả sử khoá là số nguyên 32-bit:Bảng sẽ có kích thước 232 (hơn 4 tỉ ô)Giả sử không có rào cản về bộ nhớ thì cũng mất thời gian để khởi tạo giá trị NULL  Giải pháp: ánh xạ những khoá này thành miền nhỏ hơn từ 0...p-1  Hash Table5Bảng băm (Hash Table)6Thành phần dữ liệuK: tập các khoá (set of keys)A: tập các địa chỉ (set of addresses)HF(k): hàm băm dùng để ánh xạ một khoá k từ tập các khoá K thành một địa chỉ tương ứng trong tập A7Các thao tácKhởi tạo (Initialize)Kiểm tra rỗng (Empty)Lấy kích thước của bảng băm (Size)Tìm kiếm (Search)Thêm mới phần tử (Insert)Loại bỏ (Remove)Sao chép (Copy)Duyệt (Traverse)8Vấn đề Bảng băm O(1) cho tất cả các thao tác Khóa không phải là một chỉ số mảng trực tiếp mà chỉ số thông qua hàm h(key) – hàm bămVí dụ: myArray[h(key)] Vấn đề: h()?9Vấn đề Bảng băm10h(k2)0p - 1h(k1)h(k4)h(k2)h(k3)k4k2k3k1k5U(universe of keys)K(actualkeys)h(k5)Các loại Bảng bămBảng băm đóng: mỗi khóa ứng với một địa chỉ, thời gian truy xuất là hằng số Bảng băm mở: một số khóa có cùng địa chỉ, mỗi mục địa chỉ sẽ là một DSLK các phần tử có cùng địa chỉ, thời gian truy xuất có thể bị suy giảm11Hàm băm?Hàm biến đổi giá trị khoá (số, chuỗi) thành địa chỉ, chỉ mục trong bảng băm12Giá trị khoáHàm bămĐịa chỉ hoặc chỉ mụcHash valueHàm bămVí dụ : hàm băm biến đổi khoá dạng chuỗi gồm n kí tự thành 1 địa chỉ (số nguyên)int HashFunc(String s) { int n = s.Length, i=0; int sum = 0; while( n-- ) sum = sum + s[i++]; return sum % 256;}Tính địa chỉ của khoá “AB” : hashfunc(“AB”)  131Tính địa chỉ của khoá “BA” : hashfunc(“BA”)  131Khi hàm băm 2 khoá vào cùng 1 địa chỉ thì gọi là đụng độ (Collision)13Yêu cầu của hàm bămTính toán nhanhCác khoá được phân bố đều trong bảngÍt xảy ra đụng độ14Hàm băm dạng bảng tra15KhoáĐịa chỉKhóaĐịa chỉKhóaĐịa chỉKhóaĐịa chỉa0h7o14v21b1I8p15w22c2j9q16x23d3k10r17y24e4l11s18z25f5m12t19//g6n13u20//Hàm băm sử dụng phương pháp chiaDùng số dư:h(k) = |k| mod mVới k là khoá, m là kích thước của bảngChọn giá trị m? m là nguyên tố16m=97 (nguyên tố)KhoáĐịa chỉ325341252814750m=100KhoáĐịa chỉ325251252514747Hàm băm sử dụng phương pháp nhânh(k) = m(kA - kA) Với k là khóa, m là kích thước bảng, A là hằng số: 0 < A < 1Chọn m và A?Thường chọn m = 2pKnuth: A = (5 - 1)/2  0.618033987 được xem là tốt17Hàm băm sử dụng phương pháp nhân18m=100, A=0.61803KhoáĐịa chỉ325861252514785M=100, A=0.52173KhoáĐịa chỉ325561252114769Hàm băm phổ quátMột tập các hàm băm H là phổ quát (universal ) nếu hH và 2 khoá k, ta có xác suất: Pr{h(k) = h(l)} <= 1/m với m là kích thước bảngĐể xác suất xảy ra đụng độ thấp, khởi tạo một tập các hàm băm H phổ quát và từ đó h được chọn ngẫu nhiên 19h(k2)Đụng độ (collision) địa chỉXảy ra khi h(x) ánh xạ hai khoá vào cùng vị trí0p - 1h(k1)h(k4)h(k2) = h(k5)h(k3)k4k2k3k1k5U(universe of keys)K(actualkeys)collision20Ví dụSử dụng bảng băm có kích thước N = 10,000 Hàm bămh(x) = 4 chữ số cuối của x01234999799989999451-229-0004981-101-0002200-751-9998025-612-000121Giả sử chèn thêm khóa 176-354-9998 Giá trị băm trùng với khoá 200-751-9998 !!!01234999799989999451-229-0004981-101-0002200-751-9998025-612-0001176-354-9998Ví dụ22Giải quyết đụng độ bằng phương pháp nối kết23Giải quyết đụng độ bằng cách băm lạiPhương pháp dò tuyến tính (Linear Probe)Nếu băm lần đầu bị xung đột thì băm lại lần 1, lần 2, Quá trình băm lại diễn ra cho đến khi không còn xung đột nữa hi(key)=(h(key)+i) mode m với h(key) là hàm băm chính của bảng băm24Ví dụh(x) = x mod 13Chèn các khoá theo thứ tự 18, 41, 22, 44, 59, 32, 31, 73 0123456789101112 41 18445932223173 012345678910111225Giải quyết đụng độ bằng cách băm lạiPhương pháp dò bậc hai (Quadratic Probing Method) hi(key)=(h(key) + i2) mod mvới h(key) là hàm băm chính của bảng bămNếu đã dò đến cuối bảng thì trở về dò lại từ đầu bảngNên chọn m là số nguyên tố26Bài tậpCho dãy khóa: 23, 24, 27, 1, 8, 17, 28, 10, 25, 11, 30, 20, 12, 6, 2, 0Giả sử h(x) = x mod 17Hãy chèn các khóa trên theo thứ tự từ trái sang phải và dùng phương pháp dò bậc hai để giải quyết đụng độ27