PHÉP BĂM (Hash Function)
Định nghĩa:
Trong hầu hết các ứng dụng, khoá được dùng như một phương thức để truy xuất dữ liệu. Hàm băm được dùng để ánh xạ giá trị khóa khoá vào một dãy các địa chỉ của bảng băm (hình 1).
Hình 1
Khóa có thể là dạng số hay số dạng chuỗi. Giả sử có 2 khóa phân biệt ki và kj nếu h(ki)=h(kj) thì hàm băm bị đụng độ.
Một hàm băm tốt phải thỏa mãn các điều kiện sau:
Tính toán nhanh.
Các khoá được phân bố đều trong bảng.
Ít xảy ra đụng độ.
Xử lý được các loại khóa có kiểu dữ liệu khác nhau
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.
Như vậy h(k) sẽ nhận: 0,1,2,…,m-1.
Việc chọn m sẽ ảnh hưởng đến h(k).
Nếu chọn m=2p thì giá trị của h(k) sẽ là p bit cuối cùng của k trong biểu diễn nhị phân.
Nếu chọn m=10p thì giá trị của h(k) sẽ là p chữ số cuối cùng trong biểu diễn thập phân của k.
Trong 2 ví dụ trên giá trị h(k) không phụ thuộc đầy đủ vào khóa k mà chỉ phụ thuộc vào p bít (p chữ số) cuối cùng trong khóa k. Tốt nhất ta nên chọn m sao cho h(k) phụ thuộc đầy đủ và khóa k. Thông thường chọn m là số nguyên tố.
VD: Bảng băm có 4000 mục, chọn m = 4093
Hàm Băm sử dụng Phương pháp nhân
h(k) = ⎣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
Theo Knuth thì chọn A bằng giá trị sau:
A=( -1)/2=0.6180339887…
m thường chọn m = 2p
VD: k=123456; m=10000
H(k)= ⎣10000 (123456* 0.6180339887 mod 1) ⎦
H(k)= ⎣10000 (76300.0041089472 mod 1) ⎦
H(k)= ⎣10000 (0.0041089472) ⎦
H(k)=41
Phép băm phổ quát (unisersal hashing)
Việc chọn hàm băm không tốt có thể dẫn đến xác suất đụng độ cao.
Giải pháp:
- Lựa chọn hàm băm h ngẫu nhiên.
- 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.
Cho H là một tập hợp hữu hạn các hàm băm: ánh xạ các khóa k từ tập khóa U vào miền giá trị {0,1,2,…, m-1}. Tập H là phổ quát nếu với mọi ∀ f ∈ H và 2 khoá phân biệt k1,k2 ta có xác suất: Pr{f(k1) = f(k2)} <= 1/m