Balanced allocations and double hashing
Balanced allocations and double hashing
With double hashing, for an item x, one generates two hash values f(x) and g(x), and then uses combinations (f(x) +ig(x)) mod n for i=0,1,2,... to generate multiple hash values from the initial two. We show that the performance difference between double hashing and fully random hashing appears negligible in …