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

Question

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

Answer 1

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

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

为了讨论的目的，我将把Rubyhashes称为maps，以免混淆术语散列在Ruby语言中的两种用法（1，对象上的计算值，2，值对和唯一键的映射/字典）。

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

换句话说，从被比较对象的哈希值中可以确定的关于等式的唯一一点是，如果hash1！=hash2，则对象肯定不相等。

如果的两个散列值相等，那么这两个对象必须根据它们的内容进行比较（在Ruby中，我相信通过调用==方法）。

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

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