Is there some kind of optimisation for checking set contents against another set's contents or does ...

# getting-started

[dave08]

Is there some kind of optimisation for checking set contents against another set's contents or does it just go through the whole set and check against every element? And does == check a set's content?

[Youssef Shoaib [MOD]]

Well I mean, it does check the size of the set first if that helps. I believe otherwise yes it goes through the whole set and checks that the other set contains all those elements. There's an optimisation there with hashCode probably, which speeds things up.

[dave08]

I guess you mean hashCode on each element, thanks!

[dave08]

So when people talk about checking deeply in lists/sets they're talking about if you store classes that don't implement hashCode?

[CLOVIS]

You can find the answer here: https://github.com/JetBrains/kotlin/blob/d39a7e59a75a464c656af6bed9718c427e91f236/libraries/stdlib/src/kotlin/collections/AbstractSet.kt#L42

I'm surprised it only checks the other set contains all elements, that doesn't sound symmetric to me?

[CLOVIS]

Ah, no, if the other set has all the elements of the first, and they have the same size, they must be equivalent.

[Youssef Shoaib [MOD]]

Yep, unless you have a very strange set impl, but if so then you have bigger issues

[CLOVIS]

I guess you mean hashCode on each element

That's going to depend on the Set implementation; the right-hand-side set's containAll is the one that decides. HashSet will use the hash to compare, but some other implementations like EnumSet won't.

[CLOVIS]

> So when people talk about checking deeply in lists/sets they're talking about if you store classes that don't implement hashCode?
In Kotlin, you shouldn't really need to do it manually, since Set.equals does it for you.

[dave08]

That's going to depend on the Set implementation; the right-hand-side set's containAll is the one that decides. HashSet will use the hash to compare, but some other implementations like EnumSet won't.

And I guess kotlin's setOf(..) uses a LinkedHashSet (it seems to be expect in https://github.com/JetBrains/kotlin/blob/d39a7e59a75a464c656af6bed9718c427e91f236/libraries/stdlib/src/kotlin/collections/Sets.kt#L54? And listOf() would also be the same?

[CLOVIS]

setOf : yes
listOf : well, no, it's not a Set , so it will never be equal to a Set (there's a shortcut that tests the type)

[dave08]

Yeah, I meant comparing two lists...

[CLOVIS]

List comparison: https://github.com/JetBrains/kotlin/blob/d39a7e59a75a464c656af6bed9718c427e91f236/libraries/stdlib/src/kotlin/collections/AbstractList.kt#L157

[CLOVIS]

Looks like it uses equals directly on all elements

[CLOVIS]

I wonder if using hashCode here may be a valuable performance improvement. There's a chance it may break code when hashCode is not implemented properly

[CLOVIS]

Hm, I guess when you check equality between lists, you either expect them to be identical or very clearly different, so it shouldn't matter much

[dave08]

so it shouldn't matter much

you don't mean performance?

[Youssef Shoaib [MOD]]

I think equals is expected to perform a hashcode comparison usually btw. At least I think that's what some of the generated equals impls look like

[CLOVIS]

I mean, if you are comparing two lists that are different:
• they're probably not the same size, so done
• they probably have an element towards the start that's different, so it gives up early
So I guess the performance doesn't matter that much since you always give up early

[CLOVIS]

I think equals is expected to perform a hashcode comparison usually btw.

At the very least, having an hashCode that doesn't match equals is considered a bug, even if it's not called, so maybe we can say that all code broken by this was already broken.

[Youssef Shoaib [MOD]]

The fact that HashSet uses hashcode directly is because it already deals with them to have fast access to elements. Otherwise it would've used equals I guess. I think the expectation is that equals returns false pretty fast for most things.

[Youssef Shoaib [MOD]]

I figured it was more to allow some way of associating a number to an object easily, thus allowing for hash tables. I think the onus is usually on the developer to have their equals include the same quickly-returning-false checks. I might completely wrong though; this is outside my realm of knowledge

[CLOVIS]

I figured it was more to allow some way of associating a number to an object easily, thus allowing for hash tables.

I think you're right

I think the onus is usually on the developer to have their equals include the same quickly-returning-false checks. I might completely wrong though; this is outside my realm of knowledge

It's the first time I hear of this, though. I've never seen an equals call use hashCode internally except containers (sets…).

[CLOVIS]

At the very least, I've never seen an equals implementation call the same class' hashCode .

[dave08]

Thanks a lot for this interesting discussion 👍🏼!