Bài giảng Cấu trúc dữ liệu và giải thuật 1: Chương 10 trình bày các nội dung chính sau: Bảng băm, hàm băm, phép băm phổ quát, phương pháp nối kết trực tiếp, phương pháp nối kết hợp nhất, phương pháp dò tuyến tính, . Mời các bạn cùng tham khảo để nắm nội dung chi tiết. | TRƯỜNG ĐH CÔNG NGHỆ THÔNG TIN BẢNG BĂM CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 1 Giới thiệu Phép Băm Hashing Là quá trình ánh xạ một giá trị khóa vào một vị trí trong bảng. Một hàm băm ánh xạ các giá trị khóa đến các vị trí ký hiệu h Bảng băm Hash Table là mảng lưu trữ các record ký hiệu HT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 HT có M vị trí được đánh chỉ mục từ 0 đến M- 1 M là kích thước của bảng băm. Bảng băm thích hợp cho các ứng dụng được cài đặt trên đĩa và bộ nhớ là một cấu trúc dung hòa giữa thời gian truy xuất và không gian lưu trữ. 2 HÀM BĂM Hàm băm biến đổi một khóa vào một bảng các địa chỉ. K h h K Khóa có thể là dạng số hay số dạng chuỗi. Địa chỉ tính ra được là số nguyên trong khoảng 0 đến M- CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 1 với M là số địa chỉ có trên bảng băm H k3 K1 K2 k3 h k1 h k2 3 Hàm băm Hash Functions Hàm băm tốt thỏa mãn các điều kiện sau Tính toán nhanh. Các khoá được phân bố đều trong bảng. Ít xảy ra đụng độ. Giải quyết vấn đề băm với các khoá không phải là số nguyên Tìm cách biến đổ khoá thành số nguyên CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Trong ví dụ trên loại bỏ dấu - 9635-8904 đưa về số nguyên 96358904 Đối với chuỗi sử dụng giá trị các ký tự trong bảng mã ASCCI Sau đó sử dụng các hàm băm chuẩn trên số nguyên. 4 HF Phương pháp chia k mod 28 chọn các bits Dùng số dư h k k mod m 0110010111000011010 k là khoá m là kích thước của bảng. vấn đề chọn giá trị m m 2n không tốt nếu chọn m 2n thông thường không tốt CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 h k k mod 2n sẽ chọn cùng n bits cuối của k m là nguyên tố tốt Gia tăng sự phân bố đều Thông thường m được chọn là số nguyên tố gần với 2n Chẳng hạn bảng 4000 mục chọn m 4093 5 HF Phương pháp nhân Sử dụng h k m k A mod 1 k là khóa m là kích thước bảng A là hằng số 0 lt A lt 1 Chọn m và A CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 M thường chọn m 2p Sự tối ưu trong việc chọn A phụ thuộc vào đặc trưng của dữ liệu. Theo Knuth chọn A 5 -1 được xem là tốt. 6 Phép băm phổ quát Việc chọn hàm băm không tốt có thể dẫn đến .
