ruby 如何保证散列中的对象不相同

xlpyo6sf  于 5个月前  发布在  Ruby
关注(0)|答案(2)|浏览(36)

Ruby文档中有一个关于如何使用Hash的例子,我在下面通过向Book类添加第三个属性进行了修改,下面还有第三个书评。
当类在原始代码中有两个属性时,book类中的hash方法在两个示例值之间使用^。我在不改变hash方法的情况下向类添加了第三个属性,并且在这个非常有限的数据集上,代码仍然有效,因为它没有向hash添加相同的对象。
所以我的问题是,当我在对象上有第三个属性时,我需要改变hash方法来保证相同的对象不会被添加到哈希中吗?如果是这样,怎么做?(注意,即使我读到了^,我也不知道它在这个哈希方法中是如何工作的)

class Book
    attr_reader :author, :title, :year
  
    def initialize(author, title, year)
      @author = author
      @title = title
      @year = year
    end
  
    def ==(other)
      self.class === other &&
        other.author == @author &&
        other.title == @title &&
        other.year == @year
    end
  
    alias eql? ==
  
    def hash
      @author.hash ^ @title.hash # XOR
    end
end
      
book1 = Book.new 'matz', 'Ruby in a Nutshell', 1987
book2 = Book.new 'matz', 'Ruby in a Nutshell', 1987
book3 = Book.new 'matz', 'Ruby in a Nutshell', 2015  # added by me
      
reviews = {
    book1 => 'Great reference!',
    book2 => 'Nice and compact!',
    book3 => 'Holy Moly, my additional review',
}
       
puts reviews.length #=> 2

字符串

dgtucam1

dgtucam11#

确切地说,你也应该把year添加到hash方法中,例如:

def hash
  @author.hash ^ @title.hash ^ @year.hash
end

字符串
使用Array#hash

def hash
  [@author, @title, @year].hash
end


请注意,如何计算类的哈希值并不重要,重要的是始终为相同的输入计算相同的哈希值,并且需要确保hash collisions的概率非常低。

zhte4eai

zhte4eai2#

我喜欢用杂货店的类比来解释散列图。
杂货店的组织方式让你找到你想要的东西,而不需要检查每个货架上的每一件物品。如果你想买牛奶,你知道去乳品区。如果你想买水果,你知道去农产品区。
群岛(类似于散列Map中的桶)将类似类别的事物分组在一起(这类似于它们的哈希值)。计算食物的哈希值很便宜(决定它属于哪个类别),然后让你立即排除大多数商店,并将搜索集中到一个小区域。在这个小区域内,你还是要一个一个的去找货架上的东西。
这个类比引出了一些非常直观的观察:

  • 如果你添加了新的字段,你必须将它们添加到#eql?的定义中。例如,如果你想区分黄油和人造黄油,那么这应该是#eql?方法的一部分。如果不是,那么你获取黄油的请求可能会返回人造黄油,或者相反。
  • 摘要:过于一般的等式函数会导致误报。
  • 但是,并不一定要在#hash方法的实现中添加这些新字段。例如,黄油和人造黄油都属于冷藏/乳制品岛,这很好。因为岛足够小,所以没有必要为黄油和人造黄油专门设置岛。

但大多数时候,你确实想把字段添加到Hash函数中,如果它们的查找成本很低的话(对于简单的示例变量来说,它们是很便宜的)。例如,有很多冷冻食品,所以一个“冷冻食品”的小岛不是很有用。它被进一步细分为“冷冻蔬菜”,“冷冻沙漠”,“冷冻即食餐”,“冷冻肉类”等。

  • 要点:过于通用的哈希值会预先取消较少的搜索空间,导致更多的一对一扫描,从而降低性能。
  • 然而,最重要的是,如果两个项目(例如,你正在寻找的假设黄油和货架上的真实的黄油)是相等的,它们应该具有相同的哈希值(在同一个岛上)。很明显,这是为什么。考虑一下商店是否在生产区有黄油。如果你要比较那里的黄油和你想象的黄油,它会是相等的。但这并不重要,因为你永远不会发现它能够比较它。
  • 要点:如果两个对象都是eql?,但有不同的哈希值,你可能会得到假否定(你的查找可能找不到对象,即使它存在,只是不在预期的位置)。

相关问题