algorithmdouble-hashing

Double hashing in open addressing, what hash function and table length


In Cormen's book "Introduction to algorithms" I read that double hashing (in open addressing) function is in the form of:

h(k, i) = (h1(k) + i * h2(k)) mod m

where k is a key, i is a next index in the case of a collision, m is the table length and hX are hash functions.

He says that the main problem in double hashing is to utilize all indices in the table. To solve that problem we should set m to the power of 2 and h2 function should return odd values. Why (I can't see him explaining it)?


Solution

  • The general rule is that modulo m, adding h_2(k) repeatedly is a cycle that repeats with period m/GCD(m, h_2(k)). If there are no common factors between m and h_2(k) then it will repeat with period m which means that you can reach all m indices. So you want no common factors.

    The "no common factors" rule is easily satisfied by making m a power of 2 and h_2(k) odd.