From: Mauricio Fernandez <mfp@...>
Date: 2007-01-30T20:48:55+09:00
Subject: Re: Sane #hash implementation?

[I'm resending this since the ML server is dropping some of my messages to
this thread for some reason.]

On Tue, Jan 30, 2007 at 04:26:18PM +0900, Shot (Piotr Szotkowski) wrote:
> Eric Hodel:
> 
> > On Jan 29, 2007, at 14:38, Shot (Piotr Szotkowski) wrote:
> 
> >> I'm stuck when it comes to Block#hash, though; I need these to be true:
> >> Block.new.hash == Block.new.hash
> >> Block.new([1,2]).hash == Block.new([1,2]).hash
> 
> > Try:
> 
> > class Block
> >   def hash
> >     to_a.hash
> >   end
> > end
> 
> Thanks a lot, Eric! This is the d'oh! solution I was looking for. :)

It's not a correct one though.

  require 'set'
  a = Set.new(0..1000)
  b = Set.new((0..1000).sort_by{rand})
  a == b                                             # => true
  a.to_a.hash                                        # => 31141761
  b.to_a.hash                                        # => 374826672

(The order of the elements in Hash#to_a can change.)


Try this, it's O(n ln n) but actually works

  require 'set'
  class Block < Set
    def hash
      map{|x| x.hash}.sort.hash
    end
  end
  a = Block.new(0..1000)
  b = Block.new((0..1000).sort_by{rand})
  a == b                                             # => true
  a.hash                                             # => 944434529
  b.hash                                             # => 944434529


-- 
Mauricio Fernandez  -   http://eigenclass.org   -  singular Ruby