Why isn't isequal(x,y) = hash(x) == hash(y)


From the 0.6.2 documentation

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

This typically means that if you define your own == function then you must define a corresponding hash (and vice versa). Collections typically implement isequal by calling isequal recursively on all contents.

Based on the first sentence you’d think that the default implementation of isequal is

isequal(x,y) = hash(x) == hash(y)

But the various implementations in Base do something completely different. Why is that?

Also, the documentation says “if you define your own == function then you must define a corresponding hash”.

Did it mean to say “if you define your own isequal function then you must define a corresponding hash”?


Because hash collisions exist.


Consider the example

julia> immutable Foo

julia> Base.hash(ff::Foo) = ff.x % 2 

julia> Base.isequal(ff::Foo, gg::Foo) = ff.x == gg.x

( you should actually overload Base.hash(x, h::UInt)::UInt but for this example)

So if they are equal then they will have the same hash.
We have met the requirement.
equals implies hashes match.

But the reverse does not hold.
Not everything with the same hash is equal.

julia> a = Foo(2)

julia> b = Foo(2)

julia> c = Foo(4)

julia> isequal(a,b)

julia> isequal(a,c)

julia> hash(a)==hash(b)

julia> hash(a)==hash(c)