Forum: Ruby hash method how-to?

45196398e9685000d195ec626d477f0e?d=identicon&s=25 Thomas Sawyer (7rans)
on 2010-12-01 19:41
(Received via mailing list)
Are there any good tutorials out there for writing proper #hash
methods?
C5d0fa3fe43c304760ba0c4b63cdb9be?d=identicon&s=25 Niklas Cathor (ncathor)
on 2010-12-01 20:12
(Received via mailing list)
Attachment: signature.asc (835 Bytes)
http://en.wikipedia.org/wiki/Hash_function

in most cases it's the easiest to delegate the hash method to something
else. Example:

class X
  def initialize(name)
    @name = name
  end

  def hash
    @name.hash
  end
end

h = { X.new("foo") => "bar" }
h[X.new("foo")] = "baz" # will overwrite the above
B1b1d33e0655e841d4fd8467359c58d0?d=identicon&s=25 Yossef Mendelssohn (Guest)
on 2010-12-01 20:33
(Received via mailing list)
On Dec 1, 1:10pm, niklas | brueckenschlaeger
<nik...@brueckenschlaeger.de> wrote:
>  def hash
>   @name.hash
>  end
> end
>
> h = { X.new("foo") => "bar" }
> h[X.new("foo")] = "baz" # will overwrite the above

And so will `h['foo'] = 'baz'`.
C5d0fa3fe43c304760ba0c4b63cdb9be?d=identicon&s=25 Niklas Cathor (ncathor)
on 2010-12-01 23:36
(Received via mailing list)
Attachment: signature.asc (835 Bytes)
On Thu, 2010-12-02 at 04:27 +0900, Yossef Mendelssohn wrote:
> >   end
> >
> >   def hash
> >     @name.hash
> >   end
> > end
> >
> > h = { X.new("foo") => "bar" }
> > h[X.new("foo")] = "baz" # will overwrite the above
>
> And so will `h['foo'] = 'baz'`.

sure, that is a nasty side effect, so probably not the nicest example :)
8f6f95c4bd64d5f10dfddfdcd03c19d6?d=identicon&s=25 Rick Denatale (rdenatale)
on 2010-12-02 01:15
(Received via mailing list)
On Wed, Dec 1, 2010 at 2:27 PM, Yossef Mendelssohn <ymendel@pobox.com>
wrote:
>>  end
>>
>>  def hash
>>   @name.hash
>>  end
>> end
>>
>> h = { X.new("foo") => "bar" }
>> h[X.new("foo")] = "baz" # will overwrite the above
>
> And so will `h['foo'] = 'baz'`.

No neither will:

class X
  attr_reader :name
  def initialize(name)
    @name = name
  end

  def hash
    @name.hash
  end

  def inspect
    "X:#{@name.inspect}"
  end
end

h = { X.new("foo") => :bar}
h[X.new("foo")] = :baz
h["foo"] = :bat

h # => {"foo"=>:bat, X:"foo"=>:baz, X:"foo"=>:bar}

The reason is that the value of #hash is not the only thing needed to
distinguish hash keys. All objects with the same hash value are mapped
to the same hash 'bucket' hash collisions are resolved by using the
eql? method,

X.new("a").eql?(X.new("a")) # => false

class X
  def eql?(other)
    other.class == X  && # One of the rare occurrences when checking
the class is a good thing
    name.eql?(other.name)
  end
end

h = { X.new("foo") => :bar}
h[X.new("foo")] = :baz
h["foo"] = :bat

h # => {"foo"=>:bat, X:"foo"=>:baz}

X.new("a").eql?(X.new("a")) # => true

Note that the Hash class depends on a relationship between eql? and
hash, that

a.eql?(b) => a.hash == b.hash

where => here is logical implication, that is

a => b is the same as

b ||| !a


--
Rick DeNatale

Blog: http://talklikeaduck.denhaven2.com/
Github: http://github.com/rubyredrick
Twitter: @RickDeNatale
WWR: http://www.workingwithrails.com/person/9021-rick-denatale
LinkedIn: http://www.linkedin.com/in/rickdenatale
B1b1d33e0655e841d4fd8467359c58d0?d=identicon&s=25 Yossef Mendelssohn (Guest)
on 2010-12-02 22:47
(Received via mailing list)
On Dec 1, 6:11pm, Rick DeNatale <rick.denat...@gmail.com> wrote:
> The reason is that the value of #hash is not the only thing needed to
> distinguish hash keys. All objects with the same hash value are mapped
> to the same hash 'bucket' hash collisions are resolved by using the
> eql? method,

