Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Đỗ Ngọc Như Loan

Chia sẻ: Dien_vi10 Dien_vi10 | Ngày: | Loại File: PPTX | Số trang:18

Thêm vào BST

Báo xấu

42
lượt xem 1
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 - Chương 5: Bảng băm (Hashtable)" trình bày các khái niệm về bảng băm, giải quyết đụng độ bằng kết nối, định nghĩa bảng băm, các thao tác, độ phức tạp,... Mời các bạn cùng tham khảo.

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: Chương 5 - Đỗ Ngọc Như Loan

GV: Đỗ Ngọc Như Loan
Khái niệm  Bảng băm là một cấu trúc dữ liệu có thể lưu trữ một tập các đối tượng có số phần tử tùy ý  Các thao tác tìm kiếm, chèn, xoá trên bảng băm rất hiệu quả  Phần tử có khoá k (nguyên) được lưu trữ trong slot h(k), trong đó h là hàm băm (hash function) từ tập U các khóa đến tập các slot của bảng băm T[0..m1]
Khái niệm  Hàm băm có dạng h: U → {0,1,..., m1}, m là kích thước của bảng băm  h(k) là giá trị băm (hash value) của khoá k hay còn nói phần tử có khoá k băm slot h(k)  Với hàm băm chỉ cần xử lý m giá trị thay vì | U| giá trị
Bảng băm  Có thể có sự dụng độ (collision) lưu trữ các khóa, ví dụ k2 dụng độ k5, nghĩa là h(k2)= h(k5)  Các phương pháp giải quyết đụng độ § Thiết kế hàm băm h(U) phân bố đều trên T (không triệt để) § Giải quyết dụng độ bằng danh sách liên kết collision resolution by chaining) § Giải quyết dụng độ bằng địa chỉ mở (open addressing)
GiẢI QUYẾT ĐỤNG ĐỘ BẰNG KẾT NỐI  Đặt tất cả các phần tử có cùng giá trị hàm băm vào một danh sách liên kết  Slot j chứa pointer chỉ đến đầu của danh sách liên kết của tất cả các phần tử được lưu trữ có hàm băm là j  Nếu không có khóa k để h(k)=j thì thì slot j trỏ đến NULL
ĐỊNH NGHĨA BẢNG BĂM  Định nghĩa bảng băm trong C++, các khóa là số nguyên typedef struct CELL *LIST; struct CELL { int key; LIST next; }; typedef LIST TABLE[MAX]; TABLE T;
CÁC THAO TÁC  HashInitialize(T): Khởi tạo bảng băm  HashInsert(T, k): Chèn một phần tử có khóa k vào bảng băm T  HashSearch(T, k): Tìm một phần tử có khoá k trong T  HashDelete(T, k): Xoá một phần tử có khóa k khỏi T
HashInitialize void HashInitialize(TABLE &T,int &m) // m là kích thước { // bảng băm for(int i=0; i
HashInsert void HashInsert(TABLE &T, int m, int k) { ListInsert(T[Hash(k, m)], k); } int Hash(int k, int m) //hàm băm { return k%m; }
HashSearch LIST HashSearch(TABLE T, int k, int m) { return ListSearch(T[Hash(k,m)], k); }
HashDelete void HashDelete(TABLE & T, int m, int k) { ListDelete(T[Hash(k,m)], k); }
ĐỘ PHỨC TẠP  HashInsert(T, k) có T(n) = O(1)  HashSearch(T, k) và HashDelete(T, k) có độ phức tạp trung bình T(n) = O(n/m), trong đó m là kích thước bảng băm
HÀM BĂM  Một hàm băm là tốt nếu h(k) có thể là bất kỳ slot nào trên bảng băm  Trong ứng dụng cần tìm các hàm băm thích hợp  Luôn giả sử mỗi khoá là một số tự nhiên  Có một số cách xây dựng hàm băm như: phương pháp chia (division method), phương pháp nhân (multiplication method) v.v
HÀM BĂM  Với phương pháp chia, tạo hàm băm bằng cách đặt tương ứng mỗi khoá k với số dư trong phép chia k cho số slot m  Vậy h(k) = k mod m  Tập các khoá được chia thành m lớp  Nên chọn m là số nguyên tố không quá gần với lũy thừa của 2
HÀM BĂM  Phương pháp nhân, hàm băm có dạng: § h(k) = ,A là hằng thỏa 0
Yêu cầu: Cho dãy số nguyên dương gồm n số đôi một khác nhau và số k. Hãy kiểm tra xem có giá trị k trong dãy không? Input: Dữ liệu vào từ file HASH.INP gồm 2 dòng: + Dòng 1: Gồm 2 số nguyên n và k (n