4

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

4

2 回答 2

3

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

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

出于讨论的目的，我将 Ruby哈希称为映射，以免混淆 Ruby 语言中术语哈希的两种用法（1，对象上的计算值，2，映射/字典对值和唯一键）。

据我了解，映射、集合等中的哈希值被用作确定可能相等性的快速第一步。也就是说，如果2个对象的哈希值相等，那么这2个对象就有可能相等；但也有可能两个对象不相等，但巧合地产生相同的哈希值。

换句话说，您可以从被比较对象的哈希值中判断是否相等的唯一确定的事情是，如果 hash1 != hash2 那么对象肯定不相等。

如果 2 个哈希值相等，则必须通过它们的内容来比较 2 个对象（==我相信在 Ruby 中，通过调用该方法）。

因此，比较哈希不能代替比较对象本身，它只是用于优化性能的快速第一步。

于 2016-04-30T08:09:12.443 回答
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方法，该方法会根据对象的内容生成一个较大的数值。

于 2016-04-30T07:40:12.830 回答