Bài giảng Cấu trúc dữ liệu và giải thuật - Bài: Bảng băn - Văn Chí Nam

 Giảng viên:
 Văn Chí Nam – Nguyễn Thị Hồng Nhung – Đặng Nguyễn Đức Tiến
 2
 Khái quát về băm
 Hàm băm
 Sự đụng độ
 Các phương pháp giải quyết đụng độ
 Kết luận
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
-HCMUS © FIT 1
 3
 Hash Table
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
 4
  Vấn đề: Cho trước 1 tập S gồm các phần tử 
 được đặc trưng bởi giá trị khóa. Trên giá trị các 
 khóa này có quan hệ thứ tự. Tổ chức S như thế 
 nào để tìm kiếm 1 phần tử có khóa k cho trước 
 có độ phức tạp ít nhất trong giới hạn bộ nhớ 
 cho phép?
  Ý tưởng: Biến đổi khóa k thành một số (bằng 
 hàm hash) và sử dụng số này như là địa chỉ để 
 tìm kiếm trên bảng dữ liệu.
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
-HCMUS © FIT 2
 5
 ĐNĐTiến +84.95.8345678
 VCNam +84.91.2345678
 NTHNhung +84.90.9345678
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
 6
  Chi phí tìm kiếm trung bình: O(1)
  Chi phí tìm kiếm trong trường hợp xấu nhất: 
 O(n) (rất ít gặp).
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
-HCMUS © FIT 3
 7
  Định nghĩa: Hàm băm (hash function) là hàm biến
 đổi khóa k của phần tử thành địa chỉ trong bảng
 băm.
  Tổng quát về phép biến đổi khóa: Là 1 ánh xạ
 thích hợp từ tập các khóa U vào tập các địa chỉ A.
 H: U A
 k a = h(k)
  Tập các giá trị khóa (U) có thể lớn hơn rất nhiều so 
 với số khóa thực tế (K) rất nhiều.
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
 8
 T
 1 Key Data
 2
 3
 3
 Tập U 2 
 1 . . 4 4
 5 
 6 . . 5
 4. 3 6
 Tập K .
 7
 10 8 8
 . . 8
 9 
 . 7 . 9
 10
 10
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
-HCMUS © FIT 4
 9
  Chọn số (Digit-selection):
  Chọn một vài chữ số trong khóa và ghép lại tạo thành
 giá trị băm.
  Ví dụ:
  h(001364825) = 35
  Ưu điểm: Đơn giản, tính toán nhanh
  Khuyết điểm: Không thể hiện tính chất của khóa, 
 không phân bố đều
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
 10
  Gấp số (folding)
  Cộng các chữ số của khóa
  Nhóm các chữ số thành số và cộng lại
  Ví dụ:
  h(001364825) = 0 + 0 + 1 + 3 + 6 + 4 + 8 + 2 + 5 = 29
  h(001364825) = 001 + 364 + 825 = 1190
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
-HCMUS © FIT 5
 11
  Lấy dư (modulo arithmetic)
  Sử dụng phép tính lấy dư
  h (Key) = Key mod tableSize
  Ví dụ:
  h(Key) = Key mod 101
  h(001364825) = 12
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
 12
  k1, k2 K: 
 k1 ≠ k2, H(k1) = H(k2) T
 H(3)
 9 Tập U 7 
 1. . . H(4)
 5 
 6 . .
 4. 3 .
 Tập K
 10 8 
 . . H(2) = H(8)
 2 .
 H(10)
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
-HCMUS © FIT 6
 13
 Ít xảy ra Tính 
 đụng toán 
 độ. nhanh.
 Các khóa 
 phân bố đều.
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
 14
  Phương pháp nối kết (separate chaining)
  Phương pháp địa chỉ mở (Open-addressing)
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
-HCMUS © FIT 7
 15
  Ứng với mỗi địa chỉ của bảng, ta có một danh 
 sách liên kết chứa các phần tử có khóa khác 
 nhau mà có cùng địa chỉ đó.
  Ta sẽ có danh sách (bảng băm) gồm M phần tử 
 chứa địa chỉ đầu của các danh sách liên kết. 
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
 16
 ĐNĐTiến +84.95.8345678
 VCNam +84.91.2345678
 ĐTMHậu +84.95.6543210
 NTHNhung +84.90.9345678
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
-HCMUS © FIT 8
 17
  Tên gọi khác:
  Phương pháp dò
  Phương pháp thử
  Ý tưởng:
  Khi đụng độ xảy ra, ta sẽ thử tìm đến vị trị kế tiếp nào 
 đó trong bảng cho đến khi tìm thấy vị trí nào còn trống.
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
 18
  Phương pháp dò tuyến tính (Linear probing)
  Phương pháp dò bậc 2 (Quadratic probing)
  Phương pháp băm kép (Double hashing)
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
-HCMUS © FIT 9
 19
  Phương pháp dò tuyến tính:
 H(k, i) = (h(k) + i) mod M 
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
 20
  Phương pháp dò bậc 2:
 H(k, i) = (h(k) + i2) mod M
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
-HCMUS © FIT 10
 21
  Phương pháp băm kép:
 H(k, i) = (h1(k) + i*h2(k)) mod M
 h1(key) = key mod 11
 h2(key) = 7 – (key mod 7)
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
 22
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
-HCMUS © FIT 11
 23
  Phương pháp địa chỉ mở:
  Đơn giản khi cài đặt.
  Sử dụng cấu trúc dữ liệu cơ bản.
  Giải quyết được đụng độ nhưng lại có thể gây ra đụng
 độ mới.
  Phương pháp nối kết:
  Không bị ảnh hưởng về tốc độ khi mảng gần đầy.
  Ít tốn bộ nhớ khi mảng thưa (ít phần tử).
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
 24
 1. Cho bảng băm có kích thước M = 11. Hàm 
 băm: h(k) = k mod M. Dùng phương pháp địa 
 chỉ mở. Cho biết kết quả sau khi thêm vào 
 bảng băm các khóa 10, 22, 31, 4, 15, 28, 17, 
 88, 59, với 3 phương pháp xử lý đụng độ:
 a. Dò tuyến tính.
 b. Dò bậc 2.
 c. Băm kép h2(k) = (k mod 19)+1.
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
-HCMUS © FIT 12
 25
 2. Cho từ điển Anh – Việt có 15.000 từ, hãy tổ 
 chức cấu trúc dữ liệu bảng băm và cho biết hàm 
 băm thích hợp giúp cho việc tra từ hiệu quả 
 nhất.
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
 26
 Cấu trúc dữ liệu và giải thuật – HCMUS 2015
-HCMUS © FIT 13