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!

Answer 1

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.

Answer 2

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.)