Ruby:为什么每次覆盖 `#hash` 时都需要覆盖 `#eql?`？

Question

在this presentation演讲者创建了一个值(value)类。

在实现它时，他重写了#eql?，并说在Java开发中，惯用语是每当你重写#eql?时，你必须重写#散列。

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? 同时被覆盖。

那么，为什么每次覆盖 eql? 时都需要覆盖 #hash？

Answer 1

Firstly, what is the #hash method? I can see it returns an integer.

#hash 方法应该返回接收者的哈希值。 (该方法的名称有点随意)。

Using pry I can see that an integer responds to #hash but I cannot see where it inherits the method from.

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

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

因此，#hash 继承自Kernel。但是请注意，Object 和 Kernel 之间存在一些特殊的关系，因为在 Kernel 中实现的一些方法记录在Object 反之亦然。这可能有历史原因，现在是 Ruby 社区生活中一个不幸的事实。

不幸的是，由于我不明白的原因，the documentation for Object#hash于 2017 年在 commit ironically titled "Add documents" 中删除.然而，它是 still available in Ruby 2.4 (大胆强调我的):

hash → integer

Generates an Integer hash value for this object. This function must have the property that a.eql?(b) implies a.hash == b.hash.

The hash value is used along with eql? by the Hash class to determine if two objects reference the same hash key. […]

因此，如您所见，#eql? 和 #hash 之间存在着深刻而重要的关系，事实上，使用 的方法的正确行为code>#eql? 和 #hash 取决于维持这种关系的事实。

因此，我们知道该方法称为 #hash，因此很可能会计算哈希值。我们知道它与 eql? 一起使用，我们知道它特别被 Hash 类使用。

它到底有什么作用？好吧，我们都知道哈希函数是什么:它是一种将更大的、可能无限的输入空间映射到更小的、有限的输出空间的函数。特别是，在这种情况下，输入空间是所有 Ruby 对象的空间，输出空间是“快速整数”(即过去称为 Fixnum 的整数)。

我们知道哈希表是如何工作的:值根据它们的键的哈希值放在桶中，如果我想找到一个值，那么我只需要计算键的哈希值(很快)和知道我在哪个桶中找到值(value)(在恒定时间内)，而不是例如一个键值对数组，我需要将键与数组中的每个键进行比较(线性搜索)以找到值。

但是，有一个问题:由于哈希的输出空间小于输入空间，所以有不同的对象具有相同的哈希值，因此最终在同一个桶中。因此，当两个对象具有不同的哈希值时，我知道它们是不同的事实，但如果它们具有相同的哈希值，那么它们仍然可能不同，我需要比较它们以确定是否相等——这就是哈希和相等性之间的关系从何而来。另请注意，当同一个存储桶中有许多键和向上键时，我将不得不再次将搜索键与存储桶中的每个键进行比较(线性搜索)以找到值。

从所有这些我们可以得出 #hash 方法的以下属性:

• 它必须返回一个Integer。
• 不仅如此，它还必须返回一个“快速整数”(相当于旧的Fixnum)。
• 它必须为两个被认为相等的对象返回相同的整数。
• 它可能为两个被认为不相等的对象返回相同的整数。
• 但是，这样做的可能性很小。 (否则，Hash 可能会退化为性能极低的链表。)
• 故意构造不相等但具有相同散列值的对象也应该困难。 (否则，攻击者可以强制Hash退化为链表，作为服务降级攻击的一种形式。)