Bài giảng Cấu trúc dữ liệu: Bảng băm - TS. Lê Minh Trung & Th.S Lương Trần Ngọc Khiết

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!
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu: Bảng băm - TS. Lê Minh Trung & Th.S Lương Trần Ngọc Khiết TS. Lê Minh Trung – ThS Lương Trần Ngọc KhiếtKhoa Công nghệ Thông tin, Đại học Sư phạm TP. HCMBả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ậnBà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 7Bả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ụngBả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-1Bả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-1Ví 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 5454 3 24 4 5 Làm thế nào để giải quyết đụng độ??? 6 37 7  Chuỗi liên kết (chaining) 88 8  Địa chỉ mở (open addressing) 9 Chuỗi liên kết Đặt các khóa có cùng giá trị băm (hash value) trong cùng một danh sách liên kết gắn với một ô của bảng băm. U —— (universe of keys) k1 k4 —— —— k1 —— K k4 k5 —— (actual ...