Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> Lập Trình

Băm nhân (Hashing by Multiplication) trong cấu trúc dữ liệu


Ở đây ta thảo luận về băm với phương pháp nhân. Hàm băm:

h(x) = ⌊m * x * A⌋ mod m

A là hằng số thực. Ưu điểm: giá trị m không quá quan trọng, có thể lấy m là lũy thừa của 2. Mặc dù mọi giá trị A đều cho hàm băm, nhưng một số giá trị tốt hơn.

$$A=\frac{\sqrt5-1}{2}=0.61803398$$

Dù chọn A gì, nguyên lý hộp chim (pigeonhole principle) ngụ ý nếu u ≥ n*m, sẽ tồn tại giá trị băm i và tập S ⊆ U kích thước n, sao cho h(x) = i với mọi x trong S.

Vậy trường hợp xấu nhất của băm nhân cũng tệ như băm chia.