Égalité et hachage

Fait partie de la section Programmation orientée objet du Journey Ruby de Coddy. Leçon 37 sur 57.

Ruby possède plusieurs types d’égalité. == est l’égalité de valeurs, que vous définissez pour votre classe. Les tables de hachage et uniq utilisent à la place deux autres méthodes : eql? et hash. Avec seulement == défini, des points égaux restent des clés de hachage différentes :

class Point
  attr_reader :x, :y

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

  def ==(other)
    other.is_a?(Point) && x == other.x && y == other.y
  end
end

a = Point.new(1, 2)
b = Point.new(1, 2)
puts a == b
puts [a, b].uniq.size
puts({ a => "first" }[b].inspect)

Résultat :

true
2
nil

Un Hash compare d’abord les valeurs de hash, des nombres calculés à partir d’un objet, puis vérifie les candidats avec eql?. Définis les deux à partir des mêmes champs que ==. alias eql? == réutilise ==, et [x, y].hash combine les champs :

class Point
  attr_reader :x, :y

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

  def ==(other)
    other.is_a?(Point) && x == other.x && y == other.y
  end
  alias eql? ==

  def hash
    [x, y].hash
  end
end

a = Point.new(1, 2)
b = Point.new(1, 2)
puts [a, b, Point.new(3, 4)].uniq.size
puts({ a => "first" }[b])

Sortie :

2
first

La règle est la suivante : les objets qui sont eql? doivent avoir le même hash. Deux objets différents peuvent partager une valeur de hachage par hasard, c’est pourquoi eql? effectue tout de même une vérification. Ainsi, le comptage avec un Hash porte sur les valeurs plutôt que sur les identités :

class Word
  attr_reader :text

  def initialize(text)
    @text = text.downcase
  end

  def ==(other)
    other.is_a?(Word) && text == other.text
  end
  alias eql? ==

  def hash
    text.hash
  end
end

counts = Hash.new(0)
%w[Ruby ruby RUBY gem].each { |t| counts[Word.new(t)] += 1 }
counts.each { |word, n| puts "#{word.text}: #{n}" }

Sortie :

ruby: 3
gem: 1

equal? reste l’identité et ne doit jamais être redéfini. Les valeurs intégrées suivent déjà ces règles, c’est pourquoi les chaînes et les tableaux peuvent servir de clés de hachage :

a == b          # même valeur (vous la définissez)
a.eql?(b)       # même valeur pour les clés de Hash et uniq (alias de ==)
a.hash          # un nombre ; les objets égaux donnent des nombres égaux
a.equal?(b)     # le même objet (ne jamais redéfinir)

Défi

Facile

Complétez la classe Point afin que les points ayant les mêmes coordonnées soient égaux avec ==, eql? et hash, et qu’ils puissent être utilisés comme clés d’un Hash. to_s renvoie (1, 2).

Le code fourni lit les points sous forme de lignes x,y. Il affiche le nombre de points distincts avec uniq, compte ensuite les visites pour chaque point dans un Hash et les affiche dans l’ordre de leur première visite sous la forme (1, 2): 2, puis indique enfin si un nouveau Point.new(0, 0) est une clé.

Votre code doit se trouver dans point.rb. main.rb contient le code fourni pour l’entrée et la sortie et ne peut pas être modifié.

Essayez vous-même

require_relative 'point'

# Code d'entrée/sortie fourni : le garder tel quel
input = []
while (line = gets)
  input << line.chomp
end
points = input.map { |line| Point.new(*line.split(",").map(&:to_i)) }
puts "distinct: #{points.uniq.size}"
visits = Hash.new(0)
points.each { |pt| visits[pt] += 1 }
visits.each { |pt, n| puts "#{pt}: #{n}" }
puts "origin visited: #{visits.key?(Point.new(0, 0))}"