dictionary - Go 中复杂键字典的唯一性，但 Julia 中没有？

Question

在 GO 中，当我使用结构作为映射的键时，键具有唯一性。

例如，以下代码生成一个只有一个键的 map :map[{x 1}:1]

package main

import (
    "fmt"
)

type MyT struct {
    A string
    B int
}

func main() {

    dic := make(map[MyT]int)

    for i := 1; i <= 10; i++ {
        dic[MyT{"x", 1}] = 1
    }

    fmt.Println(dic)
}

// result : map[{x 1}:1]

我试图在 Julia 中做同样的事情，但我有一个奇怪的惊喜:

这个 Julia 代码，类似于 GO 代码，生成一个包含 10 个键的字典!

    type MyT
        A::String
        B::Int64
    end

    dic = Dict{MyT, Int64}()

    for i in 1:10
        dic[MyT("x", 1)] = 1
    end

    println(dic)
    # Dict(MyT("x",1)=>1,MyT("x",1)=>1,MyT("x",1)=>1,MyT("x",1)=>1,MyT("x",1)=>1,MyT("x",1)=>1,MyT("x",1)=>1,MyT("x",1)=>1,MyT("x",1)=>1,MyT("x",1)=>1)

    println(keys(dic))
    # MyT[MyT("x",1),MyT("x",1),MyT("x",1),MyT("x",1),MyT("x",1),MyT("x",1),MyT("x",1),MyT("x",1),MyT("x",1),MyT("x",1)]

那么我做错了什么？

谢谢@DanGetz 的解决方案! :

immutable MyT     # or struct MyT with julia > 0.6
    A::String
    B::Int64
end

dic = Dict{MyT, Int64}()

for i in 1:10
    dic[MyT("x", 1)] = 1
end

println(dic)         # Dict(MyT("x", 1)=>1)
println(keys(dic))   # MyT[MyT("x", 1)]

Answer 1

在 Julia 中，可变值按身份进行哈希处理，因为如果没有关于类型表示什么的额外知识，就无法知 Prop 有相同结构的两个值是否意味着相同的事物。如果您在将一个值用作字典键之后对其进行变异，则按值对可变对象进行散列可能会特别成问题——这在按标识进行散列时不是问题，因为即使修改了可变对象的标识也保持不变。另一方面，按值散列不可变对象(immutable对象)是完全安全的——因为它们不能被改变，因此这是不可变类型的默认行为。在给定的示例中，如果您使 MyT不可变的，您将自动获得您期望的行为:

immutable MyT # `struct MyT` in 0.6
    A::String
    B::Int64
end

dic = Dict{MyT, Int64}()

for i in 1:10
    dic[MyT("x", 1)] = 1
end

julia> dic
Dict{MyT,Int64} with 1 entry:
  MyT("x", 1) => 1

julia> keys(dic)
Base.KeyIterator for a Dict{MyT,Int64} with 1 entry. Keys:
  MyT("x", 1)

对于持有 String 的类型和 Int如果要用作哈希键的值，不变性可能是正确的选择。事实上，不变性往往是正确的选择，这就是为什么引入结构类型的关键字在 0.6 中已更改为 struct。对于不可变结构和 mutable struct对于可变结构——原则上人们会首先找到更短、更简单的名称，所以这应该是更好的默认选择——即不变性。

正如@ntdef 所写，您可以通过重载 Base.hash 来更改类型的散列行为。功能。然而，他的定义在某些方面是不正确的(这可能是我们未能更突出和更彻底地记录这一点的错):

Base.hash 的方法签名你想重载的是Base.hash(::T, ::UInt) .

Base.hash(::T, ::UInt)方法必须返回 UInt值(value)。

如果您重载 Base.hash ，你也应该重载Base.==匹配。

因此，这将是使您的可变类型按值散列的正确方法(重新定义 MyT 需要新的 Julia session ):

type MyT # `mutable struct MyT` in 0.6
    A::String
    B::Int64
end

import Base: ==, hash

==(x::MyT, y::MyT) = x.A == y.A && x.B == y.B

hash(x::MyT, h::UInt) = hash((MyT, x.A, x.B), h)

dic = Dict{MyT, Int64}()

for i in 1:10
    dic[MyT("x", 1)] = 1
end

julia> dic
Dict{MyT,Int64} with 1 entry:
  MyT("x", 1) => 1

julia> keys(dic)
Base.KeyIterator for a Dict{MyT,Int64} with 1 entry. Keys:
  MyT("x", 1)

手动操作有点烦人，但是 AutoHashEquals包自动执行此操作，从而消除乏味。您需要做的就是在 type 前面加上前缀用 @auto_hash_equals 定义宏:

using AutoHashEquals

@auto_hash_equals type MyT # `@auto_hash_equals mutable struct MyT` in 0.6
    A::String
    B::Int64
end

底线:

如果您的类型应该具有基于值的相等和散列，请认真考虑使其不可变。

如果您的类型确实必须是可变的，那么请认真考虑将其用作哈希键是否是个好主意。

如果您确实需要使用可变类型作为具有基于值的相等性和散列语义的散列键，请使用 AutoHashEquals包裹。