Bài giảng Cấu trúc dữ liệu - Chương 9: Bảng băm - Lê Minh Trung

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 7Hàm nén  Nhân:  h2 (y) = y mod N  N là kích cỡ của bảng băm và thường được chọn là số nguyên tố.  Liên quan tới lí thuyết số.  Nhân (Multiply), Cộng (Add) và Chia (Divide) (MAD):  h2 (y) = (ay + b) mod N  a và b là các số nguyên không âm sao cho: a mod N  0 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 h(k2) Bảng băm 0 N - 1 h(k1) h(k4) = h(k5) h(k3) k4 k2 k3 k1 k5 U (tất cả các khóa) K (các khóa thật sự dùng) h(k2) 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)). 0 N - 1 h(k1) h(k4) = h(k5) h(k3) k4 k2 k3 k1 k5 U (tất cả các khóa) K (các khóa thật sự dùng) Đụng độ Ví dụ bảng băm  Thêm vào các khóa 51, 24, 37, 42, 88.  Hàm băm h(k) = k mod 10 0 1 2 3 4 5 6 7 8 9 51 24 37 42 88 Tìm 37 Tìm 56 Không thấy Tìm 62 Đụng độ  Làm thế nào để giải quyết đụng độ???  Chuỗi liên kết (chaining)  Địa chỉ mở (open addressing) 0 1 2 3 4 5 6 7 8 9 51 24 37 42 88 Thêm khóa 5454 Đụng độ 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. —— —— —— —— —— —— k4 k2 k3 k1 k5 U (universe of keys) K (actual keys) k6 k8 k7 k1 k4 —— k5 k2 k3 k8 k6 —— —— k7 —— Chuỗi liên kết  Thêm vào một phần tử như thế nào? —— —— —— —— —— —— k4 k2 k3 k1 k5 U (tất cả khóa) K (khóa thật sự Sử dụng) k6 k8 k7 k1 k4 —— k5 k2 k3 k8 k6 —— —— k7 —— Chuỗi liên kết  Xóa một phần tử như thế nào?  Có thể sử dụng danh sách liên kết đôi để xóa hiệu quả hơn? —— —— —— —— —— —— k4 k2 k3 k1 k5 U (tất cả khóa) K (khóa thật sự Sử dụng) k6 k8 k7 k1 k4 —— k5 k2 k3 k8 k6 —— —— k7 —— Chuỗi liên kết  Tìm kiếm một phần tử ứng với một khóa cho trước như thế nào? —— —— —— —— —— —— k4 k2 k3 k1 k5 U (tất cả khóa) K (khóa thật sự Sử dụng) k6 k8 k7 k1 k4 —— k5 k2 k3 k8 k6 —— —— k7 —— Chuỗi liên kết- Ví dụ  Thêm 24, 51, 88,42, 37 0 1 2 3 4 5 6 7 8 9 51 24 37 42 88 NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL Thêm 74 74 Thêm 97 97 Thêm 104 104Tìm 74 Xóa 97 Lợi ích của phương pháp chuỗi liên kết  Nếu số lượng mẫu tin lớn: tiết kiệm vùng nhớ.  Giải quyết đụng độ: đơn giản là đẩy vào cùng một danh sách liên kết.  Bảng băm nhỏ hơn nhiều so với số lượng mẫu tin.  Xóa một phần tử là đơn giản và nhanh chóng.  Độ phức tạp khi tìm kiếm:  Nếu có n mẫu tin, và bảng hash có kích thước N  Độ dài trung bình của DSLK là n/N Địa chỉ mở (Open Addressing)  Thêm phần tử vào có khóa k vào  Nếu ô h(k) đầy tìm ô kế tiếp tìm được một ô chưa đầy thêm phần tử có khóa k vào (probing – thăm dò).  Các kĩ thuật dò tìm: linear/quadratic/double hashing  Tìm kiếm phần tử có khóa k  Bắt đầu tìm từ ô h(k) nếu chưa tìm thấy, tìm tại ô kế tiếp  cho đến ô cuối Phương pháp thăm dò  Trả lời câu hỏi: ô kế tiếp sẽ được thăm dò là ô nào? 1. Thăm dò tuyến tính (Linear Probing) 2. Thăm dò bậc 2 (Quadratic Probing) 3. Thăm dò băm kép (double hashing) Thăm dò tuyến tính  Vị_trí_mới = (vị_trí_cũ + bước_nhảy) mod N  Ô thứ i được thăm dò có chỉ số  h(k,i) = (h(k) + c*i) mod N  c: bước nhảy  Nếu bước nhảy c=1 thì  h(k,i) = (h(k) + i) mod N Ví dụ dò tuyến tính  Thêm vào các khóa 51, 24, 37, 42, 88.  Hàm băm h(k) = k mod 10  h(k,i) = (h(k) + i) mod 10 0 1 2 3 4 5 6 7 8 9 51 24 37 42 88 Thêm 61 Xung đột 61Thêm 87 87 Thêm 108 108 Thêm 11 11 Tìm 108 Tìm 47 Not Found Việc tìm kiếm sẽ kết thúc khi  Tìm thấy khóa cần tìm  Gặp một ô trống  Số lần thăm dò = N-1 Thăm dò bậc 2  Ô thứ i được thăm dò có chỉ số  h(k,i) = (h(k) + c*i2 + d) mod N  Thông thường (c,d) = (1,0) hay (1,1)  Nếu c=1, d=0 thì các ô được thăm dò lần lượt là  h= h(k), (h + 12) mod N , (h+ 22) mod N, (h + 32) mod N,  Nếu N là số nguyên tố thì  Các ô được thăm dò sẽ lặp lại sau (N+1)/2 bước Thăm dò bậc 2  Ví dụ với N = 11: 0, 1, 4, 9, 16 ≡ 5, 25 ≡ 3, 36 ≡ 3  Với N = 13: 0, 1, 4, 9, 16 ≡ 3, 25 ≡ 12, 36 ≡ 10, 49 ≡ 10  Với N= 17: 0, 1, 4, 9, 16, 25 ≡ 8, 36 ≡ 2, 49 ≡ 15, 64 ≡ 13, 81 ≡ 13 Ví dụ dò bậc 2  Thêm vào các khóa 51, 24, 37, 42, 88.  Hàm băm h(k) = k mod 10  h(k,i) = (h(k) + i2) mod 10 0 1 2 3 4 5 6 7 8 9 51 24 37 42 88 Thêm 61 (i=2) Xung đột 61 Thêm 98 (i=1) 98 Thêm 108 (i=5) 108 Tìm 108 (i=5) Tìm 47 i=3 gặp ô trống Not Found Việc tìm kiếm sẽ kết thúc khi  Tìm thấy khóa cần tìm  Gặp một ô trống  Số lần thăm dò = (N+1)/2 Thăm dò băm kép  Ô thứ i được thăm dò có chỉ số:  h(k,i) = (h1(k) + i*h2(k)) mod N  h1 và h2 là hai hàm băm  h1 chỉ ra điểm bắt đầu dò  h2 chỉ ra qui tắc di chuyển Ví dụ băm kép  h1(k) = k mod 13  h2(k) = 8 - k mod 8  Thêm vào bảng băm các khóa  18 41 22 44 59 32 31 73 0 1 2 3 4 5 6 7 8 9 10 11 12 44 41 73 18 32 59 31 22 0 1 2 3 4 5 6 7 8 9 10 11 12 h(k,i) = (h1(k) + i*h2(k)) mod N Chọn hàm băm  Chọn hàm băm là phần quan trọng trong quá trình băm.  Hàm được chọn tốt sẽ cho ra các chỉ số được phân bố đều trên bảng băm  ít xung đột.  Nếu hàm chọn không tốt dữ liệu sẽ co cụm trên một vài phần nào đó của bảng  xung đột nhiều.  Với mỗi phương pháp, chọn hàm băm đều có các tiêu chí để hàm cho ra phân bố đều. Đánh giá phương pháp dùng bảng Hash  load factor λ = số khóa/kích thước bảng hash=n/N  Tìm kiếm với bảng băm chuỗi nối kết:  1+(1/2)λ phép thử khi tìm thấy  λ phép thử khi không tìm thấy.  Tìm với bảng hash địa chỉ mở (dò ngẫu nhiên):  (1/λ)ln (1/(1-λ)) phép thử khi tìm thấy  1/(1-λ) phép thử khi không tìm thấy  Tìm với bảng hash địa chỉ mở (dò tuyến tính):  (1/2)(1 + 1/(1-λ)) phép thử khi tìm thấy  (1/2)(1 + 1/(1-λ)2) phép thử khi không tìm thấy So sánh các phương pháp So sánh các phương pháp (tt.) CÁM ƠN VÌ ĐÃ LẮNG NGHE!