›
›

Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 9: Bảng

*Đánh giá Radix sort

*Số lần so sánh là Θ(n k), n là số phần tử và k  là số ký tự trên khóa

*So sánh với các phương pháp khác là n lg n:

*Nếu k lớn và n là nhỏ thì radix sort chậm

*Nếu k nhỏ và n là lớn thì radix sort nhanh hơn

*Bất tiện:

*Việc tách thành 27 danh sách con và ghép lại lúc sau trên DS liên tục gây ra việc di chuyển nhiều phần tử

*Khóa so sánh là chuỗi nhị phân thì không tốt

ppt 24 trang thiennv 07/11/2022 3040
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 9: Bảng", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.

File đính kèm:

  • pptbai_giang_cau_truc_du_lieu_va_giai_thuat_chuong_9_bang.ppt

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 9: Bảng

  1. Bảng Hash Bảng Hash Bảng Vị trí của 1 phần tử được tính bằng hàm hash Hàm hash: Nhận vào một khóa Trả về một chỉ số vị trí (Có thể chuyển vài khóa về cùng một vị trí) Đụng độ trên bảng hash: Nếu vị trí tìm ra đúng là dữ liệu cần tìm: O(1) Không đúng: giải quyết đụng độ (phải đảm bảo O(1)) 11 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 9. Bảng
  2. Hàm Hash Đảm bảo O(1) Ví dụ: f(x) = x % m; f(‘abc’) = (char_index(‘a’)*base_number2 + char_index(‘b’)*base_number1 + char_index(‘c’)*base_number0) % hash_size 12 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 9. Bảng
  3. Ví dụ dùng bảng Hash Các khóa: M, O, T, V, I, D, U T 0 U 1 V 2 M 3 hash(x) = char_index(x) % 10 D 4 O 5 Tìm V 6 Không có Tìm F 7 8 I 9 char_index: Space=0, A=1, B=2, , Z=27 M O T V I D U F 3 5 0 2 9 4 1 6 13 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 9. Bảng
  4. Phương pháp Địa chỉ mở (Open Addressing) Bảng hash là một array Các vị trí khi có đụng độ sẽ tìm vị trí mới bằng các phương pháp giải quyết: Thử tuyến tính (linear probing): Tăng chỉ số lên một: h = (h+i) % hash_size Thử bậc hai (quadratic probing): Tăng chỉ số lên theo bình phương: h = (h + i2)% hash_size Phương pháp khác Ngẫu nhiên 14 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 9. Bảng
  5. Thiết kế bảng Hash dùng địa chỉ mở Đảm bảo phép thử tuyến tính không bị lặp vòng const int hash_size = 997; // a prime number of appropriate size class Hash_table { public: Hash_table( ); void clear( ); Error_code insert(const Record &new entry); Error_code retrieve(const Key &target, Record &found) const; private: Record table[hash_size]; }; 15 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 9. Bảng
  6. Giải thuật thêm phần tử dùng bảng Hash địa chỉ mở Algorithm Hash_Insert Input: bảng Hash, mẫu tin cần thêm vào Output: bảng Hash đã có mẫu tin thêm vào 1. probe = hash(input_key) 2. increment = 1 //Dùng khi đụng độ 3. while (table[probe] không rỗng) //Có đụng độ //Dùng các phép thử (tuyến tính, bậc hai, ) 3.1. probe = (probe + increment) % hash_size 3.2. increment = increment + 2 //Thử bậc hai 4. table[probe] = new_data End Hash_insert 16 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 9. Bảng
  7. Mã C++ thêm phần tử dùng bảng Hash địa chỉ mở Error_code Hash_table :: insert(const Record &new entry) { Error_code result = success; int probe_count = 0, increment = 1, probe; Key null; probe = hash(new_entry); while (table[probe] != null && table[probe] != new_entry && probe_count < (hash size + 1)/2) { probe_count++; probe = (probe + increment)%hash_size; increment += 2; } if (table[probe] == null) table[probe] = new_entry; else if (table[probe] == new_entry) result = duplicate_error; else result = overflow; return result; } 17 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 9. Bảng
  8. Phương pháp nối kết (chained hash table) 18 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 9. Bảng
  9. Lợi ích của phương pháp nối 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 hash 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 m Độ dài trung bình của DSLK là n/m 19 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 9. Bảng
  10. Thiết kế bảng Hash nối kết const int hash_size = 997; // a prime number of appropriate size class Hash_table { public: //Specify methods here private: List table[hash_size]; }; 20 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 9. Bảng
  11. Thiết kế các phương thức của bảng Hash nối kết Constructor: Gọi constructor của mỗi danh sách trong array. Clear: Gọi phương thức clear cho mỗi danh sách trong array. Retrieval: sequential_search(table[hash(target)], target, position); Insertion: table[hash(new_entry)].insert(0, new_entry); Deletion: remove(const Key type &target, Record &x); Nếu tìm thấy trong danh sách tương ứng thì xóa đi 21 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 9. Bảng
  12. Đánh giá phương pháp dùng bảng Hash load factor λ = số mẫu tin/kích thước bảng hash Tìm kiếm với bảng hash nối kết: 1+(1/2)λ phép thử khi tìm thấy λ phép thử khi không tìm thấy. Tìm với bảng hash địa chỉ mở (thử ngẫu nhiên): (1/λ)ln (1/(1-λ)) phép thử khi tìm thấy 1/(1-λ) phép thử khi không tìm thấy Tìm với bảng hash địa chỉ mở (thử tuyến tính): (1/2)(1 + 1/(1-λ)) phép thử khi tìm thấy (1/2)(1 + 1/(1-λ)2) phép thử khi không tìm thấy 22 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 9. Bảng
  13. So sánh các phương pháp 23 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 9. Bảng
  14. So sánh các phương pháp (tt.) 24 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 9. Bảng