Hash values too big to fit into buckets

Discussion in 'Ruby' started by Nate Smith, Aug 19, 2004.

  1. Nate Smith

    Nate Smith Guest

    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
     
    Nate Smith, Aug 19, 2004
    #1
    1. Advertisements

  2. Maybe like this?

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

    Regards,
    Florian Gross
     
    Florian Gross, Aug 19, 2004
    #2
    1. Advertisements

  3. Nate Smith

    Nate Smith Guest

    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, Aug 19, 2004
    #3
  4. Nate Smith

    Nate Smith Guest

    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
     
    Nate Smith, Aug 19, 2004
    #4
  5. Nate Smith

    nobu.nokada Guest

    Hi,

    At Fri, 20 Aug 2004 04:36:23 +0900,
    Nate Smith wrote in [ruby-talk:109851]:
    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
     
    nobu.nokada, Aug 20, 2004
    #5
  6. 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
     
    Robert Klemme, Aug 20, 2004
    #6
  7. Nate Smith

    Nate Smith Guest

    Very good stuff indeed. Thanks for the help.

    Nate
     
    Nate Smith, Aug 20, 2004
    #7
  8. 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
     
    Robert Klemme, Aug 21, 2004
    #8
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.