在Ruby中,哈希可以使用数组作为键。

17
我有一个以数组为键的哈希表。当我改变这个数组时,哈希表不能再获取对应的键和值:
1.9.3p194 :016 > a = [1, 2]
 => [1, 2] 
1.9.3p194 :017 > b = { a => 1 }
 => {[1, 2]=>1} 
1.9.3p194 :018 > b[a]
 => 1 
1.9.3p194 :019 > a.delete_at(1)
 => 2 
1.9.3p194 :020 > a
 => [1] 
1.9.3p194 :021 > b
 => {[1]=>1} 
1.9.3p194 :022 > b[a]
 => nil 
1.9.3p194 :023 > b.keys.include? a
 => true 

我做错了什么?

更新: 好的,使用a.clone绝对是解决这个问题的一种方式。 如果我想改变"a"但仍然使用"a"来检索相应的值(因为"a"仍然是键之一)怎么办?


1
这里有另一个值得思考的代码片段:http://pastie.org/4609694 - Sergio Tulentsev
奇怪!看起来像是个bug? - tybro0103
5个回答

19

#rehash方法会重新计算哈希值,因此在更改键后执行以下操作:

b.rehash

这个方法正是我想要的。谢谢! - Eagle
虽然这可能解决了 OP 的问题,但更深层次的问题仍存在。 实际上根本不应该需要调用 #rehash 。 需要调用 #rehash 可能意味着还有其他问题存在。 这里有另一个回答 https://dev59.com/Bmct5IYBdhLWcg3wUb5-#36821695 ,讨论了一些更好的解决方案。 - Jason

9

TL;DR: 考虑使用Hash#compare_by_indentity方法。

你需要决定哈希表是否按照数组的值或者数组的引用来工作。

默认情况下,数组通过值的.hash.eql?进行比较,这就是为什么改变值会让ruby感到困惑。考虑以下代码:

pry(main)> a = [1, 2]
pry(main)> a1 = [1]
pry(main)> a.hash
=> 4266217476190334055
pry(main)> a1.hash
=> -2618378812721208248
pry(main)> h = {a => '12', a1 => '1'}
=> {[1, 2]=>"12", [1]=>"1"}
pry(main)> h[a]
=> "12"
pry(main)> a.delete_at(1)
pry(main)> a
=> [1]
pry(main)> a == a1
=> true
pry(main)> a.hash
=> -2618378812721208248
pry(main)> h[a]
=> "1"

看到这里发生了什么? 正如您发现的,它无法匹配a键,因为存储它的.hash值已过时[顺便说一句,您甚至不能依赖于它!突变可能导致相同的哈希(罕见)或不同的哈希落在同一个桶中(不太罕见)。]
但是,它没有返回nil而是匹配了a1键。 看到了吗,h[a]根本不关心aa1(叛徒!)的身份。它将您提供的当前——[1]a1——[1]进行比较并找到匹配项。
这就是为什么使用.rehash只是临时措施。它会重新计算所有键的.hash值并将它们移动到正确的桶中,但它容易出错,并可能引起麻烦:
pry(main)> h.rehash
=> {[1]=>"1"}
pry(main)> h
=> {[1]=>"1"}

哦哦。由于它们现在具有相同的值(并且很难预测哪个会获胜),因此这两个条目合并为一个。

解决方案

一个明智的方法是采用按值查找的方式,这需要该值永远不会更改。请 .freeze 您的键。或者在构建哈希表时使用 .clone/.dup,并随意更改原始数组 —— 但接受 h[a] 将根据从构建时保存的值查找当前的 a 值。

另一种方法是决定您关心标识 —— 按 a 查找应该找到 a,无论其当前值如何,并且许多键具有或现在具有相同的值都不重要。
怎么做呢?

  • Object hashes by identity. (Arrays don't because types that .== by value tend to also override .hash and .eql? to be by value.) So one option is: don't use arrays as keys, use some custom class (which may hold an array inside).

  • But what if you want it to behave directly like a hash of arrays? You could subclass Hash, or Array but it's a lot of work to make everything work consistently. Luckily, Ruby has a builtin way: h.compare_by_identity switches a hash to work by identity (with no way to undo, AFAICT). If you do this before you insert anything, you can even have distinct keys with equal values, with no confusion:

    [39] pry(main)> x = [1]
    => [1]
    [40] pry(main)> y = [1]
    => [1]
    [41] pry(main)> h = Hash.new.compare_by_identity
    => {}
    [42] pry(main)> h[x] = 'x'
    => "x"
    [44] pry(main)> h[y] = 'y'
    => "y"
    [45] pry(main)> h
    => {[1]=>"x", [1]=>"y"}
    [46] pry(main)> x.push(7)
    => [1, 7]
    [47] pry(main)> y.push(7)
    => [1, 7]
    [48] pry(main)> h
    => {[1, 7]=>"x", [1, 7]=>"y"}
    [49] pry(main)> h[x]
    => "x"
    [50] pry(main)> h[y]
    => "y"
    

    Beware that such hashes are counter-intuitive if you try to put there e.g. strings, because we're really used to strings hashing by value.


2
哈希表使用它们的键对象哈希码(a.hash)进行分组。哈希码通常取决于对象的状态;在这种情况下,当从数组中删除元素时,a 的哈希码会发生变化。由于键已经插入到哈希表中,a 会被归类到原始的哈希码下。
这意味着即使在打印哈希表时看起来正确,你也无法在 b 中检索出 a 的值。

1

你应该使用 a.clone 作为键

irb --> a = [1, 2]
==> [1, 2]

irb --> b = { a.clone => 1 }
==> {[1, 2]=>1}

irb --> b[a]
==> 1

irb --> a.delete_at(1)
==> 2

irb --> a
==> [1]

irb --> b
==> {[1, 2]=>1} # STILL UNCHANGED

irb --> b[a]
==> nil # Trivial, since a has changed

irb --> b.keys.include? a
==> false # Trivial, since a has changed

使用 a.clone 可以确保即使我们稍后更改 a,键也不会改变。


2
你如何解释原始代码片段?当keys包含a,但无法检索到值时怎么办? - Sergio Tulentsev
@SergioTulentsev 你是对的。从这个角度来看,当使用a而不是a.clone时,在删除键后b.keys[0].object_id == a.object_id返回true,这很奇怪。 - Kulbir Saini
@SergioTulentsev的原因是,从数组中删除元素后哈希码a.hash会发生变化,即使对象保持不变。因此,无法再找到该键。 - waldrumpus
1
@SergioTulentsev 在哈希表中查找键时,使用哈希码 - 在这种情况下没有运气,因为自插入键以来代码已更改。然而,哈希表的“keys”属性是一个数组,在数组搜索中使用“equal?”方法进行相等性测试。因此,在键数组中找到了该值。 - waldrumpus

1

正如您所说,问题在于哈希键是您稍后修改的完全相同的对象,这意味着键在程序执行期间会发生更改。

为了避免这种情况,请复制数组以用作哈希键:

a = [1, 2]
b = { a.clone => 1 }

现在您可以继续使用a,并保留您的哈希密钥。


1
我认为他想要能够修改数组,同时仍然能够使用这些修改的版本检索值。也许我错了。 - Sergio Tulentsev
是的,那就是我想要的。我是否可以改变变量 "a",但仍然将它用作键值? - Eagle

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接