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 = 2p 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 = 2p, for some integer p, could be (and in fact, favorably) used.

Answer 1

Division method

In Hash function, the key must be transformed into integer. The value is to be in between 0-(m-1).

Example:

hash table has size m = 12 , the key is k = 100, then h(k) = 4. it require only single division operation so it is quite fast.

m should not be a power of 2 (m = 2^p)

h(k) is the p lowest-order bits of k.

probability distribution on keys makes all low-order p-bit patterns equally likely, it is better that the hash function depend on all the bits of the key.

the value of m should not be close to the exact power of 2.

multiplication method

multiplication method for creating hash functions.

multiply key k by a constant A (range 0 < A < 1) . Then, we multiply this value by m .

In short, the hash function is

h(k) = ⌊m(kA mod 1)⌋,

the value of A should not be close to 0 or 1.

the value of m is not critical. choose m = 2^p.

Example:

Knuth says good value for A is 0.618033

k = 123456, m = 10000,

h(k) = 10000 (123456 * 0.61803 mod 1) = 10000 (76300.00411mod 1)

= 41.151 = 41