Java7 - Comparison method violates its general contract (TimSort.java)

Question

Here is the stack trace I am getting

Caused by: java.lang.IllegalArgumentException: Comparison method violates its general contract!
        at java.util.TimSort.mergeLo(TimSort.java:777)
        at java.util.TimSort.mergeAt(TimSort.java:514)
        at java.util.TimSort.mergeCollapse(TimSort.java:441)
        at java.util.TimSort.sort(TimSort.java:245)
        at java.util.Arrays.sort(Arrays.java:1512)
        at java.util.ArrayList.sort(ArrayList.java:1454)
        at java.util.Collections.sort(Collections.java:175)
        at xxx.sortDisplayFields(OfferFieldLayout.java:521)

Here is the compare method:

  public int compare(Field pObject1, Field pObject2)
{
    int compare = 0;              

   //...
    if (compare == 0)
    {
        if (pObject1.hashCode() <= pObject2.hashCode())
        {
            compare = -1;
        }
        else
        {
            compare =  1;
        }
    }

    return compare;
}

I think this is due to the transitive property not being respected : transitivity: if A > B and B > C then for any A, B and C: A > C. I am trying to come up with a counter example but I am failing here, any help appreciated!

Possible duplicate of [Java error: Comparison method violates its general contract](https://stackoverflow.com/questions/11441666/java-error-comparison-method-violates-its-general-contract) — Kon, Jul 18 '17 at 18:40
The error started since the switch to Java8 since the change in the sort came with Java7 — Astro, Jul 18 '17 at 18:46

marstran · Accepted Answer · 2017-07-18T19:13:48.447

Your function can never return 0! This means that if everything in the objects are equal, including the hashcodes, then pObject1.compare(pObject2) will not equal pObject2.compare(pObject1). The compare function must be symmetric. I also think you swapped around -1 and 1 in that test, so your last check should be this:

if (compare == 0) {
    if (pObject1.hashCode() < pObject2.hashCode()) {
        compare = 1;
    } else if (pObject1.hashCode() > pObject2.hashCode()) {
        compare =  -1;
    }
}

return compare;

And by the way, your objects should implement the Comparable interface, and the method should be called compareTo.

And finally, comparing hashcodes is not a good idea to begin with. They can collide even though the objects are not equal. This means that your compareTo method can return 0 when the objects are not equal. This is also a breach of the compareTo contract.

Thanks, I was suspecting this part in the code. I think I should just use this return Integer.compare(pObject1.hashCode(), pObject2.hashCode()) like the next answer mention. Or Just return 0 at that point since using hashCode seems like a bad practice.. — Astro, Jul 18 '17 at 18:57

score 2 · Answer 2 · answered Jul 18 '17 at 18:50

if (pObject1.hashCode() <= pObject2.hashCode())
{
   compare = -1;
} else {
   compare =  1;
}

This part is certainly not compatible with the compareTo contract, as if the hash codes are equal, the comparison is not equal. Instead, you should use return Integer.compare(pObject1.hashCode(), pObject2.hashCode()), assuming you want to use hash codes for comparisons at all. (It's not usually a good idea, as hash codes can just happen to collide.)

Java7 - Comparison method violates its general contract (TimSort.java)

2 Answers2