intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 22: Hàm băm

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

Thêm vào BST
Báo xấu
52
lượt xem 5
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 và giải thuật – Bài 22: Hàm băm" trình bày bài toán, hàm băm, giải quyết xung đột, một số ví dụ sử dụng hàm băm.

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 và giải thuật – Bài 22: Hàm băm

  1. Cấu trúc dữ liệu và giải thuật Bài 22: Hàm băm Giảng viên: TS. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com 1 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  2. Bài 22: Hàm băm Nội dung: 22.1. Bài toán. 22.2. Hàm băm. 22.3. Giải quyết xung đột. 22.4. Một số ví dụ sử dụng hàm băm. 2 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  3. 22.1. Bài toán (1/9)  Giả sử cần lưu trữ một số bản ghi và thực hiện các thao tác:  Thêm: thêm một bản ghi  Xóa: xóa một bản ghi  Tìm kiếm: tìm kiếm một bản ghi  Hãy đưa ra cách tổ chức để thực hiện hiệu quả các công việc trên. 3 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  4. 22.1. Bài toán (2/9) – Sử dụng mảng  Sử dụng mảng không được sắp xếp  Thêm: thêm vào cuối mảng->O(1)  Xóa: mất nhiều thời gian tìm vị trí cần xóa và dồn mảng->O(n)  Tìm kiếm: tìm kiếm tuần tự->O(n)  Sử dụng mảng được sắp xếp  Thêm: phải tìm vị trí thêm vào->O(n)  Xóa: mất nhiều thời gian tìm vị trí cần xóa và dồn mảng->O(n)  Tìm kiếm: tìm kiếm nhị phân->O(log(n)) 4 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  5. 22.1. Bài toán (3/9) – Sử dụng DSLK  Thêm: thêm vào vị trí bất kỳ nhanh->O(1)  Xóa: nhanh trong tổ chức các nút, nhưng chậm trong tìm kiếm nút cần khóa->O(n)  Tìm kiếm: tìm kiếm tuần tự->O(n) 5 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  6. 22.1. Bài toán (4/9) – dùng như bảng  Giả sử cần lưu trữ 1000 bản ghi về sinh viên và tìm kiếm chúng theo ID ID Họ và tên Điểm 0012345 Nguyễn Văn A 10 0033333 Nguyễn Văn B 9 0056789 Nguyễn Văn C 8 … … … 9801010 Nguyễn Thị A 7 9802020 Nguyễn Thị B 8 … … … 9903030 Trần Văn A 9 9908080 Trần Văn B 10 6 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  7. 22.1. Bài toán (5/9) – dùng như bảng  Dùng một mảng rất lớn để lưu trữ (index 0..9999999). Chỉ số của mảng bằng với chỉ số id của sinh viên, i.e. ví dụ sinh viên với studid 0012345 thì được lưu trữ tại A[12345] Tên Điểm … … … 12345 Nguyễn Văn A 10 … … … 33333 Nguyễn Văn B 9 … … … 56789 Nguyễn Văn C 8 … … … 9801010 Nguyễn Thị A 7 … … … 9802020 Nguyễn Thị B 8 … … … 9999999 … … 7 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  8. 22.1. Bài toán (6/9) – dùng như bảng Một số nhận xét:  Đánh giá các thao tác  Thêm: rất nhanh O(1)  Xóa: rất nhanh O(1)  Tìm kiếm: rất nhanh O(1)  Nhưng quá tốn kém bộ nhớ->không hiệu quả 8 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  9. 22.1. Bài toán (7/9) – dùng hàm băm function Hash(key: KeyType): integer; Giả sử có 1 hàm băm lý tưởng. Nó H(‘0012345’) = 134 ánh xạ khóa (ID) của 1000 bản ghi H(‘0033333’) = 67 vào các giá trị nguyên 0..999, hai H(‘0056789’) = 764 … khóa khác nhau cho hai số nguyên H(‘9908080’) = 3 khác nhau. 9 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  10. 22.1. Bài toán (8/9) – dùng hàm băm 0 … … • Để lưu trữ một bản ghi, … … … tính Hash(ID) cho bản 3 Trần Văn B 10 … … … ghi và lưu trữ nó tại vị trí 67 Nguyễn Văn B 9 Hash(ID) của mảng. … … … •Để tìm kiếm một sinh 134 Nguyễn Văn A 10 … … … viên, chỉ cần truy cập đến 764 Nguyễn Văn C 8 vị trí Hash(target ID). … … … 999 … … 10 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  11. 22.1. Bài toán (9/9) – dùng hàm băm  Với hàm băm lý tưởng  Thêm: O(1)  Xóa: O(1)  Tìm kiếm: O(1)  Nói chung là khó thiết kế được hàm băm lý tưởng 11 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  12. 22.2. Hàm băm (1/6) Khái niệm:  Hàm băm là giải thuật nhằm sinh ra các giá trị băm tương ứng với mỗi khối dữ liệu.  Giá trị băm đóng vai gần như một khóa để phân biệt các khối dữ liệu.  Hàm băm thường được dùng trong bảng băm nhằm giảm chi phí tính toán khi tìm một khối dữ liệu trong một tập hợp. 12 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  13. 22.2. Hàm băm (2/6) Yêu cầu đối với hàm băm:  Tính toán nhanh.  Các khóa được phân bố đều trong bảng.  Ít xảy ra đụng độ.  Xử lý được các loại khóa có kiểu khác nhau. 13 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  14. 22.2. Hàm băm (3/6) Một số lĩnh vực sử dụng hàm băm:  Mật mã học  Bảng băm  Phát hiện và sửa lỗi dữ liệu  Nhận dạng âm thanh 14 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  15. 22.2. Hàm băm (4/6) – Một số hàm băm  Hàm cắt bỏ:  Cho khóa là số nguyên, bỏ bớt một phần nào đó của khóa.  Ví dụ: khóa là một số nguyên có 6 chữ số x=842615. Ta có thể quy ước là bỏ bớt chẳng hạn các chữ số hàng lẻ (1,3,5…), số còn lại sẽ là 821. Vậy H(x) = H(842615) = 821.  Nhận xét: Hàm cắt bỏ thỏa mãn tính chất thứ nhất của hàm băm nhưng tính chất thứ hai là khó thực hiện (khó có phân bố đều). 15 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  16. 22.2. Hàm băm (5/6) – Một số hàm băm  Hàm phần dư:  Khóa có giá trị nguyên và bảng băm B có m phần tử, ta lấy phần dư của phép chia x/m làm giá trị hàm băm. Để đảm bảo tính chất thứ hai của hàm băm nên chọn m là số nguyên tố.  Nhận xét: Các cách lấy phần dư cho khả năng tránh hiện tượng xung đột là tốt hơn cả. 16 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  17. 22.2. Hàm băm (6/6) – Một số hàm băm  Hàm gấp:  Cho khóa là số nguyên, chia số nguyên đó thành một số đoạn tùy chọn, sau đó kết hợp các phần đó lại theo một quy ước nào đó.  Ví dụ: Số các hàng lẻ: 465 và số các hàng chẵn: 821, vậy H(x)=465+821=1286.  Nhận xét: Tính chất thứ nhất của hàm băm được thỏa mãn. Do các chữ số của khóa đều có sử dụng, nên tính chất thứ hai có thể thỏa mãn tốt hơn với trường hợp dùng hàm băm cắt bỏ. 17 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  18. 22.3. Xung đột và giải quyết xung đột (1/4)  Trong hầu hết các trường hợp đều không tránh được xung đột H(‘0012345’) = 134 H(‘0033333’) = 67 H(‘0056789’) = 764 … H(‘9903030’) = 3 H(‘9908080’) = 3 • Xử lý thế nào khi hai khóa khác nhau lại ánh xạ đến một địa chỉ? 18 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  19. 22.3. Xung đột và giải quyết xung đột (2/4)  Phương pháp dò tuyến tính: ý tưởng là dò tìm vị trí trống tiếp theo rồi chèn phần tử bị đụng độ vào đó. Khi mảng đầy thì resize lại mảng.  Phương pháp dây chuyền: Thay vì cố gắng tìm trong danh sách một vị trí còn trống kế tiếp, phương pháp dây chuyền liên kết các danh sách có các khóa khác nhau nhưng có cùng giá trị hàm băm thành một danh sách. 19 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  20. 22.3. Xung đột và giải quyết xung đột (3/4)  Phương pháp dò tuyến tính: Insert: 89, 18, 49, 58, 9 to table size=10, hash function is: %tablesize 49 49 49 58 58 9 18 18 18 18 89 89 89 89 89 20 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2