Question

For the division method for creating hash functions,

map a key k into one of m slots by taking the remainder of k divided by m. The hash function is:

                        h(k) = k mod m,

            where m should not be a power of 2.

For the Multiplication method for creating hash functions,

            The hash function is h(k) = _└ m(kA –_└ k A _┘) _┘ = _└ m(k A mod 1) _┘

            where “k A mod 1” means the fractional part of k A; and a constant A in the range

0 < A < 1.

An advantage of the multiplication method is that the value of m is not critical.

Choose m = 2^p for some integer p.

Give your explanations for the following questions:

(1) why m should not be a power of 2 in the division method for creating hash function; and

            (2) why m = 2^p, for some integer p, could be (and in fact, favorably) used.

Answer 1