How to define hash function for a class including comparable?

Question

Imagine a class including comparable like this:

class Element
  include Comparable
  attr_accessor :name, :pos_x, :pos_y

  def initialize(name, pos_x, pos_y)
    @name = name
    @pos_x = pos_x
    @pos_y = pos_y
  end

  def <=>(other)
    if (@pos_x == other.pos_x) and (@pos_y == other.pos_y)
      return 0
    else 
      return @name <=> other.name
    end
  end

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

How would you implement the hash function such that a.hash == b.hash in this case? In general I'd do:

def hash
  @name.hash
end

But this does not include pos_x and pos_y.

Answer 1

Unfortunately this is mathematically impossible to define a valid hash function in this case.

Let a, b be two elements with equal positions, and different names. According to eql? definition, this implies that h(a) == h(b). Since this is true for any names values, the hash function is to be independent on name attribute, which is however in contradiction with the second check. Hence there is no hash function for this eql? definition. Sorry. :(

Update:

As noted by toro2k - your equality definition is not transitive. In general if a == b and b == c, it is required that a == c. According to your eql? function:

{pos_x: 1, pos_y: 1, name: 'a'} == {pos_x: 1, pos_y: 1, name: 'b'}
{pos_x: 1, pos_y: 1, name: 'b'} == {pos_x: 2, pos_y: 2, name: 'b'}

but

{pos_x: 1, pos_y: 1, name: 'a'} != {pos_x: 2, pos_y: 2, name: 'b'}

That's the root of your problem here.

Answer 2

There is nothing you can do beyond what you are already doing. Note that your hash function is a really bad one because it has poor distribution and will lead to a lot of collisions, which will probably destroy the O(1) amortized worst-case step complexity guarantees of Hash, but there really is nothing you can do about that.

Note, however, that there is a much bigger problem with your definitions of equality and ordering: they aren't equality or ordering!

Equality and ordering relationships need to be

• reflexive: a ~ a
• symmetric: a ~ b <=> b ~ a
• transitive: a ~ b && b ~ c => a ~ c

Both your equality and ordering relations violate transitivity:

one   = Element.new('Z', 1, 1)
two   = Element.new('A', 1, 1)
three = Element.new('A', 2, 2)

one == two   # => true
two == three # => true
one == three # => false # Huh?

one <= two   # => true
two <= three # => true
one <= three # => false # Huh?

All methods that use the spaceship operator (e.g. Enumerable#sort) rely on those laws. So, your <=> and eql? implementations are fundamentally broken.

Answer 3

You can override == instead, since Object#hash does not accept an argument:

def ==(o)
  (@pos_x == o.pos_x && pos_y == o.pos_y) || (@name == o.name)
end

alias_method :eql?, :==