tailieunhanh - BẢNG BĂM (Hashing Table)

Giả sử ta có 100 số nguyên có giá trị bất kỳ nằm trong khoảng từ 0 . . 999 Nếu sử dụng mảng a gồm 1000 phần tử để lưu trữ các số nguyên này sao cho a[i] = i thì số lần tìm kiếm số nguyên bất kỳ trong 100 số này là 1 lần Tuy nhiên, chỉ có 1/10 bộ nhớ được sử dụng, dẫn đến lãng phí bộ nhớ Phép biến đổi khóa là phương pháp tham khảo trực tiếp các phần tử trong một bảng (bảng băm) thông qua việc biến đổi số học trên. | BẢNG BĂM Hashing Table Chương 5 1 Khái niệm Giả sử ta có 100 số nguyên có giá trị bất kỳ nằm trong khoảng từ 0 . . 999 Nếu sử dụng mảng a gồm 1000 phần tử để lưu trữ các số nguyên này sao cho a i i thì sốJần tìm kiếm số nguyên bất kỳ trong 100 số này là 1 lần Tuy nhiên chỉ có 1 10 bộ nhớ được sử dụng dẫn đến lãng phí bộ nhớ Phép biến đổi khóa là phương pháp tham khảo trực tiếp các phần tử trong một bảng bảng băm thông qua việc biến đổi số học trên những khoá để có được địa chỉ tương ứng của những phần tử ở trong bảng 2 Khái niệm Phép biến đổi khoá là một phương pháp giải quyêt tốt về thời gian và vùng nhớ Tổ chức dữ liệu được dùng cho phép biên đổi khoá là cấu trúc bảng bảng băm Để thực hiện phép biên đổi khoá ta cần hai bước 1. Bước 1 Tính toán việc biên đổi số học hàm H nào đó để biên đổi khoá cần tìm thành địa chỉ trong bảng. Trong bước này có thể có hai hay nhiều khoá khác nhau thông qua hàm H sẽ cho cùng một địa chỉ trong bảng