Sorting in ArrayMap may be failing to achieve its purpose

[gvlasov]

If I understand it correctly, ArrayMap innards are sorted in order to have deterministic ordering of its elements.

If that's true, then there is an error. ArrayMap#Cmp comparator compares string representation of objects if they are not Comparable. String representation is not a deterministic function, because if Object#toString() is not overridden, then it is a function of Object#hashCode(), which is not deterministic by definition. Thus, ordering of ArrayMap is not deterministic if its contents are not Comparable and don't override Object#toString() in a deterministic manner.

[dmarkov]

@yegor256 please dispatch this issue

[yegor256]

@Suseika but how can we solve this problem?

[gvlasov]

@yegor256 We can (the following are steps, not alternatives):

1. Get rid of sorting;
2. Make iteration order depend solely on insertion order;
3. Document that if a Map passed to ArrayMap(Map) constructor has non-deterministic ordering, then ArrayMap's ordering will be non-deterministic as well.

Of course, that will mean that we will be unable to do new ArayMap<>(hashMap) and have it iterated in a predictable manner, but that feature was unreliable in the first place.

[yegor256]

@Suseika as far as I understood your original ticket description, the problem exists only when we pass non-Comparable elements as keys, right?

[gvlasov]

@yegor256 That's right.

[yegor256]

@Suseika so in this case we don't really care what's going on in the map. We can't sort properly anyhow. This usage of String is just our internal workaround. There is no guarantee to the user about anything. I don't see what exactly is a bug?