Chương này cung cấp kiến thức về tìm kiếm theo bảng băm. Nội dung trình bày trong chương gồm có: Khái quát về hash, độ phức tạp, hàm băm (hash funtion), khó khăn của hàm băm, những yêu cầu đối với hàm băm, . | 31 Hash Table Cấu trúc dữ liệu và giải thuật – HCMUS 2011 32 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ác khó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ước có độ 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ằng hà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 2011 1 33 ĐNĐTiến + VCNam + NTHNhung + Cấu trúc dữ liệu và giải thuật – HCMUS 2011 34 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 2011 2 35 Đị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 A k a = h(k) Cấu trúc dữ liệu và giải thuật – HCMUS 2011 36 Tập các giá trị khóa (U) có thể lớn hơn rất nhiều so 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 2011 3 37 T . . . . Tập U 1 6 2 5 4 Tập K 10 9 3 8 7 1 2 3 4 5 6 7 8 9 10 Key Data 3 4 8 10 Cấu trúc dữ liệu và giải thuật – HCMUS 2011 38 k1, k2 K: k1 ≠ k2, H(k1) = H(k2) . 9 6 1 . . . Tập U 7 T H(3) H(4) 5 4 Tập K 10 3 8 2 H(2) = H(8) H(10) Cấu trúc dữ liệu và giải thuật – HCMUS 2011 © FIT-HCMUS 2011 4 39 Ít xảy ra đụng độ. Tính toán nhanh. Các khóa phân bố đều. Cấu trúc dữ liệu và giải thuật – HCMUS 2011 40 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ọn hà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 .
