3.5.2 Multiplication Method

There are two steps:

1.

Multiply the key k by a constant A in the range 0 < A < 1 and extract the fractional part of kA

2.

Multiply this fractional part by m and take the floor. 

          h(k) = $$\lfloor$$m(kA mod 1)$$\rfloor$$

where

$$\lfloor \rfloor$$

$$\lfloor \lfloor \rfloor \rfloor$$

 
 

• Advantage of the method is that the value of m is not critical. We typically choose it to be a power of 2: 

                                                                                                                                                    m = 2^p

for some integer p so that we can then easily implement the function on most computers as follows:

Suppose the word size = w. Assume that k fits into a single word. First multiply k by the w-bit integer $\lfloor$A.2^w$\rfloor$. The result is a 2w - bit value 

r₁2^w + r₀ where r₁ is the high order word of the product and r₀ is the low order word of the product. The desired p-bit hash value consists of the p most significant bits of r₀.
• Works practically with any value of A, but works better with some values than the others. The optimal choice depends on the characteristics of the data being hashed. Knuth recommends 
A$$\simeq$$$${\frac{\sqrt{5}-1}{2}}$$ = 0.6180339887...  (Golden Ratio)