From: Seth Kurtzberg <seth@...>
Date: 2003-03-03T12:36:43+09:00
Subject: Re: Is Ruby slower?

On Sunday 02 March 2003 05:26 pm, Bill Kelly wrote:
> Hi,
>
> From: "Mauricio Fern�ndez" <batsman.geo@yahoo.com>
>
> >  * however, a perf. increase of 1-3% can be achieved by setting the
> >    number of bins in the hash to be a power of 2, so that we can later
> >    use bitwise AND instead of the modulus operator [I assume our hash is
> >    good enough not to increase the num. of collisions a lot]
>
> Sorry if this contribution is "newbie-like" as I'm not an expert
> in any kind of mathematical/analytical field, but... Just wanted
> to mention that my Sedgewick algorithms book goes into a bit of
> detail on why prime numbers should generate better distributed
> hash values using the modulo operator than powers-of-two...

Mathematically, that is true.  However, if you analyze the computational 
aspects, the impact is not obvious, as you are decreasing collisions at the 
cost of a more expensive hash generation algorithm.  I'm not saying that it 
definitely wouldn't pay off, but the answer is not obvious, and my belief is 
that there would be a small net loss.

>
>
> HTH,
>
> Bill

-- 
Seth Kurtzberg
M. I. S. Corp.
480-661-1849
seth@cql.com