Noob:Objects as key in hash

Thomas_G_Willis · 6 March 2005 17:30

Hi all,

I didn't want my first bit of participation on this list to be
something this silly. But I'm afraid I missed something vital in my 48
hour crash course.

If someone could take 10 seconds and tell me what I'm doing wrong I'd
greatly appreciate it and will give you props in my epitaph.

Feel free to point out and make fun of the style too I have thick skin.

I want to use an object as a key in a Hash.

here's some example code...

def main
puts "running this script..."
testpointid
end

def testpointid
  p = PointID.new(1,1)
  p2 = PointID.new(1,2)
  pdup = PointID.new(1,1)
  print "p!=pdup\n" if p!=pdup
  d = Hash.new()
  d[p]="point1"
  d[p2]="point2"

  #both of these return nil and I don't understand why
  print "PointID test failed" if d[p]!="point1"
  print "PointID test failed" if d[pdup]!="point1"

  #this works, but it's not quite the interface I want
  d[p.hash]="point1"
  d[p2.hash]="point2"

print "PointID test failed" if d[p.hash]!="point1"
print "PointID test failed" if d[pdup.hash]!="point1"

end

class PointID
attr_reader :x,:y

  def initialize(x,y)
    @x = x
    @y = y
    @x.freeze
    @y.freeze

end

  def hash
    return [@x.object_id,@y.object_id].to_s
  end

  def ==(other)
    return hash == other.hash
  end

  def to_s
    return hash()
  end

end

···

--
Thomas G. Willis
http://paperbackmusic.net

Anonymous_Coward · 6 March 2005 18:17

Hi all,

I didn't want my first bit of participation on this list to be
something this silly. But I'm afraid I missed something vital in my 48
hour crash course.

If someone could take 10 seconds and tell me what I'm doing wrong I'd
greatly appreciate it and will give you props in my epitaph.

Feel free to point out and make fun of the style too I have thick skin.

I want to use an object as a key in a Hash.

here's some example code...

def main
  puts "running this script..."
  testpointid
end

def testpointid
  p = PointID.new(1,1)
  p2 = PointID.new(1,2)
  pdup = PointID.new(1,1)
  print "p!=pdup\n" if p!=pdup
  d = Hash.new()
  d[p]="point1"
  d[p2]="point2"

  #both of these return nil and I don't understand why
  print "PointID test failed" if d[p]!="point1"
  print "PointID test failed" if d[pdup]!="point1"

  #this works, but it's not quite the interface I want
  d[p.hash]="point1"
  d[p2.hash]="point2"

  print "PointID test failed" if d[p.hash]!="point1"
  print "PointID test failed" if d[pdup.hash]!="point1"

end

class PointID
  attr_reader :x,:y

  def initialize(x,y)
    @x = x
    @y = y
    @x.freeze
    @y.freeze

  end

  def hash
    return [@x.object_id,@y.object_id].to_s
  end

  def ==(other)
    return hash == other.hash
  end

  def to_s
    return hash()
  end

end

Hash normally goes by object equality; i.e. whether the reference
points to the same object. Your #hash generates a string from the
two values, but the crux is that it's a String that it returns so
I think object-equality is used for comparisons. Try to have your
#hash return ...to_s.hash instead, and see what happens.

Generally speaking, using an object this way might not be the best
idea. If each Point were an immutable, unique instance (think Fixnum,
for example), I would think it's OK but I'm somewhat leery of this.
Maybe use the direct coordinates instead -or then make each Point
unique (and then you'd have a RefToPoint that would be used in making
shapes, for example).

What effect do you want?

Thomas G. Willis

E

···

On Sun, March 6, 2005 5:30 pm, Tom Willis said:

Jim_Weirich1 · 6 March 2005 18:18

Hi all,

Hi Tom!

I want to use an object as a key in a Hash.
class PointID

[...]

  def hash
    return [@x.object_id,@y.object_id].to_s
  end
  def ==(other)
    return hash == other.hash
  end

[...]

end

You are very close. In order to use an object as a hash key, it must support
the hash function and the eql? (not ==) function.

The hash function should return an integer to be used for hashing. Your
version returns a string. One correction might be ...

  def hash
    [@x.object_id, @y.object_id].to_s.hash
  end

