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

Băm không đối xứng (Asymmetric Hashing) trong cấu trúc dữ liệu


Xem kỹ thuật Asymmetric Hashing. Bảng băm chia thành d khối, mỗi khối dài n/d. Giá trị dò xi (0 ≤ i ≤ d) lấy đều từ {i*n/d, …, (i+1)*n/(d-1)}. Giống multiple-choice hashing, để chèn x, thuật toán kiểm tra độ dài danh sách A[x0], A[x1], …, A[xd-1]. Sau đó gắn x vào danh sách ngắn nhất. Nếu hòa, chèn vào danh sách chỉ số nhỏ nhất.

Theo Vocking, kỳ vọng độ dài danh sách dài nhất cho asymmetric hashing:

$$E[W]\leq\frac{\ln\ln n}{d\ln\phi_{2}}+O(1)$$

Hàm φd là khái quát tỷ số vàng, φ2 = (1+√5)/2.