compareTo involving non-comparable field: how to maintain transitivity?

Question

Consider a class with a comparable (consistent with equals) and a non-comparable field (of a class about which I do not know whether it overrides Object#equals or not).

The class' instances shall be compared, where the resulting order shall be consistent with equals, i.e. 0 returned iff both fields are equal (as per Object#equals) and consistent with the order of the comparable field. I used System.identityHashCode to cover most of the cases not covered by these requirements (the order of instances with same comparable, but different other value is arbitrary), but am not sure whether this is the best approach.

public class MyClass implements Comparable<MyClass> {
    private Integer intField;
    private Object nonCompField;

    public int compareTo(MyClass other) {
        int intFieldComp = this.intField.compareTo(other.intField);
        if (intFieldComp != 0)
            return intFieldComp;
        if (this.nonCompField.equals(other.nonCompField))
            return 0;
        // ...and now? My current approach:
        if (Systems.identityHashCode(this.nonCompField) < Systems.identityHashCode(other.nonCompField))
            return -1;
        else
            return 1;
     }
}

Two problems I see here:

• If Systems.identityHashCode is the same for two objects, each is greater than the other. (Can this happen at all?)
• The order of instances with same intField value and different nonCompField values need not be consistent between runs of the program, as far as I understand what Systems.identityHashCode does.

Is that correct? Are there more problems? Most importantly, is there a way around this?

Answer 1

Systems.identityHashCode […] the same for two objects […] (Can this happen at all?)

Yes it can. Quoting from the Java API Documentation:

As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects.
identityHashCode(Object x) returns the same hash code for the given object as would be returned by the default method hashCode(), whether or not the given object's class overrides hashCode().

So you may encounter hash collisions, and with memory ever growing but hash codes staying fixed at 32 bit, they will become increasingly more likely.

The order of instances with same intField value and different nonCompField values need not be consistent between runs of the program, as far as I understand what Systems.identityHashCode does.

Right. It might even be different during a single invocation of the same program: You could have (1,foo) < (1,bar) < (1,baz) even though foo.equals(baz).

Most importantly, is there a way around this?

You can maintain a map which maps each distinct value of the non-comparable type to a sequence number which you increase for each distinct value you encounter.

Memory management will be tricky, though: You cannot use a WeakHashMap as the code might make your key object unreachable but still hold a reference to another object of the same value. So either you maintain a list of weak references to all the objects of a given value, or you simply use strong references and accept the fact that any uncomparable value ever encountered will never be garbage collected.

Note that this scheme will still not result in reproducible sequence numbers unless you create values reproducibly in just the same order.