`getindex` function for a `Dict{X,Int}` with keys of custom type `X` behaves not as expected : keys not found

dictionary

#1

I wish to use the key-indexing in a Dict{X,Int} where X is defined as the following:

mutable struct X
    i::Int
end
import Base: isless, isequal
isless(a::X,b::X) = isless(a.i,b.i)
isequal(a::X,b::X) = isequal(a.i,b.i)

Then I want to use X(6) as an index of a dictionary

DX = Dict(X(i)=>i for i=1:10)

but , I cannot do this.

#NOTE doesn't work as expected
X6 = X(6)
DX[X6] # error

I got an error: key not found. However, if I retrieve the keys from DX, then I got what I wanted:

#NOTE works
kDX = sort(collect(keys(DX)))
DX[kDX[6]]

Question:

what is going on? I know it is somehow related to the hash function… But is it conceptually wrong to use DX[X(6)] to retrive values?


#2
julia> Base.hash(x::X) = hash(x.i)

julia> DX[X6]
6

Dict uses hash function to find the key, but Base.hash isn’t automatically defined for mutable structs since you can change its content and thus invalidate the key (you can see the same behavior in other languages as well). Defining Base.hash() solves the problem, but make sure not to modify instance of X while it’s a key in a Dict. Or better use (immutable) structs which define correct Base.hash automatically:

julia> struct X
           i::Int
       end

julia> import Base: isless, isequal

julia> isless(a::X,b::X) = isless(a.i,b.i)
isless (generic function with 71 methods)

julia> isequal(a::X,b::X) = isequal(a.i,b.i)
isequal (generic function with 23 methods)

julia> DX = Dict(X(i)=>i for i=1:10)
Dict{X,Int64} with 10 entries:
  X(1)  => 1
  X(7)  => 7
  X(5)  => 5
  X(8)  => 8
  X(4)  => 4
  X(10) => 10
  X(3)  => 3
  X(2)  => 2
  X(6)  => 6
  X(9)  => 9

julia> X6 = X(6)
X(6)

julia> DX[X6] # no error
6

#3

Overload the hash(x, h::UInt) version instead.


#4

thanks @dfdx @yuyichao ! Problem solved.

I realized that in the hashing.jl line 23

the objectid of my struct X is actually hashed because the type is “no specialize”, i.e hash() does not understand what is struct X. Then I need to specialize (specify) it :smiley: