# Dictionary has same key more than once

For my chess engine with alpha-beta-pruning algorithm with transposition tables, I wanted to create a Dictionary, that uses my own hash function. So i did the following:

``````mutable struct Zobrist
val::UInt
end

Base.hash(a::Zobrist, h::UInt) = xor(a.val, h)
Base.:(==)(a::Zobrist, b::Zobrist) = a.val == b.val

gTranspositions = Dict{Zobrist, Transpositionentry}();
``````

This is the Transpositionentry structure:

``````mutable struct Transpositionentry
value::Int64
recursion::Int64
vtype::Valuetype
end
``````

After running my algorithm the dictionary looks like this:

``````Dict{Zobrist, Transpositionentry} with 116849 entries:
Zobrist(0x3fb8d5fc38d3094c) => Transpositionentry(40, 1, upperbound)
Zobrist(0x7ec1223b4016e966) => Transpositionentry(-15, 1, upperbound)
Zobrist(0x491a5a230f24671a) => Transpositionentry(-75, 1, lowerbound)
Zobrist(0x491a5a230f24671a) => Transpositionentry(55, 1, upperbound)
Zobrist(0x491a5a230f24671a) => Transpositionentry(25, 1, upperbound)
Zobrist(0x63b155121ea7907e) => Transpositionentry(-65, 1, upperbound)
....
``````

As you can see, for example the zobrist key with the value “491a5a230f24671a” is more than one time in the dictionary and i don’t know how that is possible.

Does someone have an idea what the problem is?

1 Like

I think you might need to define isequal rather than == (although I thought isequal had a fallback to ==). also, you probably want immutable structs here. they will be faster

2 Likes

This may be caused by mutation of keys. I made a simpler example based on yours:

``````julia> mutable struct MyRef{T}  val::T  end
julia> Base.hash(a::MyRef, h::UInt) = xor(a.val, h)
julia> Base.:(==)(a::MyRef, b::MyRef) = a.val == b.val

julia> d = Dict{MyRef{Int}, Symbol}()
Dict{MyRef{Int64}, Symbol}()

julia> x = MyRef(0); y = MyRef(0); d[x] = :x; d[y] = :y; d # y replaces x
Dict{MyRef{Int64}, Symbol} with 1 entry:
MyRef{Int64}(0) => :y

julia> y.val = 1; d[x] = :x; d # mutate y, now add x
Dict{MyRef{Int64}, Symbol} with 2 entries:
MyRef{Int64}(1) => :y
MyRef{Int64}(0) => :x

julia> y.val = 0; d # mutate y back, now same key as x
Dict{MyRef{Int64}, Symbol} with 2 entries:
MyRef{Int64}(0) => :y
MyRef{Int64}(0) => :x

julia> d[x], d[y] # uh oh
(:y, :y)
``````
2 Likes

Good call. That’s the actual problem.

1 Like

We can’t say that’s the problem for sure, we don’t know what algorithm resulted in OP’s dictionary.

1 Like

Given how Zobrist hashes work and that `Zobrist` is a mutable struct, it’s highly likely that mutation is the problem. The solution would be to either make `Zobrist` an immutable struct and adapt the code as needed or simply key the transposition table on the Zobrist value rather than the object.

1 Like

Now that I look up Zobrist hashing, it doesn’t seem like a mutable object is necessary? I still don’t understand the algorithm at all, really.

For thoroughness, when a key is inserted, its index is computed by the hash function, and the index does not change. So if the key’s value changes in a way that also changes its hash value, you have a couple problems: 1) it cannot be used to find its own existing index, 2) another key with the previous value (and thus hash value) can be inserted.

I was really careful not to say mutable or immutable struct because 1) a mutable struct can have `const` fields or fixed properties like `size(::Matrix)`, and the hash value is constant if it only depends on those, and 2) an immutable struct’s value and hash value can depend on a field holding a mutable instance e.g. many wrappers of mutable arrays are actually immutable structs.

1 Like