1.3) Một số phương pháp xây dựng hàm băm
a. Hàm băm dạng bảng tra:
Hàm băm có thể tổ chức ở dạng bảng tra (còn gọi là bảng truy xuất) hoặc thông dụng nhất là ở dạng công thức.
Ví dụ sau đây là bảng tra với khóa là bộ chữ cái, bảng băm có 26 địa chỉ từ 0 đến 25. Khóa a ứng với địa chỉ 0, khoá b ứng với địa chỉ 1,… , z ứng với địa chỉ 25.
Hình 1.3 Hàm băm dạng bảng tra được tổ chức dưới dạng danh sách kề.
b. Hàm băm sử dụng phương pháp chia
• Dùng số dư:
h(k) = k mod m
k là khoá, m là kích thước của bảng.
vấn đề chọn giá trị m
• Nếu chọn m= 2n thông thường không tốt vì h(k) = k mod 2n sẽ chọn cùng n bits thấp của k nên chọn m là nguyên tố (tốt) gần với 2n
Ví dụ: Ta có tập khoá là các giá trị số gồm 3 chữ số, và vùng nhớ cho bảng địa chỉ có khoảng 100 mục, như vậy ta sẽ lấy hai số cuối của khoá để làm địa chỉ theo phép chia lấy dư cho 100 : chẳng hạn 325 Mod 100 = 25
Tuy nhiên ta nhận thấy nếu hàm băm dùng công thức như trên thì địa chỉ của khoá tính được chỉ căn cứ và 2 ký số cuối. Vì thế, để hàm băm có thể tính địa chỉ khoá một cách "ngẫu nhiên" hơn ta nên chọn m=97 thay vì 100
c. Hàm băm sử dụng phương pháp nhân
• Sử dụng công thức
h(k) = floor(m (k A mod 1))
k là khóa, m là kích thước bảng, A là hằng số: 0 < A < 1
• Chọn m và A
Ta thường chọn m = 2n
Theo Knuth chọn A = 1/2(sqrt(5) -1) 0.618033987 được xem là tốt
d. Dùng hàm băm phổ quát
Một tập các hàm băm H là phổ quát (universal ) nếu hH và 2 khoá k, l ta có xác suất: Pr{h(k) = h(l)} <= 1/m ,• với m là kích thước bảng
Để xác suất xảy ra đụng độ thấp, khởi tạo một tập các hàm băm H phổ quát và từ đó h được chọn ngẫu nhiên.
Ví dụ: Giả sử nếu khoá là một số nguyên, dương và HK(key) là một số nguyên với một digit từ 0..9, Thế thì, hàm băm sẽ dùng toán tử modulo-10 để trả về giá trị tương ứng của một khoá. Chẳng hạn: nếu khoá=49 thì HF(49)=9.