Bài giảng Cấu trúc dữ liệu: Bảng băm cung cấp cho người học những kiến thức như: Hàm băm (hash function); Bảng băm; Đụng độ và xử lí đụng độ; Chuỗi liên kết; Dò tuyến tính/ bậc 2/ băm kép; Kết luận. Mời các bạn cùng tham khảo! | TS. Lê Minh Trung ThS Lương Trần Ngọc Khiết Khoa Công nghệ Thông tin Đại học Sư phạm TP. HCM Bảng băm Hash Table Hàm băm hash function Bảng băm Đụng độ và xử lí đụng độ Chuỗi liên kết Dò tuyến tính bậc 2 băm kép Kết luận Bài toán tìm kiếm Tìm kiếm tuần tự Duyệt qua các phần tử của mảng một cách tuần tự Độ phức tạp O N Tìm kiếm nhị phân Mảng đã được sắp thứ tự Độ phức tạp 2 Trong thực tế kích cỡ mảng cần tìm N có thể lên tới hàng tỷ Có phương pháp tìm kiếm nào có độ phức tạp O 1 Hàm băm Hash function Là hàm ℎ ánh xạ từ tập các khóa key K vào 0 1 . ℎ 0 1 2 1 ℎ được gọi là giá trị băm của . Tập các khóa K có thể là tập các chuỗi các số tự nhiên ℎ 0 1 với ℎ Hàm băm tt Với các khóa chưa ở dạng số hàm băm thường có dạng sau ℎ ℎ2 ℎ1 với là một khóa. ℎ1 để tính mã băm hash code . ℎ2 0 1 2 1 là hàm nén. ℎ2 Ví dụ hàm băm Giả sử các khóa là các chuỗi 1 1 0 Có thể tính mã băm như sau ℎ1 0 128 bảng mã ASCII có 128 kí hiệu ℎ1 0 36 26 chữ thường 10 chữ số Có thể sử dụng hàm nén như sau ℎ2 100 Hàm băm ℎ ℎ2 ℎ1 ℎ1 100 Hàm nén Nhân Nhân Multiply Cộng h2 y y mod N Add và Chia Divide MAD N là kích cỡ của bảng h2 y ay b mod N băm và thường được chọn là số nguyên tố. a và b là các số nguyên không âm sao cho Liên quan tới lí thuyết số. a mod N 0 7 Bảng băm Hash Table Là một bảng mảng có kích cỡ hash_size N. N thường được chọn là số nguyên tố. Mẩu tin record có khóa là k sẽ được lưu trữ tại vị trí h k trong bảng. h là hàm hash h thường được chọn là hàm modulo h k k mod N. Lí tưởng nếu chọn được N là số khóa k thực sự được sử dụng Bảng băm U 0 tất cả các khóa h k1 k1 h k4 K k4 các khóa k5 h k2 h k5 thật sự dùng k2 h k3 k3 N-1 Bảng băm Một đụng độ collision xảy ra khi hai khóa được ánh xạ vào cùng vị trí trong bảng ℎ 1 ℎ 2 . U 0 tất cả các khóa Đụng h k độ1 k1 h k4 K k4 các khóa k5 h k2 h k5 thật sự dùng k2 h k3 k3 N-1 Ví dụ bảng băm Thêm vào các khóa 51 24 37 42 88. 0 Hàm băm h k k mod 10 51 1 42 2 Tìm 37 3 24 4 5 Không thấy Tìm 56 6 37 7 88 8 Tìm 62 9 Đụng độ 0 51 1 Đụng 42 độ 2 Thêm khóa
