Bài giảng Cấu trúc dữ liệu và giải thuật: Bảng băm - Nguyễn Văn Toàn (ĐH Công nghệ Thông tin8

Chia sẻ: May Trời Gio Bien | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

62
lượt xem 4
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ảng băm" cung cấp cho người học các kiến thức: Dẫn nhập, cách lựa chọn hàm băm, ví dụ về hàm băm không hiệu quả, cài đặt, giải pháp sử dụng hàm băm. Mời các bạn cùng tham khảo nội dung chi tiết.

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ảng băm - Nguyễn Văn Toàn (ĐH Công nghệ Thông tin8

Bảng băm (Hash table) Giáo viên: Nguyễn Văn Toàn 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 1
Dẫn nhập Một số nhận xét khi tìm kiếm trên mảng Nếu mảng chưa được sắp thứ tự Æ tìm tuyển tính, thời gian sẽ là O(n) Nếu không tìm thấy, chúng ta phải duyệt n phần tử Nếu tìm thấy, trung bình sẽ duyệt n/2 phần tử Nếu mảng được sắp xếp Æ tìm nhị phân Thời gian tìm kiếm O(log n) Nếu tìm được hay không thì thời gian tìm kiếm gần như nhau Có phương án nào hay hơn ? Có phương pháp nào sẽ cho thời gian tìm kiếm là O(1) ? Câu trả lời là có nếu chúng ta tổ chức lại mảng theo cơ chế khác. 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 2
Băm (Hashing) Giả sử chúng ta có một hàm đặc biệt (“magic function”), hàm có tham số là giá trị cần tìm x, trả về một vị trí trên mảng i : f(x)=i a[i] = x Æ Tìm thấy a[i] x Æ Không tìm thấy Các hàm băm thông dụng: Chia lấy dư. Ví dụ: f(x) = x % 100 Dãy số tuần tự. Ví dụ: f(123456789) = 258 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 3
Ví dụ về hàm băm (hash function) Khóa Chỉ số Hàm băm thực chất là một ánh 0 kiwi xạ biến đổi khóa thành chỉ số của 1 bảng. 2 banana Hàm băm cho chúng ta các giá trị như sau: 3 watermelon hashCode("apple") = 5 4 hashCode("watermelon") = 3 5 apple hashCode("grapes") = 8 hashCode("cantaloupe") = 7 6 mango hashCode("kiwi") = 0 7 cantaloupe hashCode("strawberry") = 9 hashCode("mango") = 6 8 grapes hashCode("banana") = 2 9 strawberry 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 4
Tại sao lại dùng bảng băm (hash tables)? ... Key Value Bảng băm là một 141 mảng lưu giá trị. 142 robin robin info Thông thường người 143 sparrow sparrow info ta sử dụng cặp 144 hawk hawk info khóa/giá trị trong 145 seagull seagull info bảng 146 Key để tìm một vị trí 147 bluejay bluejay info trong mảng 148 owl owl info Value: chứa thông tin thực sự ta muốn lưu 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 5
Cách lựa chọn hàm băm Làm thế nào để có thể chọn được hàm băm? Một cách tổng quát, chúng ta không thể chọn được / Trong một số trường hợp đặc biệt, khi chúng ta hiểu rõ các giá trị trong bảng, chúng ta có thể tính toán được hàm băm một cách tương đối hiệu quả. Cách đánh giá hàm băm? Một hàm băm được đánh giá là tốt khi nó cho chúng ta biết chính xác vị trí cần tìm Î giảm đụng độ Phân bố đều các giá trị trên bảng băm 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 6
Ví dụ về hàm băm không hiệu quả Giả sử hàm băm cung cấp cho chúng ta các giá trị 0 kiwi 1 sau: hash("apple") = 5 2 banana hash("watermelon") = 3 3 watermelon hash("grapes") = 8 4 hash("cantaloupe") = 7 hash("kiwi") = 0 5 apple hash("strawberry") = 9 6 mango hash("mango") = 6 hash("banana") = 2 7 cantaloupe hash("honeydew") = 6 8 grapes • “Điều gì đã xảy ra”? 9 strawberry 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 7
Đụng độ (Collisions) Khi xảy ra hiện tượng hai gía trị băm có cùng một vị trí trên mảng thì ta gọi đó là đụng độ, collision. f(x1)= f(x2) = i (x1 x2) Giải quyết vấn đề đụng độ theo cơ chế Queue (“first come, first served”) — giá trị đầu tiên được băm sẽ được cấp phát vị trí trước. Còn giá trị cần băm thứ hai cấp phát vị trí nào? 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 8
Giải quyết đụng độ Giải quyết như thế nào khi 2 phần tử được băm đều có cùng một vị trí trên bảng băm? f(x1) = f(x2) Giải pháp #1: Nếu một vị trí đã được cấp phát, ta bắt đầu từ đó để tìm một vị trí trống để cấp phát cho phần tử còn lại Điều kiện để dừng tìm kiếm là khi gặp giá trị cần băm (đã có phần tử đó trong bảng) hay tìm được vị trí trống Tìm kiếm vòng Giải pháp #2: Dùng hàm băm thứ hai …và hàm băm thứ ba, thứ tư, thứ năm ... Giải pháp #3: Dùng danh sách liên kết (DSLK) Việc thêm và tìm kiếm chỉ sử dụng cùng một giải pháp. 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 9
Giải pháp 1: Ví dụ 1, Thêm Giả sử chúng ta thêm từ ... seagull vào bảng băm 141 Các bước: 142 robin hashCode(seagull) = 143 143 sparrow table[143] đã có rồi / 144 hawk table[143] != seagull 145 seagull table[144] đã có rồi / 146 table[144] != seagull 147 bluejay table[145] rỗng 148 owl Do đó, đặt seagull ở vị trí ... 145 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 10
Giải pháp 1: Địa chỉ mở (Open-Addressing) Có các phương pháp chính như sau: Thử tuyến tính (Linear Probing) i0 = f(x1) ik = (i +k) % M (k = 1,…,M-1) Thử bậc hai (Quadratic Probing) i0 = f(x1) ik = (i +k*k) % M (k = 1,…,M-1) 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 11
Giải pháp 1: Ví dụ 2, Tìm kiếm Giả sử chúng ta muốn tìm ... giá trị seagull trên bảng 141 băm 142 robin Các bước: hashCode(seagull) = 143 143 sparrow table[143] không rỗng 144 hawk table[143] != seagull 145 seagull table[144] không rỗng 146 table[144] != seagull table[145] không rỗng 147 bluejay table[145] == seagull ! 148 owl Chúng ta tìm thấy giá trị ... seagull ở vị trí 145 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 12
Giải pháp 1: Ví dụ 3, Tìm kiếm Giả sử chúng ta tìm kiếm giá ... trị cow trong bảng băm 141 Các bước: 142 hashCode(cow) = 144 robin table[144] không rỗng 143 sparrow table[144] != cow 144 hawk table[145] không rỗng 145 seagull table[145] != cow 146 table[146] rỗng Nếu giá trị cow có trong 147 bluejay bảng, chúng ta đã tìm ra nó 148 owl Ngược lại, giá trị đó không ở ... trong bảng 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 13
Giải pháp 1: Ví dụ 4, Thêm Giả sử chúng ta thêm giá ... trị hawk vào bảng băm 141 Các bước 142 robin hashCode(hawk) = 143 143 sparrow table[143] không rỗng 144 hawk table[143] != hawk 145 seagull table[144] không rỗng 146 table[144] == hawk 147 bluejay hawk đã có trong bảng, 148 owl do đó không cần thêm ... vào 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 14
Giải pháp 1: Ví dụ 5, Thêm Giả sử: ... Bạn muốn thêm cardinal vào 141 bảng băm hashCode(cardinal) = 147 142 robin Bảng băm có tất cả 148 phần 143 sparrow tử 144 hawk Vị trí 147 và 148 không rỗng 145 seagull Giải pháp: Xem bảng băm như một vòng 146 tròn; sau 148 trở lại 0 147 bluejay Do đó, cardinal sẽ được thêm 148 owl vào vị trí 0 (hay 1, hay 2, hay ...) 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 15
Giải pháp 1: Ví dụ 6, Xóa Giả sử: Bạn muốn xóa owl ... hashCode(bluejay) = 147 0 cardinal hashCode(owll) = 147 142 ... hashCode(cardinal) = 147 143 sparrow Bảng băm có tất cả 148 phần tử 144 hawk Nếu xóa vị trí 148 thì sẽ không tìm 145 seagull được cardinal 146 Giải pháp: 147 bluejay Di chuyển cardinal về vị trí 148 148 owl 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 16
Hiệu quả Bảng băm thực sự có hiệu quả không ngờ Thậm chí bảng đã đầy khoảng 70%, số lần tìm kiếm khi đụng độ chỉ là 2 hay 3 lần Bằng các phân tích toán học phức tạp đã chứng minh rằng chi phí để thêm hay tìm kiếm trong bảng băm chỉ là O(1) Thâm chí khi bảng băm đã đầy, hiệu quả cũng vẫn cao 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 17
Cài đặt Qui ước hàm băm f(x) Kích thước bảng băm: M Số lượng phần tử thực sự trong bảng băm: N Khởi tạo Cho bảng băm trống N=0; For (i=0;i
Cài đặt (tt) Thêm phần tử x vào bảng băm trả về vị trí đã thêm vào If (N == M-1) // Thông báo đã đầy Else { i = f(x); While ((a[i].Key -1) && (a[i].Key x)) { i=(i+1) % M; } if (a[i].Key x) { a[i].Key = x; N++; } return i; } 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 19
Cài đặt (tt) Tìm phần tử x vào bảng băm trả về vị trí tìm được i = f(x); While ((a[i].Key -1) && (a[i].Key x)) { i=(i+1) % M; } if (a[i].Key == x) return i; else return M; 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 20