Support: why the iteration in the operator== algorithm? about built_collection.dart HOT 3 CLOSED

Hi Daniel,

Thanks for the detailed issue.

Such an equals method will work most of the time, but it fails as soon as there are hash collisions. That is, if different lists end up with the same hash. Since we're using a 32 bit hash, the best case is a one in four billion chance of a collision. (If the hash function is perfect).

That sounds like a lot, but due to the birthday paradox you need to square root it for collections. So actually the number of hashes that will lead to a problem is only 2^16, i.e. 65536. This is a number that is easily small enough to turn up in practice.

An equals method is supposed to work 100% of the time :) ... if people want "probably equals", which would indeed be much faster, they can directly check the hashCode. This will probably happen as part of an algorithm that takes into account the probability of collisions and does check using "equals" when needed.

from built_collection.dart.

@davidmorgan, thanks for the answer. Since it's not really an issue, we can close this :)

TL;DR: hashCode match does not guarantee equality, hence the algorithm.

from built_collection.dart.

It's interesting to think about adding a wide enough hash that it can be used for equality, though. You could keep 128 bit hashes, then you should be okay with ~2^64 items. Plenty :)

I think we should have a use case for it first, though, i.e. an algorithm/system that's slow because of equality on lists and needs speeding up.

For UI code of the type I work on lists are usually limited in size to what you can display to a user, and the major cost is rendering rather than data processing. So, not much benefit to be had.

from built_collection.dart.