That will now work. But you probably really don't want to bother converting
the above to a string. Why not just do:

  def hash
    @x.object_id + @y.object_id
  end

The other issue is that hash uses eql? for comparisons rather than ==. But
eql? and == compare values, but == might attempt a type conversion before
comparisons (e.g. 1 == 1.0 is true) while eql? will not (1.eql?(1.0) is
false). I would simply add:

  def eql?(other)
    self == other
  end

That should do it.

···

On Sunday 06 March 2005 12:30 pm, Tom Willis wrote:

--
-- Jim Weirich jim@weirichhouse.org http://onestepback.org
-----------------------------------------------------------------
"Beware of bugs in the above code; I have only proved it correct,
not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)

Joel_VanderWerf1 · 6 March 2005 20:06

Tom Willis wrote:
...

class PointID
  attr_reader :x,:y

  def initialize(x,y)
    @x = x
    @y = y
    @x.freeze
    @y.freeze

  end

  def hash
    return [@x.object_id,@y.object_id].to_s
  end

  def ==(other)
    return hash == other.hash
  end

  def to_s
    return hash()
  end

end

One approach to this problem that saves some typing (but isn't terribly
efficient because it generates garbage arrays):

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/1555

Jim_Weirich1 · 6 March 2005 18:26

Good points. I see the example uses .freeze on the x and y attributes. This
freezes the objects referenced by @x and @y (and since the objects are
Fixnum, this is a bit pointless. Fixnums are immutable anyways). What it
doesn't do is freeze the binding between @x/@y and those objects. I'm
guessing you really intended the following:

  def initialize(x,y)
    @x = x
    @y = y
    freeze # Freeze the PointID object
  end

···

On Sunday 06 March 2005 01:17 pm, ES wrote:

Generally speaking, using an object this way might not be the best
idea. If each Point were an immutable, unique instance (think Fixnum,
for example), I would think it's OK but I'm somewhat leery of this.

--
-- Jim Weirich jim@weirichhouse.org http://onestepback.org
-----------------------------------------------------------------
"Beware of bugs in the above code; I have only proved it correct,
not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)

James_Britt6 · 6 March 2005 18:47

Jim Weirich wrote:

...
The hash function should return an integer to be used for hashing. Your version returns a string. One correction might be ...

  def hash
    [@x.object_id, @y.object_id].to_s.hash
  end

That will now work. But you probably really don't want to bother converting the above to a string. Why not just do:

  def hash
    @x.object_id + @y.object_id
  end

Isn't this the same value as

@y.object_id + @x.object_id

giving, for example,

PointID.new( 1, 2).hash == PointID.new( 2, 1).hash

But they are different coordinates.

James

Anonymous_Coward · 6 March 2005 18:50

Generally speaking, using an object this way might not be the best
idea. If each Point were an immutable, unique instance (think Fixnum,
for example), I would think it's OK but I'm somewhat leery of this.

Good points. I see the example uses .freeze on the x and y attributes. This
freezes the objects referenced by @x and @y (and since the objects are
Fixnum, this is a bit pointless. Fixnums are immutable anyways). What it
doesn't do is freeze the binding between @x/@y and those objects. I'm
guessing you really intended the following:

  def initialize(x,y)
    @x = x
    @y = y
    freeze # Freeze the PointID object
  end

Yep, that would certainly work for a simple solution. For a more complex
realization of the idea, I'd consider some sort of a factory object, call
it PointSpace, for example. Whenever a user needs a reference to a point
that exists within the PointSpace, the factory finds out if there's already
a Point for the specified coordinates. If there is, a reference to that is
returned, otherwise a new Point is created. Points could of course be removed
from the list when there are no references remaining. Pretty standard factory
stuff but it'd guarantee a Point's uniqueness -and for syntactical simplicity,
Point could certainly internalize/implement PointSpace.

-- Jim Weirich

E

···

On Sun, March 6, 2005 6:26 pm, Jim Weirich said:

On Sunday 06 March 2005 01:17 pm, ES wrote:

Thomas_G_Willis · 6 March 2005 18:55

> Generally speaking, using an object this way might not be the best
> idea. If each Point were an immutable, unique instance (think Fixnum,
> for example), I would think it's OK but I'm somewhat leery of this.

