From: Robert Klemme <bob.news@...>
Date: 2004-08-20T19:46:00+09:00
Subject: Re: Hash values too big to fit into buckets


"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


Note:

>> (2**30-1).class
=> Fixnum
>> (2**30).class
=> Bignum

Btw: Does anybody know a reason why Fixnum::MAX and MIN aren't defined?  The
only reason that comes to mind is that usually these limits are irrelevant
since all math functions automatically take care of conversions between
Fixnum and Bignum.

Kind regards

    robert