From: Robert Klemme <bob.news@...>
Date: 2004-08-08T17:36:26+09:00
Subject: Re: Sets are not extensional


"Kristof Bastiaensen" <kristof@vleeuwen.org> schrieb im Newsbeitrag
news:pan.2004.08.07.18.15.03.660477@vleeuwen.org...
> On Sun, 08 Aug 2004 00:16:11 +0900, Charles Mills wrote:
>
> > On Aug 7, 2004, at 6:11 AM, Kristof Bastiaensen wrote:
> >
> >> Hi,
> >>
> >> On Fri, 06 Aug 2004 18:08:57 +0000, Csaba Henk wrote:
> >>> [snip]
> >>> I've read the thread spawned by this post, and now I summarize that
> >>> part
> >>> of what was written there which is relevant to my original problem,
and
> >>> wasn't stated there explicitly.
> >>>
> >>>
> >> I think the thread was relevant to your post, since it described what
> >> was causing the bug.  The following should solve the problems (but can
> >> be very slow for large Hashes/Sets):
> >>
> >> class Array
> >>   def hash
> >>     to_a.hash
> >>   end
> >> end
> >>
> > I think you mean:
> >
> > class Hash
> >    def hash
> >      to_a.hash
> >    end
> > end
> >
> > -Charlie
> >
>
> I did.  Thanks!

IMHO a solution that recalculates the hash value on each change is more
efficient.  I imagine something like this (incomplete):

class FixedHash < Hash
  def initialize(*a,&b)
    super
    calc_hash
  end


  def []=(key,val)
    @hc ^= self[key].hash << 3 if has_key? key
    @hc ^= val.hash << 3
    super
  end

  def clear
    super
    calc_hash
  end

  # all other modifying methods must be
  # changed, too

  def hash() @hc end

  private

  HASH_MASK = (1 << 32) - 1

  def calc_hash
    @hc = 0
    each {|k,v| @hc ^= (k.hash ^ (v.hash << 3)) }
    @hc &= HASH_MASK
  end
end


>> h = FixedHash.new
=> {}
>> h2 = FixedHash.new
=> {}
>> 7.times{|i| h[i] = true; h2[6-i] = true }
=> 7
>> h
=> {5=>true, 0=>true, 6=>true, 1=>true, 2=>true, 3=>true, 4=>true}
>> h2
=> {5=>true, 0=>true, 6=>true, 1=>true, 2=>true, 3=>true, 4=>true}
>> h == h2
=> true
>> h.sort
=> [[0, true], [1, true], [2, true], [3, true], [4, true], [5, true], [6,
true]]
>> h2.sort
=> [[0, true], [1, true], [2, true], [3, true], [4, true], [5, true], [6,
true]]
>> h.hash
=> 16
>> h2.hash
=> 16

Kind regards

    robert