1.Đặt vấn đề
Vấn đề đặt ra là, chúng ta có một tập dữ liệu, chúng ta cần đưa ra một cấu trúc dữ liệu cài đặt tập dữ liệu này sao cho các phép toán tìm kiếm, xen, loại được thực hiện hiệu quả.
Các thuật toán tìm kiếm đều dựa vào việc so sánh giá trị khoá (Key) của phần tử cần tìm với các giá trị khoá trong tập các phần tử, thao tác này
- Phụ thuộc kích thước của tập các phần tử
- Thời gian tìm kiếm không nhanh do phải thực hiện nhiều phép so sánh có thể không cần thiết ( O(n), O(logn), …)
=> Có phương pháp lưu trữ nào cho phép thực hiện tìm kiếm với hiệu suất cao hơn không ( độ phức tạp hằng số)?
Sau đây chúng ta trình bày một kỹ thuật để lưu giữ một tập dữ liệu, đó là phương pháp băm.
2.Bảng băm
Ví dụ: Giả sử ta có một tập phần tử gồm các giá trị khoá bất kỳ được tổ chức lưu trữ dưới dạng bảng chỉ mục có cỡ SIZE như sau gọi là bảng truy xuất trực tiếp (Direct access table)
- Phần tử có giá trị khoá k được lưu trữ tương ứng tại vị trí thứ k trong bảng chỉ mục
- Để tìm kiếm một phần tử nào đó ta sẽ dựa vào khoá của nó và tra trong bảng chỉ mục, nếu tại vị trí đó có phần tử thì chính là phần tử cần tìm, nếu không có phần tử nào có nghĩa là phần tử cần tìm không có trong bảng chỉ mục
- Thời gian tìm kiếm là hằng số O(1)
Khi một dữ liệu có khóa là k, nếu tính địa chỉ theo k ta thu được chỉ số i, 0 ≤ i ≤ SIZE-1, thì dữ liệu sẽ được lưu trong thành phần mảng T[i].
Như vậy hàm băm là một ánh xạ h từ tập các giá trị khóa của dữ liệu vào tập các số nguyên {0, 1, 2, …, SIZE-1}
h:K -> {0, 1, 2, …, SIZE-1}
với K là tập các giá trị khóa, h(k) được gọi là giá trị băm và dữ liệu được lưu trong T[h(k)].
Trong thực tế một hàm băm có thể ánh xạ hai hay nhiều giá trị khóa tới cùng một thành phần mảng mà mỗi thành phần mảng chỉ cho phép lưu một dữ liệu ! Hiện tượng này được gọi là va chạm (collision). Vấn đề đặt ra là giải quyết sự va chạm như thế nào?
· Các tiêu chuẩn để thiết kế một hàm băm tốt :
- Tính được dễ dàng và nhanh địa chỉ ứng với mỗi khóa
- Đảm bảo ít xảy ra va chạm
3. Các phương pháp thiết kế hàm băm
3.1. Phương pháp chia
Phương pháp này đơn giản là lấy phần dư của phép chia khóa k cho cỡ bảng băm SIZE làm giá trị băm.
Int hash(int k)
{
Return k % SIZE;
}
Để hạn chế va chạm chúng ta cần biết cách lựa chọn kích cỡ bảng băm, thường lựa chọn SIZE là số nguyên tố, có dạng 4k + 3
3.2. Phương pháp nhân
Phương pháp nhân có ưu điểm là ít phụ thuộc vào cỡ của bảng băm
H(k) = [{α*k }.SIZE]
Trong thực tế người ta thường chọn hằng số α như sau :
α = ϕ-1 
0.61803399
0.618033993.3. Hàm băm cho các giá trị khóa là xâu kí tự
Trước hết chúng ta chuyển đổi các xâu kí tự thành các số nguyên.
Các ký tự trong bảng mã ASCII gồm 128 kí tự từ 0..127, do đố một xâu kí tự có thể xem như là 1 số trong hệ đếm 128.
-> VD : ‘NOTE’ ‘N’ * 1283 + ‘O’ * 1282 + ‘T’ * 128 + ‘E’ = 78 * 1283 + 79 * 1282 + 84 * 128 + 69
Trong thực tế một xâu kí tự thường được tạo thành từ 26 chữ cái và 10 chữ số, do đó chúng tat hay 128 bằng 37 và tính số nguyên ứng với xâu kí tự theo luật Horner. Ví dụ :
‘NOTE’ -> 78*373 + 79*372 + 84*37 + 69 = ((78*37 + 79)*37 + 84)*37 + 69
Unsigned int hash(const string &k,int SIZE)
{
Int value = 0;
For (int i = 0;i < strlen(k);i++)
Value = 37*value + k[i];
Return value % SIZE;
}
4. Các phương pháp giải quyết va chạm
4.1. Phương pháp định địa chỉ mở
Mỗi khi cần xen dữ liệu mới với khóa k vào bảng, nhưng tại vị trí h(k) đã chứa dữ liệu, chúng ta sẽ tiến hành thăm dò 1 số vị trí khác trong mảng để tìm ra một vị trí còn trống và đặt dữ liệu mới vào vị trí đó. Phương pháp này gọi là phương pháp định địa chỉ mở.
4.1.1. Thăm dò tuyến tính
4.1.2. Thăm dò bình phương
4.1.3. Băm kép
4.2. Phương pháp tạo dây chuyền
(Còn tiếp...)
0 nhận xét:
Đăng nhận xét