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: Chương 8 - Nguyễn Xuân Vinh

Chia sẻ: Xaydung K23 | Ngày: | Loại File: PPTX | Số trang:38

Thêm vào BST
Báo xấu
106
lượt xem 12
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 - Chương 8: Hash table trình bày các vấn đề cơ bản với arrays list, linked list, bảng băm "hoàn hảo", hàm băm hoàn hảo, phương pháp xây dựng hàm băm, ưu điểm của bảng băm, các cách giải quyết xung đột, các bảng băm phổ biến,...

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: Chương 8 - Nguyễn Xuân Vinh

  1. GV: NGUYỄN XUÂN VINH CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] HASH TABLE MÔN: CẤU TRÚC DỮ LIỆU Nguyễn Xuân Vinh nguyenxuanvinh@hcmuaf.edu. 6/12/14 vn /XX 1
  2. GV: NGUYỄN XUÂN VINH Nội dung • Giới thiệu • Các vấn đề cơ bản với ArrayList, Linked List • Bảng băm “hoàn hảo” • Hàm băm hoàn hảo MÔN: CẤU TRÚC DỮ LIỆU • Phương pháp xây dựng hàm băm • Ưu điểm của bảng băm • Các cách giải quyết xung đột (collision) • Các bảng băm phổ biến (đọc them) • Java Map Interface • Map implementations in Java HashMap example 6/12/14 • /XX 2 2
  3. GV: NGUYỄN XUÂN VINH Giới thiệu MÔN: CẤU TRÚC DỮ LIỆU Tất cả các thao tác phải so sánh khoá!!! 6/12/14 Khắc /XX 3 phục? 3
  4. GV: NGUYỄN XUÂN VINH Vấn đề cơ bản • Bài toán: cần lưu trữ các mẫu tin và thực hiện các thao tác – Thêm mẫu tin – Xoá mẫu tin – Tìm mẫu tin theo khóa MÔN: CẤU TRÚC DỮ LIỆU • Tìm cách thức thực hiện một cách hiệu quả? 6/12/14 /XX 4 4
  5. GV: NGUYỄN XUÂN VINH Vấn đề cơ bản • Unsorted array – Sử dụng mảng để lưu mẫu tin, không có thứ tự – Thêm: thêm cuối nhanh O(1) – Xoá: chậm do tìm rồi xoá O(n) MÔN: CẤU TRÚC DỮ LIỆU – Tìm kiếm: tuần tự chậm O(n) 6/12/14 /XX 5 5
  6. GV: NGUYỄN XUÂN VINH Vấn đề cơ bản • Sorted array – Sử dụng mảng lưu trữ mẫu tin, có thứ tự – Thêm: chèn vào đúng vị trí, chậm O(n) – Xoá: phải dời các phần tử phía sau, chậm O(n) MÔN: CẤU TRÚC DỮ LIỆU – Tìm: nhị phân, nhanh O(logn) 6/12/14 /XX 6 6
  7. GV: NGUYỄN XUÂN VINH Vấn đề cơ bản • Linked list – Lưu trữ mẫu tin trong danh sách liên kết – Thêm: nhanh, O(1) – Xoá: nhanh khi xoá nút, chậm khi tìm O(n) MÔN: CẤU TRÚC DỮ LIỆU – Tìm kiếm: tìm kiếm tuần tự O(n) 6/12/14 /XX 7 7
  8. GV: NGUYỄN XUÂN VINH Vấn đề cơ bản • Cấu trúc dữ liệu phức tạp hơn, nhưng thực thi tốt hơn – Tree BST – Hash table MÔN: CẤU TRÚC DỮ LIỆU 6/12/14 /XX 8 8
  9. GV: NGUYỄN XUÂN VINH Array as table 0012345 An 8.15 0033333 Binh 90 MÔN: CẤU TRÚC DỮ LIỆU 0056789 Danh 5.68 ... 9801010 Phuong 2.0 9802020 Minh 10.0 ... 9903030 Thao 7.3 9908080 Tung 4.9 6/12/14 Vấn đề: lưu trữ 10,000,000 mẫu tin sinh viên và /XX tìm kiếm theo mã số sinh viên. 9
  10. GV: NGUYỄN XUÂN VINH Array as table 0 : : : MÔN: CẤU TRÚC DỮ LIỆU 12345 An 8.15 : : : Một cách “stupid” là lưu trữ mẫu tin 33333 Binh 9.0 trong mảng cực lớn 0..9999999 : : : Index được sử dụng như là mã số sinh viên. Khi đó mẫu tin sv với ms 56789 Danh 5.68 0012345 được lưu trữ ở A[12345]! : : : : : : 9908080 Tung 4.9 6/12/14 : : : 9999999 /XX 10 10
  11. GV: NGUYỄN XUÂN VINH Array as table • Dạng bảng băm với địa chỉ trực tiếp – Mỗi vị trí tương ứng một khoá trong U – Nếu 1 phần tử x có khoá k, thì T[k] chứa tham chiếu đến x – Ngược lại T[k] = Ø được thể hiện là null MÔN: CẤU TRÚC DỮ LIỆU 0 - U 1 - (universe of key) 2 2 4 3 6 0 9 3 7 4 - 1 5 K (actual keys) 5 6/12/14 6 3 - 2 8 7 - 5 8 /XX 8 - 9 11 11
  12. GV: NGUYỄN XUÂN VINH Array as table • Lưu trữ mẫu tin trong mảng lớn: chỉ mục tương đương khóa • Thêm: rất nhanh O(1) • Xóa: rất nhanh O(1) • Tìm: rất nhanh O(1) MÔN: CẤU TRÚC DỮ LIỆU • Nhưng lãng phí rất nhiều bộ nhớ! 6/12/14 /XX 12 12
  13. GV: NGUYỄN XUÂN VINH Hàm băm “hoàn hảo” int Hash(KeyType key) MÔN: CẤU TRÚC DỮ LIỆU Giả sử có hàm “magic” hash. Nó H(‘0012345’) = 134 ánh xạ mã số của 1000 sinh viên H(‘0033333’) = 67 vào các số 0..999, ánh xạ one to H(‘0056789’) = 764 one. Không có 2 mã số cùng giá … trị ánh xạ. H(‘9908080’) = 3 6/12/14 /XX 13
  14. GV: NGUYỄN XUÂN VINH Hàm băm “hoàn hảo” 0 name score : : : MÔN: CẤU TRÚC DỮ LIỆU 3 9908080 Tung 4.9 Để lưu trữ 1 mẫu tin, gọi Hash(stud_id) và lưu trữ : : : 67 0033333 Binh 9.0 vào vị trí Hash(stud_id) trong mảng. : : : 134 0012345 An 8.15 Để tìm một sinh viên, chỉ cần gọi Hash(stud_id). : : : 764 0056789 Danh 5.68 : : : 6/12/14 999 : : : /XX 14 14
  15. GV: NGUYỄN XUÂN VINH Bảng băm với hàm băm hoàn hảo • Magic hash – Thêm: rất nhanh O(1) – Xóa: rất nhanh O(1) – Tìm: rất nhanh O(1) MÔN: CẤU TRÚC DỮ LIỆU • Thực tế rất khó xây dựng được hàm băm hoàn hảo (khi không gian khóa quá lớn) 6/12/14 /XX 15 15
  16. GV: NGUYỄN XUÂN VINH Ưu điểm bảng băm • Dung hòa tốt giữa thời gian truy xuất và dung lượng bộ nhớ – Nếu ko giới hạn bộ nhớ: one-to-one, truy xuất tức thì – Nếu dung lượng bộ nhớ có giới hạn thì tổ chức khóa cùng địa chỉ Bảng băm ứng dụng nhiều trong thực tế, thích hợp tổ chức dữ MÔN: CẤU TRÚC DỮ LIỆU • liệu có kích thước lớn và lưu trữ ngoài 6/12/14 /XX 16 16
  17. GV: NGUYỄN XUÂN VINH Hàm băm • Hàm băm: biến đổi khóa thành chỉ mục trên bảng băm – Khóa có thể là dạng số hay dạng chuỗi – Chỉ mục được tính từ 0..M-1, với M là số chỉ mục của bảng băm Hàm băm thường dùng: key % M, với M là độ lớn của bảng MÔN: CẤU TRÚC DỮ LIỆU – băm • Hàm băm tốt phải thoả yêu cầu – Tính toán nhanh. – Các khoá đượ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 dữ liệu khác nhau. 6/12/14 /XX 17 17
  18. GV: NGUYỄN XUÂN VINH Hàm băm: Một số PP xây dựng • Hàm băm dạng bảng tra – Ví dụ: cho bảng chữ cái alphabet, chữ cái a được băm vào địa chỉ 0, chữ cái b được băm vào địa chỉ 1,..., của bảng băm • Hàm băm sử dụng phương pháp chia Dùng số dư: h(x) = x % M MÔN: CẤU TRÚC DỮ LIỆU – x là khóa, M là kích thước bảng băm (nên là số nguyên tố ) 6/12/14 /XX 18
  19. GV: NGUYỄN XUÂN VINH Hàm băm: Một số PP xây dựng • Sử dụng phương pháp trung phương(Middle Square) Với M = 2k (k>=1) (M là kích thước của mảng) W = 2w (w: là số lượng bit của một số int = 32) MÔN: CẤU TRÚC DỮ LIỆU 6/12/14 /XX 19
  20. GV: NGUYỄN XUÂN VINH Hàm băm: Một số PP xây dựng • Sử dụng phương pháp nhân – Sử dụng công thức MÔN: CẤU TRÚC DỮ LIỆU x là khóa, M là kích thước bảng 6/12/14 /XX 20
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