Bài Giảng Cấu Trúc Dữ Liệu Và Giải Thuật Trong C++ - Bài: Bảng Băm

• Đăng ký
• Đăng nhập
• Liên hệ

TimTaiLieu.vn - Tài liệu, ebook, giáo trình, đồ án, luận văn

TimTaiLieu.vn - Thư viện tài liệu, ebook, đồ án, luận văn, tiểu luận, giáo trình, hướng dẫn tự học

• Trang Chủ
• Tài Liệu
• Upload

Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài: Bảng băm - Hash Tables

3. Phương pháp phân đoạn Giá trị khóa được phân ra thành nhiều đoạn bằng nhau  Người ta sử dụng hai kỹ thuật phân đoạn sau đây:  Tách: Tách các đoạn ra và mỗi đoạn được xếp thành một hàng, dóng lề trái hoặc lề phải.  Gấp: Gấp các đoạn lại theo đường biên tương tự như gấp giấy, các chữ rơi vào cùng một chỗ được đặt thành hàng thẳng nhau.

14 trang | Chia sẻ: thanhle95 | Lượt xem: 1231 | Lượt tải: 1 Bạn đang xem nội dung tài liệu Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài: Bảng băm - Hash Tables, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên© 2004 Goodrich, Tamassia 3. Tìm kiếm theo địa chỉ *** Bảng băm - Hash Tables   0 1 2 3 4 451-229-0004 981-101-0002 025-612-0001 2I. Hàm băm Cấu trúc hàm băm  Hàm băm có dạng như sau: h : K  0..m-1  Trong đó: - h được gọi là hàm băm (hash function) - K là tập giá trị khóa - 0..m-1 là bảng địa chỉ (là các số nguyên) - m là kích thước của bảng  Yêu cầu khi xây dựng hàm băm:  Hàm phải dải đều các địa chỉ trên bảng địa chỉ  Hàm băm phải được tính toán đơn giản. 0 m-1 1 2 x z 3 y K h 3Hình ảnh hàm băm K h(k) k1 k2 k3 0 1 N-1 h(k1) h(k3) h(k2) 4Hàm băm Một hàm băm ánh xạ các đối tượng vào tập các địa chỉ [0, N-1] Các đối tượng Hàm băm 0 1 2 N-1 Bảng địa chỉ 5II. Một số phương pháp xây dựng hàm băm 1. Phương pháp chia  Để tính địa chỉ dải của đối tượng ta lấy giá trị khóa chia cho kích thước của bảng. Địa chỉ dải là phần dư của phép chia đó. h(k) = k % m  Yêu cầu:  Hàm h phải dải đều các đối tượng trên bảng một cách ngẫu nhiên. Để có được điều đó h phải phụ thuộc vào m.  Phụ thuộc vào m  Thông thường người ta chọn m là một số nguyên tố nhỏ hơn gần với (10, 100, 1000,...) nhất. 62. Phương pháp nhân Giá trị khóa được nhân với chính nó sau đó lấy con số bao gồm một số chữ số ở “giữa” kết quả để làm “địa chỉ rải”. Ví dụ: k k2 h(k) gồm 3 chữ số 5402 0367 1246 29181604 00134689 01552516 181 hoặc 816 134 hoặc 346 552 hoặc 525 Rõ ràng các chữ số ở giữa phụ thuộc vào mọi chữ số của khóa do đó nếu khóa có khác nhau chút ít thì địa chỉ dải vẫn khác nhau nhiều. 73. Phương pháp phân đoạn Giá trị khóa được phân ra thành nhiều đoạn bằng nhau  Người ta sử dụng hai kỹ thuật phân đoạn sau đây:  Tách: Tách các đoạn ra và mỗi đoạn được xếp thành một hàng, dóng lề trái hoặc lề phải.  Gấp: Gấp các đoạn lại theo đường biên tương tự như gấp giấy, các chữ rơi vào cùng một chỗ được đặt thành hàng thẳng nhau. 8Ví dụ: Tách: giả sử có khóa là k = 17046329 329 + 046 017 392 Gấp: 046 + 923 710 1679 Chọn 167 hoặc 679 9III. Bảng băm - Hash table Một bảng băm là một cấu trúc dựa trên mảng để lưu trữ các phần tử, mỗi phần tử là một cặp Khóa-Giá trị (key-value) Các thành phần cấu thành lên bảng băm  Mảng chứa  Mỗi phần tử mảng quản lý một danh sách các phần tử có khóa qua ánh xạ h cho cùng một địa chỉ.  Hàm băm h(k) - Hash function, h(k)  Mã băm 10 0 1 2 3 4 44-4-34 12 11-21-41 Giả sử có hàm h(k) = k % 5 Có các giá trị: 11, 21, 44, 23, 41, 4, 34, 12 23 Thùng chứa 11 Độ phức tạp về thời gian Độ phức tạp về thời khi đưa một phần tử vào bảng và tìm kiếm một phần tử trong bảng Độ phức tạp về thời gian  Trường hợp xấu nhất là O(n)  Trường hợp tốt nhất O(1) 12 Cấu trúc dữ liệu bảng băm Thuộc tính  Mảng (mỗi phần tử mảng lưu một danh sách các phần tử)  N: kích thước mảng Các phương thức  Node *Add(Key, Object)  void Remove(Key)  Node *Find(Key)  bool Contains(Key)  int Count() 13 Bài tập 1. Viết chương trình nhập vào một dãy số nguyên. Xây dựng hàm băm để tìm kiếm một phần tử nhập từ bàn phím. (hàm băm theo số) 2. Viết chương trình tìm kiếm một sinh viên (sử dụng lớp sinh viên đã học) sử dụng bảng băm (hàm băm theo chữ). Thời gian: 17h00 ngày 12/11/2014 14 Relax Tài liệu liên quan

• Bài giảng Microsoft Office

  18 trang | Lượt xem: 1964 | Lượt tải: 1

• Tóm tắt văn bản tiếng Việt dựa trên phương pháp học không giám sát

  6 trang | Lượt xem: 630 | Lượt tải: 1

• Chương 5a. Khái niệm và thao tác cơ bản trong Microsoft Excel

  35 trang | Lượt xem: 2036 | Lượt tải: 2

• Bài giảng Kiến trúc máy tính - Chương 7: Đa lõi, Đa xử lý và Máy tính cụm

  31 trang | Lượt xem: 748 | Lượt tải: 1

• Kho dữ liệu và Hệ hỗ trợ quyết định

  313 trang | Lượt xem: 2613 | Lượt tải: 1

• Giáo trình Hệ số đếm và mã

  112 trang | Lượt xem: 1846 | Lượt tải: 1

• Sử dụng các thành phần giao diện người dùng trong jQuery Mobile

  10 trang | Lượt xem: 1824 | Lượt tải: 1

• Bài giảng Chương 1 nhập môn cơ sở dữ liệu

  19 trang | Lượt xem: 1975 | Lượt tải: 1

• Tương thích của SQL trong CLPPlus

  22 trang | Lượt xem: 1549 | Lượt tải: 1

• Chương 1: Tiền xử lý dữ liệu

  39 trang | Lượt xem: 3183 | Lượt tải: 1

Copyright © 2024 TimTaiLieu.vn Website đang trong thời gian thử nghiệm, chờ xin giấy phép của Bộ TT & TT. Chia sẻ: Thư viện Luận Văn, Tài Liệu và Đồ Án tốt nghiệp. Thư viện Ebook miễn phí, Thư viện giáo án, PDF Hướng dẫn giải bài tập SGK.