Struct equality seems weird inside Sets

General Usage
, ,
1

Screen Shot 2020-12-04 at 7.02.36 PM
Screen Shot 2020-12-04 at 7.02.36 PM924×784 75.1 KB

Can someone help me understand this behavior?

So I define a struct. To define what equality means for the struct, I define the == function for the struct, and also a hash() function.

Note the println() statements in the definition.

It seems that for the Set equality case, when the structs are not the same the program isn’t entering the == function. Why?

Code:

mutable struct ForbiddenPair
    comp₁::Int
    comp₂::Int
end

function Base.:(==)(fp_1::ForbiddenPair, fp_2::ForbiddenPair)
    comp1s = (fp_1.comp₁ == fp_2.comp₁)
    comp2s = (fp_1.comp₂ == fp_2.comp₂)
    println("Comp 1s: ", comp1s)
    println("Comp 2s: ", comp2s)
    comp1s && comp2s
end

Base.hash(fp::ForbiddenPair, h::UInt) = hash(fp.comp₁, hash(fp.comp₂, hash(:ForbiddenPair, h)))

a = ForbiddenPair(1, 2)
b = ForbiddenPair(1, 2)
c = ForbiddenPair(2, 2)

println(a == b, " ", hash(a) == hash(b))
println()
println(a == c, " ", hash(a) == hash(c))

a = Set([ForbiddenPair(1, 2)])
b = Set([ForbiddenPair(1, 2)])
c = Set([ForbiddenPair(2, 2)])

println(a == b, " ", hash(a) == hash(b))
println()
println(a == c, " ", hash(a) == hash(c))
2

Could you please post your actual code instead of a screenshot? See PSA: how to quote code with backticks for some helpful tips on formatting code on Discourse. Screenshots make it harder to help you because there’s no way to copy your code to test it out locally.

2 Likes
3

Woops thanks for letting me know the etiquette, just made the edit!

4

Thanks!

I think all that’s going on here is that the hash for the entry in set c is different than the hash of the entry in set a, so the equality check can be performed without needing to use == at all. After all, that’s kind of the point of a hash table: most of the time we can skip equality checks when there is no hash collision.

1 Like
5

Thank you, that makes a lot of sense!

6

BTW, if you want to prove this for yourself, you can use the debugger to step into the actual calls and look what’s going on. To do that, you’ll need to install Debugger.jl via:

pkg> add Debugger

and then do

using Debugger
@enter a == c

Try s to step into the next call, so to step out of a call, and o to open the given function in a text editor. The fact that Julia is mostly implemented in Julia means that you can go all the way into the guts of how Set equality works without having to switch languages or tools.

3 Likes
7

You can see how the hash comes into play in Set comparisons by purposefully defining a bad hash function that leads to collisions. Try redoing the test, for example with

Base.hash(fp::ForbiddenPair, h::UInt) = hash(fp.comp₂)

If you make this change, then hash(ForbiddenPair(1,2))==hash(ForbiddenPair(2,2), so the set comparison needs to call == on the elements to figure out if they’re the same, and your extra lines will print.