Re: the bit manipulation problem in multiplicative hashing.
 From: Ben Bacarisse <ben.usenet@xxxxxxxxx>
 Date: Tue, 05 May 2009 12:02:43 +0100
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 02^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) = mostsignificant '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.

Ben.
.
 FollowUps:
 Re: the bit manipulation problem in multiplicative hashing.
 From: robin
 Re: the bit manipulation problem in multiplicative hashing.
 From: Pascal J. Bourguignon
 Re: the bit manipulation problem in multiplicative hashing.
 References:
 the bit manipulation problem in multiplicative hashing.
 From: mohangupta13
 the bit manipulation problem in multiplicative hashing.
 Prev by Date: Re: Text indexing problem.
 Next by Date: Re: the bit manipulation problem in multiplicative hashing.
 Previous by thread: the bit manipulation problem in multiplicative hashing.
 Next by thread: Re: the bit manipulation problem in multiplicative hashing.
 Index(es):
Relevant Pages
