Double Hashing | Lei Jiang Coding
For double hashing,one popular choice is f(i)=i·hash2(x).
applying a second hash function to x and probe at a distance hash2(x), 2hash2(x),…, and so on.
The function must never evaluate to zero and all cells can be probed.
Hash2(x) = R − (x mod R), R a prime smaller thanTableSize.
If the table size is not prime, it is possible to run out of alternative locations prematurely. However, if double hashing is correctly implemented,it is almost the same as for a random collision resolution strategy.
Read full article from Double Hashing | Lei Jiang Coding
No comments:
Post a Comment