...

Thanks for the replies.

The problem I'm trying to solve. Which really isn't a problem, because
I'm just experimenting is a board game emulation.

I had an idea that a framework could be slapped together for various
board games. Tic Tac Toe, Checkers, Chess etc...

So to represent the board or get access to the board state, my first
stab at it was an immutable collection of coordinates that you can
associae arbitrary data with keyed by x,y.

I imagine I'd have a board object. And I would access it like this.

tictactoe = GameBoard.new(length=3,width=3)
tictactoe.place(2,2,"x")
tictactoe.place(3,3,"o")
tictactoe.place(2,3,"x")
tictactoe.place(3,1,"o")
tictactoe.place(2,1,"x")

"x's win"

class GamBoard
...
def place(x,y,data)

@pointcollection[PointID.new(x,y)].data = data if <some conditions>

end

#previous implementation which I didn't like
#because it would be something I'd do in python
def place(x,y,data)
@pointcollection["#{x}:#{y}"].data = data
end
...
end

haven't figured out the how to determine a winner yet, which is why I
didn't start with chess.

Probably not the best design. But my main goal is learning a new
language, and it's more fun than reading a bunch of documentation.

Probably more than you wanted to know, but this is how I arrived at
this little problem /misunderstanding.

Thanks again.

···

On Mon, 7 Mar 2005 03:26:55 +0900, Jim Weirich <jim@weirichhouse.org> wrote:

On Sunday 06 March 2005 01:17 pm, ES wrote:

--
Thomas G. Willis
http://paperbackmusic.net

Joel_VanderWerf1 · 6 March 2005 20:05

James Britt wrote:

Jim Weirich wrote:

...
The hash function should return an integer to be used for hashing. Your version returns a string. One correction might be ...

  def hash
    [@x.object_id, @y.object_id].to_s.hash
  end

That will now work. But you probably really don't want to bother converting the above to a string. Why not just do:

  def hash
    @x.object_id + @y.object_id
  end

Isn't this the same value as

  @y.object_id + @x.object_id

giving, for example,

PointID.new( 1, 2).hash == PointID.new( 2, 1).hash

But they are different coordinates.

That's ok, as long as #eql? says they are different. In fact, many
objects must give the same value in response to #hash, since there are
far more possible objects than Fixnums. The #hash method is only used to
find the hash bin, and then #eql? is used to test equality within the bin.

Jim_Weirich1 · 6 March 2005 20:48

Yes. As Joel points out that to some degree you expect things to occasionally
hash the the same value. If too many things hash to the same value, then
your hash array will slow down.

For small boards, it probably doesn't matter, but not only do [1,2] and [2,1]
map to the same hash, but so would [0,3] and [3,0]. In fact, all diagnols
running from the lower left to the upper right have the same hash value on
all their cells.

So x+y suggestion, while working, is rather suboptimal. How about this ...

  def hash
    @x + 1000*@y
  end

(I dropped the object_id call because it looks like we are mapping from
fixnums).

···

On Sunday 06 March 2005 01:47 pm, James Britt wrote:

Jim Weirich wrote:
> def hash
> @x.object_id + @y.object_id
> end

Isn't this the same value as

@y.object_id + @x.object_id

--
-- Jim Weirich jim@weirichhouse.org http://onestepback.org
-----------------------------------------------------------------
"Beware of bugs in the above code; I have only proved it correct,
not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)

Thomas_G_Willis · 6 March 2005 22:00

LOL I should learn to read. or get a bigger monitor or glasses.

I've been pulling my hair out for the last few hours trying to get it
to work with Jim's suggestions of using eq? only to compose a lengthy
self-deprecating rantish reply.

Only to discover, Jim said the eql? operator.

So, I'm to new to know the difference just yet.

But I got it working.

Here's the code in all it's glory for future noobs sake.

#---ruby proggie
class PointID
attr_reader :x,:y

  def initialize(x,y)
    @x = x
    @y = y
    freeze
  end

  def hash
   return [@x.object_id ,@y.object_id].hash
  end

  def ==(other)
    result = self.hash == other.hash
    #result = (self.x == other.x)and (self.y == other.y)
    return result
  end

  def eql?(other)
    return self == other
  end

  def to_s
    return "#{@x},#{@y}"
  end

