Trong phần này, chúng ta sẽ xem kỹ thuật Double Hashing trong lược đồ địa chỉ mở là gì. Có một hàm băm thông thường h´ (x):U → {0, 1 ,. . ., m - 1}. Trong lược đồ định địa chỉ mở, hàm băm thực tế h (x) đang sử dụng hàm băm thông thường h ’(x) khi không gian trống, sau đó thực hiện một hàm băm khác để có một số khoảng trống để chèn.
$$ h_ {1} (x) =x \:mod \:m $$
$$ h_ {2} (x) =x \:mod \:m ^ {\ prime} $$
$$ h (x, i) =(h ^ {1} (x) + ih ^ {2}) \:mod \:m $$
Giá trị của i =0, 1 ,. . ., m - 1. Vì vậy, chúng tôi bắt đầu từ i =0, và tăng điều này cho đến khi chúng tôi nhận được một không gian trống. Vì vậy, ban đầu khi i =0, thì h (x, i) giống với h´ (x).
Ví dụ
Giả sử chúng ta có một danh sách kích thước 20 (m =20). Chúng tôi muốn đưa một số yếu tố vào kiểu thăm dò tuyến tính. Các phần tử là {96, 48, 63, 29, 87, 77, 48, 65, 69, 94, 61}
$$ h_ {1} (x) =x \:mod \:20 $$
$$ h_ {2} (x) =x \:mod \:13 $$
x h (x, i) =(h1 (x) + ih2 (x)) mod 20
Bảng băm
