Hash values too big to fit into buckets

[Nate Smith]

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

When @expansion.hash is very large, the hash values get large, and
values like: 67 4 -946450216 for @nonTerminal.hash, @action.hash, and
@expansion.hash, respectively, generate the following error:

in `hash': bignum too big to convert into `int' (RangeError)

My gut tells me there's no way to get around this, and the only way is
to restructure production's hash to be something smaller. Anyone have
any ideas? Thanks

Nate

 

[Florian Gross]

Hello,
Moin!

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

Maybe like this?

def hash
[@nonTerminal, @action, @expansion].hash
end

Regards,
Florian Gross

 

[Nate Smith]

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

 

[Nate Smith]

Hello,
Moin!

Hallo!

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

Maybe like this?

def hash
[@nonTerminal, @action, @expansion].hash
end

Ah, great. That didn't work completely (but sent me on the path that got
to this, which fixed the problem):

[@nonTerminal.hash, @action.hash, @expansion.hash].hash.hash

Thanks much.

Nate

 

[nobu.nokada]

Hi,

At Fri, 20 Aug 2004 04:36:23 +0900,
Nate Smith wrote in [ruby-talk:109851]:

When @expansion.hash is very large, the hash values get large, and
values like: 67 4 -946450216 for @nonTerminal.hash, @action.hash, and
@expansion.hash, respectively, generate the following error:

in `hash': bignum too big to convert into `int' (RangeError)

It seems to work for me.

$ cat a.rb
class X; def hash; 1 << 34; end; end
x = X.new
p x.hash, x.hash.class
h = {x => 1}
p h[x]

$ ruby16 -v a.rb
ruby 1.6.8 (2003-10-15) [i686-linux]
17179869184
Bignum
1

$ ruby18 -v a.rb
ruby 1.8.2 (2004-08-19) [i686-linux]
17179869184
Bignum
1

 

[Robert Klemme]

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

 

[Nate Smith]

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

 

[Robert Klemme]

Very good stuff indeed. Thanks for the help.

While rereading this one more remark comes to mind: Using bitwise and is
probably more efficient than modulus calculation in this case (meaning a
power of 2 as limit). So that would yield:

PATTERN = 2**30 - 1 # all 1's

def hash # Production#hash
(@nonTerminal.hash + @action.hash << 3 + @expansion.hash << 7) & PATTERN
end

Kind regards

robert