end
#---end proggie

Thanks again for all the feedback. Hopefully someday I can return the favor.

···

On Mon, 7 Mar 2005 05:48:47 +0900, Jim Weirich <jim@weirichhouse.org> wrote:

On Sunday 06 March 2005 01:47 pm, James Britt wrote:
> Jim Weirich wrote:
> > def hash
> > @x.object_id + @y.object_id
> > end
>
> Isn't this the same value as
>
> @y.object_id + @x.object_id

Yes. As Joel points out that to some degree you expect things to occasionally
hash the the same value. If too many things hash to the same value, then
your hash array will slow down.

For small boards, it probably doesn't matter, but not only do [1,2] and [2,1]
map to the same hash, but so would [0,3] and [3,0]. In fact, all diagnols
running from the lower left to the upper right have the same hash value on
all their cells.

So x+y suggestion, while working, is rather suboptimal. How about this ...

  def hash
    @x + 1000*@y
  end

(I dropped the object_id call because it looks like we are mapping from
fixnums).

--
-- Jim Weirich jim@weirichhouse.org http://onestepback.org
-----------------------------------------------------------------
"Beware of bugs in the above code; I have only proved it correct,
not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)

--
Thomas G. Willis
http://paperbackmusic.net

Douglas_Livingstone · 8 March 2005 11:51

Good job

I think you can get rid of the returns too:

#---ruby proggie
class PointID
attr_reader :x,:y

def initialize(x,y)
@x, @y = x, y
freeze
end

def hash
[@x.object_id, @y.object_id].hash
end

def ==(other)
self.hash == other.hash
end

def eql?(other)
self == other
end

def to_s
"#{@x},#{@y}"
end

end
#---end proggie

Douglas

···

On Mon, 7 Mar 2005 07:00:32 +0900, Tom Willis <tom.willis@gmail.com> wrote:

Thanks again for all the feedback. Hopefully someday I can return the favor.
--
Thomas G. Willis
http://paperbackmusic.net

Thomas_G_Willis · 8 March 2005 12:29

Whoa that's crazy, I'm not sure if I'm ready to give up returns yet.
It took me 2 years to feel ok about not declaring variable types or
even worrying about it. Someday it will probably happen.

···

On Tue, 8 Mar 2005 20:51:55 +0900, Douglas Livingstone <rampant@gmail.com> wrote:

Good job

I think you can get rid of the returns too:

#---ruby proggie
class PointID
attr_reader :x,:y

def initialize(x,y)
   @x, @y = x, y
   freeze
end

def hash
  [@x.object_id, @y.object_id].hash
end

def ==(other)
   self.hash == other.hash
end

def eql?(other)
   self == other
end

def to_s
   "#{@x},#{@y}"
end

end
#---end proggie

Douglas

On Mon, 7 Mar 2005 07:00:32 +0900, Tom Willis <tom.willis@gmail.com> wrote:
>
> Thanks again for all the feedback. Hopefully someday I can return the favor.
> --
> Thomas G. Willis
> http://paperbackmusic.net
>
>

--
Thomas G. Willis
http://paperbackmusic.net

Lee_Braiden · 8 March 2005 12:35

lol.. agreed, it seems strange to me too. Doesn't read well, and feels like
black magic. Almost like an unwanted and unexplained side-effect, which I've
seen many more warnings about than celebrations of

···

On Tuesday 08 March 2005 12:29, Tom Willis wrote:

Whoa that's crazy, I'm not sure if I'm ready to give up returns yet.
It took me 2 years to feel ok about not declaring variable types or
even worrying about it. Someday it will probably happen.

--
Lee.

Topic		Replies	Views
Hash with two identical keys? ruby-talk	14	145	26 December 2006
Ruby Hash Keys and Related Questions ruby-talk	6	166	5 March 2011
How to use tuple as hash key ruby-talk	12	106	18 September 2007
Get the real object in a Hash key ruby-talk	13	183	16 April 2011
What’s the standard way of implementing #hash for value objects in Ruby? ruby-talk	22	259	2 January 2012

Noob:Objects as key in hash

Related topics