Double hashing takes on the following form:

h(k)=(h’(k)  i * h’’(k)) mod m

If m is a table size that is relatively prime to h’’(k), then wouldn’t choosing a h’’(k) value that is a prime number but larger than the table size still makes it relatively prime? Just that for every iteration, the step size wraps around the whole table again. Are there any complications if one does not use h’’(k) to be an integer less than m?

CodePudding user response：

Choosing h''(k) larger than m works just fine, but works out to be the same as having picked h''(k) % m instead. And the latter is easier to calculate with. So it makes no sense to pick a larger value.

CodePudding user response：

You choose the range of h''(k), but you do not choose the value h''(k) for any particular key.

If m is prime, then the hash can produce any number in [1,m-1], and you'll be sure that it's relatively prime to m. If you choose from a larger range, though, then you could get m itself, which would be 0 mod m, and that wouldn't work.