Good explanation. My response was a knee-jerk reaction without
checking if it actually worked, and it definitely makes sense for the
language to care about more than simply the results of #hash.

Although I still think what I was trying to point out is something to
consider, that simply delegating #hash to an internal element isn't
all that good because on some level it makes them the same.
E0d864d9677f3c1482a20152b7cac0e2?d=identicon&s=25 Robert Klemme (Guest)
on 2010-12-02 23:36
(Received via mailing list)
On 12/02/2010 10:46 PM, Yossef Mendelssohn wrote:

> Although I still think what I was trying to point out is something to
> consider, that simply delegating #hash to an internal element isn't
> all that good because on some level it makes them the same.

Ultimately all hash values are derived from member hash values.  The key
point - and I believe this is what you want to stress - is _how_ values
are derived.  The methodology applied should strive to yield different
hash values for things that are considered non equivalent.  For example,
hash value of an Array or list implementation should somehow consider
position of elements in order to not return the same hash for two
collections which only differ in ordering.  We can see that Array#hash
obeys this:

irb(main):001:0> [1,2].hash
=> 11
irb(main):002:0> [2,1].hash
=> 1

On the other hand, since Set conceptually is agnostic of position
different ordering of elements should not create different hash codes:

irb(main):001:0> require 'set'
=> true
irb(main):002:0> s1 = [1,2].to_set
=> #<Set: {1, 2}>
irb(main):003:0> s2 = [2,1].to_set
=> #<Set: {2, 1}>
irb(main):004:0> s1.hash
=> 14
irb(main):005:0> s2.hash
=> 14
irb(main):006:0> s1 == s2
=> true

Kind regards

  robert
8f6f95c4bd64d5f10dfddfdcd03c19d6?d=identicon&s=25 Rick Denatale (rdenatale)
on 2010-12-03 18:30
(Received via mailing list)
On Thu, Dec 2, 2010 at 5:35 PM, Robert Klemme
<shortcutter@googlemail.com> wrote:
> value of an Array or list implementation should somehow consider position of
>
> irb(main):006:0> s1 == s2
> => true

Note that Set, like hash depends on that implication relationship
between #hash and #eql?

class X
 attr_reader :name
 def initialize(name)
   @name = name
 end

 def hash
   @name.hash
 end

 def inspect
   "X:#{@name.inspect}"
 end
end

require 'set'

[X.new("foo"), X.new("foo")].to_set # => #<Set: {X:"foo", X:"foo"}>

class X
 def eql?(other)
   other.class == X  &&
   name.eql?(other.name )
 end
end

[X.new("foo"), X.new("foo")].to_set # => #<Set: {X:"foo"}>



--
Rick DeNatale

Blog: http://talklikeaduck.denhaven2.com/
Github: http://github.com/rubyredrick
Twitter: @RickDeNatale
WWR: http://www.workingwithrails.com/person/9021-rick-denatale
LinkedIn: http://www.linkedin.com/in/rickdenatale
E0d864d9677f3c1482a20152b7cac0e2?d=identicon&s=25 Robert Klemme (Guest)
on 2010-12-03 18:51
(Received via mailing list)
On 12/03/2010 06:28 PM, Rick DeNatale wrote:
>> derived.  The methodology applied should strive to yield different hash
>> On the other hand, since Set conceptually is agnostic of position different
>> irb(main):005:0>  s2.hash
>> =>  14
>> irb(main):006:0>  s1 == s2
>> =>  true
>
> Note that Set, like hash depends on that implication relationship
> between #hash and #eql?

This is a different story: I was talking about how Set calculates its
hash code from members.  You are talking about how Set determines member
equivalence and especially what role the implementation of #hash of the
_members_ plays in this.

Kind regards

  robert
Please log in before posting. Registration is free and takes only a minute.
Existing account

NEW: Do you have a Google/GoogleMail, Yahoo or Facebook account? No registration required!
Log in with Google account | Log in with Yahoo account | Log in with Facebook account
No account? Register here.