# 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 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.

--

Ben.

.

**Follow-Ups**:**Re: the bit manipulation problem in multiplicative hashing.***From:*robin

**Re: the bit manipulation problem in multiplicative hashing.***From:*Pascal J. Bourguignon

**References**:**the bit manipulation problem in multiplicative hashing.***From:*mohangupta13

- 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):