dictionary - 带有自定义类型键的奇怪 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)
...

我有一个愚蠢的错误，还是 Julia 的 dict 中有错误？

Answer 1

默认情况下，自定义类型带有相等和散列的实现 按对象标识 .由于您的 id type 是可变的，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))

Julia 不知道你是关心对象的长期行为还是它的当前值。

有两种方法可以使这种行为如您所愿:

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

如果你确实需要改变这些值，你也可以定义你自己的 == 实现。和 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 just pointed out on the mailing list ，这不是可变值的默认值，“因为它可以轻松地将某些内容粘贴到字典中，然后对其进行变异，然后'丢失它'。”也就是说，对象的散列值已更改，但字典将其存储在基于其旧散列值的位置，现在您无法再通过键查找来访问该键/值对。即使您创建的第二个对象具有与第一个相同的原始属性，它也无法找到它，因为字典在找到哈希匹配后会检查相等性。查找该键的唯一方法是将其变异回其原始值或明确要求字典 Base.rehash!其内容。

在这种情况下，我强烈推荐选项 1。