Unclear "Comparison method violates its general contract!" in transitive comparator

Question

In Java8 I have an algorithm I cannot really change that orders a particular structure as follows:

• All elements in category XXX must go to the end of the array (does not matter the order)
• All other elements can have any order

It was implemented like this:

list.sort((o1, o2) -> {
        boolean isXXX1 = "XXX".equals(o1.getCategory());
        boolean isXXX2 = "XXX".equals(o2.getCategory());
        if(isXXX1) {
            return isXXX2 ? 0 : 1;
        } else if(isXXX2) {
            return -1;
        }
        return o1.hashCode() - o2.hashCode();
    });

Hashcode is created by ReflectionashCode on the PoJo objects, so I do not expect weird collisions.

Occasionally, apparently at random, this piece of code throws IllegalArgumentException: Comparison method violates its general contract!

I tried to debug it, but even with the same data in debug mode it does not break. What could be the cause? I dont see any case where the sorting does not respect the contract

Answer 1

TL;DR

Never use minus as a comparator function.

Your comparator ends with return o1.hashCode() - o2.hashCode();

Unfortunately, developers come up with this idea all the time and for some tests (i.e. with small values), it might seem to work.

The problem is that comparing arbitrary integer values (and hash codes may use the entire int value range) can lead to overflow, as the distance between two int values may be larger than the int value range.

The correct idiom would be return Integer.compare(o1.hashCode(), o2.hashCode());

There is no problem if a hash collision occurs, as that simply means that the two elements would be treated as equal for this particular sort operation, which is fine if you don’t care about their relative order anyway. In fact, you can treat all elements whose relative order is irrelevant as equal, replacing the last line with return 0;.

Or, simplify the entire operation with

list.sort(Comparator.comparing(o -> "XXX".equals(o.getCategory())));

Since Boolean values are comparable and its compareTo method will treat true as larger than false, it will move the matching elements to the end of the list.