Ruby: Почему `# hash` нужно переопределять всякий раз, когда` #eql? `Переопределяется?

Question

В этой презентации говорящий создал класс значений.

При его реализации он переопределяет #eql? и говорит, что в Java-разработке идиома заключается в том, что всякий раз, когда вы переопределяете #eql? вы должны переопределить #hash.

class Weight
  # ...

  def hash
    pounds.hash
  end

  def eql?(other)
    self.class == other.class &&
      self.pounds == other.pounds
  end
  alias :== eql?
end

Во-первых, что такое метод #hash?Я вижу, что он возвращает целое число.

> 1.hash
=> -3708808305943022538

> 2.hash
=> 1196896681607723080

> 1.hash
=> -3708808305943022538

Используя pry, я вижу, что целое число отвечает на #hash, но я не вижу, откуда оно наследует метод.Это не определено в Numeric или Object.Если бы я знал, что делает этот метод, я бы, наверное, понял, почему его необходимо переопределить одновременно с #eql?.

Итак, почему #hash нужно переопределять всякий раз, когда eql? переопределяется

Answer 1

Во-первых, что такое метод #hash?Я вижу, что он возвращает целое число.

Метод #hash должен возвращать хэш получателя.(Название метода - нечто вроде дешевой распродажи.)

Используя pry, я вижу, что целое число отвечает на #hash, но я не вижу, откуда оно наследует метод.

Есть десятки вопросов типа «Откуда этот метод» на [так], и ответ всегда один и тот же: лучший способ узнать, откуда берется метод, это просто спроситьэто:

hash_method = 1.method(:hash)
hash_method.owner #=> Kernel

Итак, #hash наследуется от Kernel.Тем не менее, обратите внимание, что между Object и Kernel существует некоторая специфическая взаимосвязь в том, что некоторые методы, которые реализованы в Kernel, документированы в Object или наоборот.Это, вероятно, имеет исторические причины, и теперь это печальный факт жизни в сообществе Ruby.

К сожалению, по причинам, которые я не понимаю, документация для Object#hash была удалена в2017 в коммит с иронией под названием «Добавить документы» .Тем не менее, по-прежнему доступен в Ruby 2.4 ( жирный выделение):

hash → integer

Создает целочисленное хеш-значение для этого объекта.Эта функция должна иметь свойство, которое a.eql?(b) подразумевает a.hash == b.hash.

Хеш-значение используется вместе с eql? классом Hash, чтобы определить, являются ли дваобъекты ссылаются на один и тот же хэш-ключ.[…]

Итак, как вы можете видеть, между #eql? и #hash существует глубокая и важная связь, и фактически правильное поведение методов, использующих #eql? и #hash зависит от того факта, что эта связь поддерживается.

Итак, мы знаем, что метод называется #hash и, таким образом, вероятно, вычисляет хэш.Мы знаем, что он используется вместе с eql?, и мы знаем, что он используется, в частности, Hash классом.

Что именно он делает?Что ж, мы все знаем, что такое хеш-функция: это функция, которая отображает большее, потенциально бесконечное входное пространство в меньшее конечное выходное пространство.В частности, в этом случае пространство ввода - это пространство всех объектов Ruby, а пространство вывода - это «быстрые целые числа» (т. Е. Те, которые раньше назывались Fixnum).

И мызнать, как работает хеш-таблица: значения помещаются в сегменты на основе хеш-функции их ключей, если я хочу найти значение, мне нужно только вычислить хеш-код ключа (это быстро) и узнать, какой сегмент я нахожузначение в (в постоянном времени), в отличие, например, от массива пар ключ-значение, где мне нужно сравнить ключ с каждым ключом в массиве (линейный поиск), чтобы найти значение.

Однако существует проблема: поскольку выходное пространство хеша меньше, чем входное пространство, существуют разные объекты, которые имеют одинаковое значение хэш-функции и, следовательно, оказываются в одном и том же сегменте.Таким образом, когда два объекта имеют разные значения хеш-функции, я точно знаю, что они разные, но если они имеют одинаковое значение хеш-функции, они все равно могут быть разными, и мне нужно сравнить их на равенство, чтобы быть уверенным - и этооткуда взялись отношения между хешем и равенством.Также обратите внимание, что, когда в одном сегменте много ключей и выше, мне снова придется сравнивать ключ поиска с каждым ключом в сегменте (линейный поиск), чтобы найти значение.

Из всего этого можно сделать выводследующие свойства метода #hash:

• Он должен возвращать Integer.
• Мало того, он должен возвращать "быстрое целое число" (эквивалентное старому *).1079 * s).
• Он должен возвращать одно и то же целое число для двух объектов, которые считаются равными.
• Он может возвращать одинаковое целое число для двух объектов, которые считаются неравными.
• Однако , он должен делать это только с низкой вероятностью.(В противном случае Hash может выродиться в связанный список с сильно ухудшенной производительностью.)
• IТакже должно быть трудно для создания объектов, которые неравны, но имеют намеренно одинаковое значение хеш-функции.(В противном случае злоумышленник может заставить a Hash выродиться в связанный список как форма атаки с ухудшением качества обслуживания.)

Answer 2

Метод #hash возвращает числовое значение хеша для принимающего объекта:

:symbol.hash # => 2507

Хэши Ruby являются реализацией структуры данных карты хеша, и они используют значениевозвращается #hash, чтобы определить, ссылаются ли на тот же ключ.Хэши используют метод #eql? в сочетании со значениями #hash для определения равенства.

Учитывая, что эти два метода работают вместе, чтобы предоставить хэшам информацию о равенстве, если вы переопределите #eql?, вам необходимо такжепереопределить #hash, чтобы сохранить поведение вашего объекта согласованным с другими объектами Ruby.

Если вы НЕ переопределите его, это происходит:

class Weight
  attr_accessor :pounds

  def eql?(other)
    self.class == other.class && self.pounds == other.pounds
  end

  alias :== eql?
end

w1 = Weight.new
w2 = Weight.new

w1.pounds = 10
w2.pounds = 10

w1 == w2 # => true, these two objects should now be considered equal

weights_map = Hash.new
weights_map[w1] = '10 pounds'
weights_map[w2] = '10 pounds'

weights_map # => {#<Weight:0x007f942d0462f8 @pounds=10>=>"10 pounds", #<Weight:0x007f942d03c3c0 @pounds=10>=>"10 pounds"}

Если w1и w2 считаются равными, в хэше должна быть только одна пара значений ключа.Однако класс Hash вызывает #hash, который мы НЕ переопределяем.Чтобы исправить это и действительно сделать w1 и w2 равными, мы переопределяем #hash на:

class Weight
  def hash
    pounds.hash
  end
end

weights_map = Hash.new
weights_map[w1] = '10 pounds'
weights_map[w2] = '10 pounds'

weights_map # => {#<Weight:0x007f942d0462f8 @pounds=10>=>"10 pounds"}

Теперь хэш знает, что эти объекты равны, и поэтому хранит только одну пару ключ-значение