# Dictionary has same key more than once

**URL:** <https://discourse.julialang.org/t/dictionary-has-same-key-more-than-once/98019>\
**Category:** New to Julia\
**Tags:** dictionary\
**Created:** [April 28, 2023, 12:10am UTC](https://discourse.julialang.org/t/dictionary-has-same-key-more-than-once/98019 "2023-04-28T00:10:01Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![okai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/okai/32/49336_2.png) [@okai](https://discourse.julialang.org/u/okai)\
**Post date:** [April 28, 2023, 12:10am UTC](https://discourse.julialang.org/t/dictionary-has-same-key-more-than-once/98019/1 "2023-04-28T00:10:01Z")

</div>

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:

```julia
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:

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

```

After running my algorithm the dictionary looks like this:

```julia
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?

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [April 28, 2023, 12:23am UTC](https://discourse.julialang.org/t/dictionary-has-same-key-more-than-once/98019/2 "2023-04-28T00:23:49Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [April 28, 2023, 1:14am UTC](https://discourse.julialang.org/t/dictionary-has-same-key-more-than-once/98019/3 "2023-04-28T01:14:47Z")

</div>

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

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

```

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [April 28, 2023, 1:16am UTC](https://discourse.julialang.org/t/dictionary-has-same-key-more-than-once/98019/4 "2023-04-28T01:16:54Z")

</div>

Good call. That’s the actual problem.

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [April 28, 2023, 1:17am UTC](https://discourse.julialang.org/t/dictionary-has-same-key-more-than-once/98019/5 "2023-04-28T01:17:37Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [April 28, 2023, 6:06am UTC](https://discourse.julialang.org/t/dictionary-has-same-key-more-than-once/98019/6 "2023-04-28T06:06:43Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [April 28, 2023, 6:57am UTC](https://discourse.julialang.org/t/dictionary-has-same-key-more-than-once/98019/7 "2023-04-28T06:57:21Z")

</div>

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.