Ruby 内部以及如何保证唯一的哈希值

Question

Ruby中的哈希（Hash）仅使用其哈希值（对于字符串和数字）。在内部，它使用Murmur哈希函数。我想知道鉴于两个不同键具有相同哈希值的概率不为零，如何实现哈希。

- Marco

Answer 1

你能和我们分享一下你是如何得出Ruby仅使用哈希值来确定相等性的结论的吗？

下面的文字是为了向他人解释你的优秀观点，即“计算两个不同键的相同哈希值的概率不为零”，那么Hash类如何单凭哈希值来确定相等性呢？

在本文讨论中，我将把Ruby中的哈希表称为“映射”，以避免混淆Ruby语言中“哈希”的两个用法（1.对象上的计算值，2.值对和唯一键的地图/字典）。

据我所知，映射、集合等中的哈希值被用作快速确定“可能相等性”的第一步。也就是说，如果两个对象的哈希值相等，则它们“可能”相等；但也有可能它们不相等，仅仅是巧合产生了相同的哈希值。

换句话说，从比较对象的哈希值中唯一确定的关于相等性的信息是：如果hash1！= hash2，则这两个对象肯定不相等。

如果两个哈希值相等，则必须通过它们的内容进行比较（在Ruby中，似乎是通过调用“==”方法）。

因此，比较哈希值不是比较对象本身的“替代品”，而是一种用于优化性能的快速初步处理。

- Keith Bennett

Answer 2

记住，“哈希表”或字典可以有冲突，这在任何合理的实现中都是预期和允许的。

理想情况下，您应该尽可能地减少哈希冲突，关于什么构成良好的哈希函数，有整个博士级别的讨论，但是它们是不可避免的。当发生碰撞时，两个值将共享容器中的相同索引。

无论如何，对于基于哈希的任何“潜在”匹配，都必须进行评估。执行直接比较以确保您正在访问的值是所请求的值，而不是巧合映射到相同位置的值。

普通哈希表可以被视为数组的数组，即使在一般用途中，这一切都完全隐藏了。

如果您想探索其行为，可以在Ruby中实现自己的哈希表：

class ExampleHash
  include Enumerable

  def initialize
    @size = 9
    @slots = Array.new(@size) { [ ] }
  end

  def [](key)
    @slots[key.hash % @size].each do |entry|
      if (entry[0] == key)
        return entry[1]
      end
    end

    nil
  end

  def []=(key, value)
    entries = @slots[key.hash % @size]

    entries.each do |entry|
      if (entry[0] == key)
        entry[1] = value

        return
      end
    end

    entries << [ key, value ]
  end
end

这很容易实现，因为Ruby中的每个对象都有一个内置的hash方法，它可以生成一个基于对象内容的大数值。

- tadman