自定义类型键的奇怪字典行为

Question

我有一个递归函数，它利用全局字典来存储在遍历树时已经获取的值。然而，至少一些存储在字典中的值似乎会消失！以下简化的代码展示了这个问题：

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的字典出现了bug？

- Steven White

---

还可以查看相关的Julia包：Memoize.jl - HarmonicaMuse

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))

Julia不确定您关心对象的长期行为还是其当前值。

有两种方法可以使其按照您的意愿进行操作：

1. Make your custom type immutable. It looks like you don't need to mutate the contents of Id. The simplest and most straightforward way to solve this is to define it as immutable Id. Now Id(11, -111) is completely indistinguishable from any other construction of Id(11, -111) since its values can never change. As a bonus, you may see better performance, too.

2. If you do need to mutate the values, you could alternatively define your own implementations of == and Base.hash so they only care about the current value:

   ==(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))
   

   As @StefanKarpinski just pointed out on the mailing list, this isn't the default for mutable values "since it makes it easy to stick something in a dict, then mutate it, and 'lose it'." That is, the object's hash value has changed but the dictionary stored it in a place based upon its old hash value, and now you can no longer access that key/value pair by key lookup. Even if you create a second object with the same original properties as the first it won't be able to find it since the dictionary checks equality after finding a hash match. The only way to lookup that key is to mutate it back to its original value or explicitly asking the dictionary to Base.rehash! its contents.

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

- mbauman