# \`unique(Vector{CustomStruct})\` requires method for hash | Bug or misleading documentation?

**URL:** <https://discourse.julialang.org/t/unique-vector-customstruct-requires-method-for-hash-bug-or-misleading-documentation/77974>\
**Category:** General Usage\
**Tags:** question, hash\
**Created:** [March 16, 2022, 2:30pm UTC](https://discourse.julialang.org/t/unique-vector-customstruct-requires-method-for-hash-bug-or-misleading-documentation/77974 "2022-03-16T14:30:33Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![aaronpeikert](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/aaronpeikert/32/34603_2.png) [@aaronpeikert](https://discourse.julialang.org/u/aaronpeikert)\
**Post date:** [March 16, 2022, 2:30pm UTC](https://discourse.julialang.org/t/unique-vector-customstruct-requires-method-for-hash-bug-or-misleading-documentation/77974/1 "2022-03-16T14:30:33Z")

</div>

I was surprised to see that it is not enough to implement `isequal` to get `unique` for free, though the documentation seems to suggest it:

[https://docs.julialang.org/en/v1/base/collections/#Base.unique](https://docs.julialang.org/en/v1/base/collections/#Base.unique)

> Return an array containing only the unique elements of collection `itr` , as determined by [`isequal`](https://docs.julialang.org/en/v1/base/base/#Base.isequal)

The problem seems to be that `unique` implicitly assumes that `struct1 == struct2` implies `hash(struct1) == hash(struct2)`.

I noticed this behaviour for a struct with two fields where the order does not matter for comparison. Here an MWE:

```julia
struct UndirectedEdge
    f1
    f2
end

import Base.==
==(x::UndirectedEdge, y::UndirectedEdge) = (x.f1 == y.f1 && x.f2 == y.f2) || (x.f2 == y.f1 && x.f1 == y.f2)
e1 = UndirectedEdge(:a, :b)
e2 = UndirectedEdge(:b, :a) # equal to e1
e3 = UndirectedEdge(:c, :a)

unique([e1, e2, e3])

e1 == e2
isequal(e1, e2) # isequal should be enough for unique

```

It works, when I additionally define a hash method:

```julia
import Base.hash
hash(x::UndirectedEdge, h::UInt) = hash(sort([x.f1, x.f2]), h)

unique([e1, e2, e3])

```

---

<div class="post-metadata">

**Author:** ![StevenWhitaker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevenwhitaker/32/9749_2.png) [@StevenWhitaker](https://discourse.julialang.org/u/StevenWhitaker)\
**Post date:** [March 16, 2022, 2:37pm UTC](https://discourse.julialang.org/t/unique-vector-customstruct-requires-method-for-hash-bug-or-misleading-documentation/77974/2 "2022-03-16T14:37:04Z")

</div>

It works for me if I define `Base.isequal` instead of `Base.==`.

EDIT: It even works when I define `Base.==` as you did (no `Base.hash` method necessary).

---

<div class="post-metadata">

**Author:** ![jakobnissen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jakobnissen/32/13477_2.png) [@jakobnissen](https://discourse.julialang.org/u/jakobnissen)\
**Post date:** [March 16, 2022, 2:37pm UTC](https://discourse.julialang.org/t/unique-vector-customstruct-requires-method-for-hash-bug-or-misleading-documentation/77974/3 "2022-03-16T14:37:49Z")

</div>

This is documented in the docs for `isequal`:

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

, as well as in the docs of `hash`. But yes, this invariant is a little to easy to forget, for which there is an old issue: [custom hashing is too easy to accidentally break · Issue #12198 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/issues/12198)

---

<div class="post-metadata">

**Author:** ![aaronpeikert](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/aaronpeikert/32/34603_2.png) [@aaronpeikert](https://discourse.julialang.org/u/aaronpeikert)\
**Post date:** [March 16, 2022, 2:42pm UTC](https://discourse.julialang.org/t/unique-vector-customstruct-requires-method-for-hash-bug-or-misleading-documentation/77974/4 "2022-03-16T14:42:01Z")

</div>

Performance aside, can I define `isequal` in terms of hashing?

```julia
import Base.==
import Base.hash

hash(x::UndirectedEdge, h::UInt) = hash(sort([x.f1, x.f2]), h)
==(x::UndirectedEdge, y::UndirectedEdge) = hash(x) == hash(y)

```

---

<div class="post-metadata">

**Author:** ![jakobnissen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jakobnissen/32/13477_2.png) [@jakobnissen](https://discourse.julialang.org/u/jakobnissen)\
**Post date:** [March 16, 2022, 2:43pm UTC](https://discourse.julialang.org/t/unique-vector-customstruct-requires-method-for-hash-bug-or-misleading-documentation/77974/5 "2022-03-16T14:43:14Z")

</div>

I think so! But then you might get nasty surprises if you find a hash collision.

---

<div class="post-metadata">

**Author:** ![aaronpeikert](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/aaronpeikert/32/34603_2.png) [@aaronpeikert](https://discourse.julialang.org/u/aaronpeikert)\
**Post date:** [March 16, 2022, 3:06pm UTC](https://discourse.julialang.org/t/unique-vector-customstruct-requires-method-for-hash-bug-or-misleading-documentation/77974/6 "2022-03-16T15:06:30Z")

</div>

Thank you so much. It was not clear to me that I have to implement `hash` and `isequal` in tandem even if I do not care too much about hashing.

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [March 16, 2022, 5:02pm UTC](https://discourse.julialang.org/t/unique-vector-customstruct-requires-method-for-hash-bug-or-misleading-documentation/77974/7 "2022-03-16T17:02:02Z")

</div>

If you don’t implement them in tandem, things like putting your custom struct into a `Dict` may break, as it uses a hash to determine which bucket to place the object. It’s not necessarily related to whether you care about hashing itself, but what you want to do with it.