Bài giảng Cấu trúc dữ liệu và giải thuật: Tìm kiếm theo bảng băm - ĐHKHTN

Bài giảng "Cấu trúc dữ liệu và giải thuật: Tìm kiếm theo bảng băm" trình bày về các nội dung: khái quát về bảng băm, độ phức tạp thuật toán, hàm băm, khó khăn của hàm băm, sự đụng độ, những yêu cầu đối với hàm băm, phương pháp xử lý đụng độ. Để biết rõ hơn về nội dung chi tiết, 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: Tìm kiếm theo bảng băm - ĐHKHTN31Hash TableCấu trúc dữ liệu và giải thuật – HCMUS 201132Vấn đề: Cho trước 1 tập S gồm các phần tửđược đặc trưng bởi giá trị khóa. Trên giá trị cáckhóa này có quan hệ thứ tự. Tổ chức S như thếnào để tìm kiếm 1 phần tử có khóa k cho trướccó độ phức tạp ít nhất trong giới hạn bộ nhớcho phép?Ý tưởng: Biến đổi khóa k thành một số (bằnghàm hash) và sử dụng số này như là địa chỉ đểtìm kiếm trên bảng dữ liệu.Cấu trúc dữ liệu và giải thuật – HCMUS 2011© FIT-HCMUS 2011133ĐNĐTiến+84.95.8345678VCNam+84.91.2345678NTHNhung+84.90.9345678Cấu trúc dữ liệu và giải thuật – HCMUS 201134Chi phí tìm kiếm trung bình: O(1)Chi phí tìm kiếm trong trường hợp xấu nhất:O(n) (rất ít gặp).Cấu trúc dữ liệu và giải thuật – HCMUS 2011© FIT-HCMUS 2011235Định nghĩa: là hàm biến đổi khóa k của phần tửthành địa chỉ trong bảng băm.Ví dụ: H(k) = k mod M.Tổng quát về phép biến đổi khóa: Là 1 ánh xạthích hợp từ tập các khóa U vào tập các địa chỉA.H: U  Ak  a = h(k)Cấu trúc dữ liệu và giải thuật – HCMUS 201136Tập các giá trị khóa (U) có thể lớn hơn rất nhiềuso với số khóa thực tế (K) rất nhiều.Ví dụ: Quản lý danh sách 1000 sinh viên, mãsinh viên gồm 7 chữ số.Có U = 107 khóa so với K = 1000.Cấu trúc dữ liệu và giải thuật – HCMUS 2011© FIT-HCMUS 2011337T. ... ... .. .Tập U16254Tập K10938712345678910KeyData34810Cấu trúc dữ liệu và giải thuật – HCMUS 201138k1, k2  K:k1 ≠ k2, H(k1) = H(k2)...961...... .Tập U7TH(3)H(4)54Tập K10382H(2) = H(8)H(10)Cấu trúc dữ liệu và giải thuật – HCMUS 2011© FIT-HCMUS 2011439Ít xảy rađụngđộ.Tínhtoánnhanh.Các khóaphân bố đều.Cấu trúc dữ liệu và giải thuật – HCMUS 201140Xét lại ví dụ về danh sách sinh viên:Với kích thước bảng là M = 1000, ta có thể chọnhàm băm như sau:H(k) = k mod M.Khóa này thỏa mãn yêu cầu tính toán nhanh vàtrải đều trên bảng.Cấu trúc dữ liệu và giải thuật – HCMUS 2011© FIT-HCMUS 20115