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à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.
Nội dung trích xuất từ tài liệu:
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àn9-Apr-06 Nguyễn Văn Toàn - CTDL 2 1Dẫ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 2Bă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) = 2589-Apr-06 Nguyễn Văn Toàn - CTDL 2 3Ví 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 kiwixạ biến đổi khóa thành chỉ số của 1bảng. 2 bananaHà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 strawberry9-Apr-06 Nguyễn Văn Toàn - CTDL 2 4Tạ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 5Cá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ăm9-Apr-06 Nguyễn Văn Toàn - CTDL 2 6Ví dụ về hàm băm không hiệu quảGiả sử hàm băm cung cấpcho chúng ta các giá trị 0 kiwi 1sau: „ 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 strawberry9-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 8Giả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 9Giả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 „ ...