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

Chia sẻ: Conbongungoc09 | Ngày: | Loại File: PDF | Số trang:32

Thêm vào BST

Báo xấu

35
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ế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 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 k7 k5 k2 k7 —— keys) —— k2 k3 k3 —— k8 k6 k8 k6 —— ——
Chuỗi liên kết  Thêm vào một phần tử như thế nào? U —— (tất cả khóa) k1 k4 —— —— k1 —— K k4 k5 —— (khóa thật sự k7 k5 k2 k7 —— Sử dụng) —— k2 k3 k3 —— k8 k6 k8 k6 —— ——
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? U —— (tất cả khóa) k1 k4 —— —— k1 —— K k4 k5 —— (khóa thật sự k7 k5 k2 k7 —— Sử dụng) —— k2 k3 k3 —— k8 k6 k8 k6 —— ——
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? U —— (tất cả khóa) k1 k4 —— —— k1 —— K k4 k5 —— (khóa thật sự k7 k5 k2 k7 —— Sử dụng) —— k2 k3 k8 k3 —— k6 k8 k6 —— ——
Chuỗi liên kết- Ví dụ  Thêm 24, 51, 88,42, 37 0 NULL 1 NULL 51 2 NULL 42 Thêm 74 Thêm 97 Thêm 104 3 NULL Tìm 74 4 NULL 24 74 104 5 NULL Xóa 97 6 NULL 7 NULL 37 97 8 NULL 88 9 NULL
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)