使用自定义类型的键的奇怪Dict行为

Question

我有一个递归函数,它利用全局字典来存储遍历树时已经获得的值.但是,至少存储在dict中的一些值似乎消失了!此简化代码显示了问题:

type id
    level::Int32
    x::Int32
end

Vdict = Dict{id,Float64}()

function getV(w::id)
    if haskey(Vdict,w)
        return Vdict[w]
    end 
    if w.level == 12
        return 1.0
    end
    w.x == -111 && println("dont have: ",w)

    local vv = 0.0
    for j = -15:15
        local wj = id(w.level+1,w.x+j)
        vv += getV(wj)
    end
    Vdict[w] = vv
    w.x == -111 && println("just stored: ",w)
    vv
end

getV(id(0,0))

输出有很多行,如下所示:

just stored: id(11,-111)
dont have: id(11,-111)
just stored: id(11,-111)
dont have: id(11,-111)
just stored: id(11,-111)
dont have: id(11,-111)
...

我有一个愚蠢的错误,或者朱莉娅的词典中是否有错误？

Answer 1

默认情况下,自定义类型带有按对象标识进行相等和散列的实现.由于你的id类型是可变的,Julia是保守的,并且假设你关心区分每个实例(因为它们可能分歧):

julia> type Id # There's a strong convention to capitalize type names in Julia
           level::Int32
           x::Int32
       end

julia> x = Id(11, -111)
       y = Id(11, -111)
       x == y
false

julia> x.level = 12; (x,y)
(Id(12,-111),Id(11,-111))

朱莉娅不知道你是否关心物体的长期行为或其当前价值.

有两种方法可以让您按照自己的意愿行事:

1. 使您的自定义类型不可变.看起来你不需要改变内容Id.解决此问题的最简单,最直接的方法是将其定义为immutable Id.现在Id(11, -111)与任何其他结构完全无法区分,Id(11, -111)因为它的价值永远不会改变.作为奖励,您可能也会看到更好的表现.

2. 如果你确实需要变异值,你可以或者定义自己的实现==,并Base.hash让他们只关心当前值:

   ==(a::Id, b::Id) = a.level == b.level && a.x == b.x
   Base.hash(a::Id, h::Uint) = hash(a.level, hash(a.x, h))
   

   正如@StefanKarpinski 刚刚在邮件列表中指出的那样,这不是可变值的默认值"因为它可以很容易地在dict中粘贴某些东西,然后改变它,然后'丢失它'." 也就是说,对象的哈希值已更改,但字典根据其旧哈希值将其存储在某个位置,现在您无法再通过键查找访问该键/值对.即使您创建第二个具有与第一个相同的原始属性的对象,它也无法找到它,因为字典在找到哈希匹配后检查相等性.查找该密钥的唯一方法是将其变回原始值或明确询问字典Base.rehash!的内容.

在这种情况下,我强烈建议选项1.