# Set inconsistencies with structs

**URL:** <https://discourse.julialang.org/t/set-inconsistencies-with-structs/60637>\
**Category:** General Usage\
**Tags:** question\
**Created:** [May 6, 2021, 10:28am UTC](https://discourse.julialang.org/t/set-inconsistencies-with-structs/60637 "2021-05-06T10:28:58Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![lklein](https://avatars.discourse-cdn.com/v4/letter/l/839c29/32.png) [@lklein](https://discourse.julialang.org/u/lklein)\
**Post date:** [May 6, 2021, 10:28am UTC](https://discourse.julialang.org/t/set-inconsistencies-with-structs/60637/1 "2021-05-06T10:28:58Z")

</div>

Hi all,

I was working with sets and self defined structs and noticed the following:

```julia
julia> struct A a end
       Base.:(==)(a::A,b::A) = true
       set = Set{A}()
       push!(set, A(1))
Set{A} with 1 element:
  A(1)

julia> A(2) in set
true

julia> A(7) in set
false

```

My expectation would have been for the last two lines to be consistent.  
While experimenting with this I found that the problem is with different hashes being generated for different objects. It is apparent from the definition of `Set` that an equivalence relation is required to compare different objects in the `Set`. This equivalence relation seems to be:

> a~b \Leftrightarrow (a == b && hash(a) == hash(b))

as shown by:

```julia
julia> struct A a end
       Base.:(==)(a::A,b::A) = true
       Base.hash(a::A) = UInt(1)   
       set = Set{A}()
       push!(set, A(1))
Set{A} with 1 element:
  A(1)

julia> A(2) in set
true

julia> A(7) in set
true

```

This leads to undefined behaviour when using self defined structs with custom `Base.:(==)` in Sets or Dicts.  
Is this intentional?

---

<div class="post-metadata">

**Author:** ![pfitzseb](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pfitzseb/32/45566_2.png) [@pfitzseb](https://discourse.julialang.org/u/pfitzseb)\
**Post date:** [May 6, 2021, 10:49am UTC](https://discourse.julialang.org/t/set-inconsistencies-with-structs/60637/2 "2021-05-06T10:49:57Z")

</div>

Yes, as per the docstrings for `hash`/`==`/`isequal`:

```julia
help?> isequal
search: isequal issetequal

  isequal(x, y)

  Similar to ==, except for the treatment of floating point numbers and of missing
  values. isequal treats all floating-point NaN values as equal to each other,
  treats -0.0 as unequal to 0.0, and missing as equal to missing. Always returns a
  Bool value.

  Implementation
  ≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡

  The default implementation of isequal calls ==, so a type that does not involve
  floating-point values generally only needs to define ==.

  isequal is the comparison function used by hash tables (Dict). isequal(x,y) must
  imply that hash(x) == hash(y).

  This typically means that types for which a custom == or isequal method exists
  must implement a corresponding hash method (and vice versa). Collections
  typically implement isequal by calling isequal recursively on all contents.

  Scalar types generally do not need to implement isequal separate from ==, unless
  they represent floating-point numbers amenable to a more efficient
  implementation than that provided as a generic fallback (based on isnan,
  signbit, and ==).

```

```julia
help?> hash
search: hash hasmethod haskey hasfield hasproperty skipchars Threads MathConstants

  hash(x[, h::UInt])

  Compute an integer hash code such that isequal(x,y) implies hash(x)==hash(y).
  The optional second argument h is a hash code to be mixed with the result.

  New types should implement the 2-argument form, typically by calling the
  2-argument hash method recursively in order to mix hashes of the contents with
  each other (and with h). Typically, any type that implements hash should also
  implement its own == (hence isequal) to guarantee the property mentioned above.
  Types supporting subtraction (operator -) should also implement widen, which is
  required to hash values inside heterogeneous arrays.

```

---

<div class="post-metadata">

**Author:** ![lklein](https://avatars.discourse-cdn.com/v4/letter/l/839c29/32.png) [@lklein](https://discourse.julialang.org/u/lklein)\
**Post date:** [May 6, 2021, 1:22pm UTC](https://discourse.julialang.org/t/set-inconsistencies-with-structs/60637/3 "2021-05-06T13:22:45Z")

</div>

Thanks for your answer.  
I am actually more confused now.

```julia
Compute an integer hash code such that isequal(x,y) implies hash(x)==hash(y).

```

This part of the documentation from `hash()` sounds to me like changing the `(==)` function should automatically change the hash function as well.  
Also:

```julia
Typically, any type that implements hash should also
  implement its own == (hence isequal) to guarantee the property mentioned above.

```

this explains, that changing hash() also requires you to change `(==)`. But nowhere is the inverse mentioned.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [May 6, 2021, 1:38pm UTC](https://discourse.julialang.org/t/set-inconsistencies-with-structs/60637/4 "2021-05-06T13:38:36Z")

</div>

> [@lklein](#):
>
> like changing the `(==)` function should automatically change the hash function as well

No, that is up to the programmer. That’s kind of the point, it cannot be done automatically.

---

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [May 6, 2021, 2:36pm UTC](https://discourse.julialang.org/t/set-inconsistencies-with-structs/60637/5 "2021-05-06T14:36:33Z")

</div>

> [@lklein](#):
>
> But nowhere is the inverse mentioned.

The documentation of `==` does say:

```julia
If your type will be used as a dictionary key, it should therefore also implement hash.

```

but I agree that could be more clearly and prominently stated.

What phrasing of the documentation of `==` would have helped you avoid the misunderstanding? If we can come up with something better, then we can improve the docs and hopefully save the next person from going through the same trouble you did.