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

Question

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

Answer 1

请记住，"hash table" 或字典完全可以避免冲突。事实上，它在任何合理的实现中都是预期和适应的。

理想情况下，您会努力使散列具有尽可能少的冲突，并且整个博士级别的讨论都在讨论什么是好的散列函数，但它们是不可避免的table。当确实发生冲突时，两个值在容器中共享相同的索引。

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

普通哈希 tables 可以被认为是一个数组的数组，尽管在一般用途中这对您来说是完全隐藏的。

如果您想探索它的行为方式，您可以在 Ruby 中实现您自己的散列 table：

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 方法，可以根据对象的内容生成一个很大的数值。

Answer 2

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

下面的文字是为了向其他人解释你的精彩观点两个不同的键计算相同哈希值的概率不为零，那么哈希class 仅仅依靠散列值来判断是否相等？

出于讨论的目的，我将 Ruby hashes 称为 maps，以免混淆2 在 Ruby 语言中使用术语 hash（1，对象的计算值，以及 2，map/dictionary 值对和唯一键).

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

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

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

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

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

Ruby internals and how to guarantee unique hash values

ruby

hash

hashmap

murmurhash