Ruby Language Fonction de hachage prioritaire


Exemple

Les hashes Ruby utilisent les méthodes hash et eql? pour effectuer l'opération de hachage et attribuer des objets stockés dans le hachage à des bacs de hachage internes. L'implémentation par défaut du hash dans Ruby est la fonction de hachage de murmure sur tous les champs membres de l'objet haché . Pour contourner ce comportement, il est possible de remplacer le hash et eql? méthodes.

Comme avec les autres implémentations de hachage, deux objets a et b seront hachés dans le même a.hash == b.hash si a.hash == b.hash et seront réputés identiques si a.eql?(b) . Ainsi, lors de la réimplémentation du hash et de l’ eql? il faut veiller à ce que si a et b sont égaux sous eql? ils doivent retourner la même valeur de hash . Sinon, cela pourrait entraîner des doublons dans un hachage. À l'inverse, un mauvais choix dans l'implémentation du hash peut conduire de nombreux objets à partager le même compartiment de hachage, détruisant ainsi le temps de recherche O (1) et provoquant l'appel de eql? O (n) eql? sur tous les objets.

Dans l'exemple ci-dessous, seule l'instance de la classe A est stockée en tant que clé, car elle a été ajoutée en premier:

class A
  def initialize(hash_value)
    @hash_value = hash_value
  end
  def hash
    @hash_value # Return the value given externally
  end
  def eql?(b)
    self.hash == b.hash
  end
end

class B < A
end

a = A.new(1)
b = B.new(1)

h = {}
h[a] = 1
h[b] = 2

raise "error" unless h.size == 1
raise "error" unless h.include? b
raise "error" unless h.include? a