Re: the bit manipulation problem in multiplicative hashing.

mohangupta13 <mohangupta13@xxxxxxxxx> writes:

I was reading the section on multiplicative hashing from "introduction
to algorithms and data structure" form coreman

there he says that we use a hash function as:

h(k)= floor( m* [k*A mod 1] ) ,...........................(i)

I don't have the book. Can you check the formula carefully. This
looks wrong. Anything mod 1 is either 0 or 1 so h(k) only has two
values: 0 and m.

where m is table size and should be like 2^p .
k is the key represented by a word of size 'w' (i.e between 0-2^w )
A is a fractional number given as s/2^w where 0< s>2^w
Till here its all fine but
now he says that the calculation of h(k) can be done fast on most
computers with word size 'w'-bit long as :

k * s = r1 * 2^w + r2 * 2^w , where 'r1r2' is the bit
representation of k*s

This also looks wrong. You need k*s = r1r2 = 2^w * (r1 + r2) which is
not, in general true.

h(k) = most-significant 'p' bits of r2 .

Can anyone please explain how these bit manipulations results in h(k)
as given by the above formula (i)

Sorry, not as they stand, no. Maybe someone else can see what it
intended but I can't.