From: Nate Smith <nsmith5@...>
Date: 2004-08-20T22:19:13+09:00
Subject: Re: Hash values too big to fit into buckets

On Fri, 2004-08-20 at 06:46, Robert Klemme wrote:
> "Nate Smith" <nsmith5@nist.gov> schrieb im Newsbeitrag
> news:1092944939.2849.45.camel@circuit.eeel.nist.gov...
> > On Thu, 2004-08-19 at 15:36, Nate Smith wrote:
> > > Hello,
> > >
> > > Is there any way to get around values being too big (being assigned as
> > > bignums) to fit into a hash? (Not a Hash class, but a hash fixnum
> > > assigned to each bucket). For example, in my LR parser, each
> > > Production's hash is composed of the hashes of its elements:
> > >
> > > def hash    #   Production#hash
> > >     @nonTerminal.hash + @action.hash + @expansion.hash
> > > end
> >
> > Well dividing the resulting hash value by 2 fixes the problem.. but such
> > a hack probably has bad side effects down the road.... >:-)
> 
> The usual solution is to take the remainder like in
> 
> Limit = 2**30
> 
> def hash    #   Production#hash
>     (@nonTerminal.hash + @action.hash + @expansion.hash) % Limit
> end
> 
> Typically I use shifting to achieve a bit better distribution of hash values
> like in
> 
> def hash    #   Production#hash
>     (@nonTerminal.hash + @action.hash << 3 + @expansion.hash << 7) % Limit
> end

Very good stuff indeed. Thanks for the help.

Nate