Ruby：为什么在覆盖`#eql?` 时需要覆盖`#hash`？

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数字哈希值：

: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，我们没有覆盖它。为了解决这个问题并真正实现 makew1和w2equals，我们重写#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"}

现在哈希知道这些对象是相等的，因此只存储一个键值对

Answer 2

首先，#hash方法是什么？我可以看到它返回一个整数。

该#hash方法应该返回接收者的哈希值。（该方法的名称有点泄露）。

使用 pry 我可以看到一个整数响应，#hash但我看不到它从哪里继承该方法。

[so] 上有几十个“这个方法从哪里来”类型的问题，答案总是一样的：知道一个方法从哪里来的最好方法，就是简单地问它：

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.
• 不仅如此，它还必须返回一个“快速整数”（相当于旧的Fixnums）。
• 对于被认为相等的两个对象，它必须返回相同的整数。
• 对于被认为不相等的两个对象，它可能会返回相同的整数。
• 然而，它只应该以低概率这样做。（否则， aHash可能退化为性能严重下降的链表。）
• 故意构造不相等但具有相同哈希值的对象也应该很困难。（否则，攻击者可以强制aHash退化为链表，作为服务降级攻击的一种形式。）