Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 9: Bảng băm (Hash table)

9-Apr-06 Nguyễn Văn Toàn - CTDL 2 1 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 2 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 3 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 4 Ví dụ về hàm băm (hash function) Hàm băm thực chất là một ánh xạ biến đổi khóa thành chỉ số của bảng. Hàm băm cho chúng ta các giá trị như sau: hashCode("apple") = 5 hashCode("watermelon") = 3 hashCode("grapes") = 8 hashCode("cantaloupe") = 7 hashCode("kiwi") = 0 hashCode("strawberry") = 9 hashCode("mango") = 6 hashCode("banana") = 2 kiwi banana watermelon apple mango cantaloupe grapes strawberry 0 1 2 3 4 5 6 7 8 9 Khóa Chỉ số 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 5 Tại sao lại dùng bảng băm (hash tables)? Bảng băm là một mảng lưu giá trị. Thông thường người ta sử dụng cặp khóa/giá trị trong bảng „ Key để tìm một vị trí trong mảng „ Value: chứa thông tin thực sự ta muốn lưu robin sparrow hawk seagull bluejay owl . . . 141 142 143 144 145 146 147 148 robin info sparrow info hawk info seagull info bluejay info owl info Key Value 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 6 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 7 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ị sau: „ hash("apple") = 5 hash("watermelon") = 3 hash("grapes") = 8 hash("cantaloupe") = 7 hash("kiwi") = 0 hash("strawberry") = 9 hash("mango") = 6 hash("banana") = 2 hash("honeydew") = 6 kiwi banana watermelon apple mango cantaloupe grapes strawberry 0 1 2 3 4 5 6 7 8 9 • “Điều gì đã xảy ra”? 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 8 Đụ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 9 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 10 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 Các bước: „ hashCode(seagull) = 143 „ table[143] đã có rồi / „ table[143] != seagull „ table[144] đã có rồi / „ table[144] != seagull „ table[145] rỗng Do đó, đặt seagull ở vị trí 145 robin sparrow hawk bluejay owl . . . 141 142 143 144 145 146 147 148 . . . seagull 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 11 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 12 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 băm Các bước: „ hashCode(seagull) = 143 „ table[143] không rỗng „ table[143] != seagull „ table[144] không rỗng „ table[144] != seagull „ table[145] không rỗng „ table[145] == seagull ! Chúng ta tìm thấy giá trị seagull ở vị trí 145 robin sparrow hawk bluejay owl . . . 141 142 143 144 145 146 147 148 . . . seagull 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 13 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 Các bước: „ hashCode(cow) = 144 „ table[144] không rỗng „ table[144] != cow „ table[145] không rỗng „ table[145] != cow „ table[146] rỗng Nếu giá trị cow có trong bảng, chúng ta đã tìm ra nó Ngược lại, giá trị đó không ở trong bảng robin sparrow hawk bluejay owl . . . 141 142 143 144 145 146 147 148 . . . seagull 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 14 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 Các bước „ hashCode(hawk) = 143 „ table[143] không rỗng „ table[143] != hawk „ table[144] không rỗng „ table[144] == hawk hawk đã có trong bảng, do đó không cần thêm vào robin sparrow hawk seagull bluejay owl . . . 141 142 143 144 145 146 147 148 . . . 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 15 Giải pháp 1: Ví dụ 5, Thêm Giả sử: „ Bạn muốn thêm cardinal vào bảng băm „ hashCode(cardinal) = 147 „ Bảng băm có tất cả 148 phần tử „ Vị trí 147 và 148 không rỗng Giải pháp: „ Xem bảng băm như một vòng tròn; sau 148 trở lại 0 „ Do đó, cardinal sẽ được thêm vào vị trí 0 (hay 1, hay 2, hay ...) robin sparrow hawk seagull bluejay owl . . . 141 142 143 144 145 146 147 148 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 16 Giải pháp 1: Ví dụ 6, Xóa Giả sử: „ Bạn muốn xóa owl hashCode(bluejay) = 147 hashCode(owll) = 147 hashCode(cardinal) = 147 „ Bảng băm có tất cả 148 phần tử „ Nếu xóa vị trí 148 thì sẽ không tìm được cardinal Giải pháp: „ Di chuyển cardinal về vị trí 148 sparrow hawk seagull bluejay owl . . . 0 142 143 144 145 146 147 148 . . . cardinal 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 17 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 18 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<N;i++) A[i].Key=-1 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 19 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 20 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 21 Cài đặt (tt) Xóa // Tìm // Xóa a[i].Key=-1; N--; While (a[i].Key -1 ) { a[i].Key = a[(i-1) % M].Key-1; i = (i-1) % M; } A[i].Key=-1 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 22 Giải pháp #2: Băm lại (Rehashing) Khi đụng độ xảy ra, một giải pháp khác là rehash: tính toán một hàm băm khác „ Do chúng ta có thể phải băm lại nhiều lần, chúng ta cần một dãy hàm dễ tính toán Ví dụ: Khi băm chuỗi (String), chúng ta có thể lấy giá trị trả về của hàm băm trước cộng vào chiều dài của chuỗi để tạo thành chỉ số mới. f’(x)=f(x) + strlen(x) Băm lại là một cách tiếp cận không thông dụng. 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 23 Giải pháp #3: Băm dùng DSLK Các giải pháp trước dùng bảng băm mở (open hashing): tất cả các mục được đưa vào trong một mảng bình thường Giải pháp khác là làm cho mỗi vị trí của bảng là header của một DSLK. DSLK này sẽ chứa các giá trị băm có cùng vị trí robin sparrow hawk bluejay owl . . . 141 142 143 144 145 146 147 148 . . . seagull 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 24 Giải pháp 3: Phương pháp nối kết Có các phương pháp nối kết trực tiếp (Direct Chaining, Seperate Chaining) M << N Có các phương pháp nối kết hợp nhất (Coalesced Chaining) M = N 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 25 Hết – Cảm ơn