Imporre un ordinamento totale su tutte le istanze di *qualsiasi* classe in Java

Question

Non sono sicuro che il seguente codice garantisca tutte le condizioni fornite nel Javadoc di Comparator.

class TotalOrder<T> implements Comparator<T> {

    public boolean compare(T o1, T o2) {
        if (o1 == o2 || equal(o1, o2)) return 0;

        int h1 = System.identityHashCode(o1);
        int h2 = System.identityHashCode(o2);

        if (h1 != h2) {
            return h1 < h2 ? -1 : 1;
        }

        // equals returned false but identity hash code was same, assume o1 == o2
        return 0;
    }

    boolean equal(Object o1, Object o2) {
        return o1 == null ? o2 == null : o1.equals(o2);
    }
}

Il codice sopra imporrà un ordinamento totale su tutte le istanze di qualsiasi classe, anche se quella classe non implementa Comparable?

Answer 1

Ehi, guarda cosa ho trovato!

http://gafter.blogspot.com/2007/03/compact-object-comparator.html

Oh sì, ho dimenticato IdentityHashMap (solo Java 6 e versioni successive).Devi solo prestare attenzione a rilasciare il tuo comparatore.

Answer 2

Ehi, guarda cosa ho trovato!

http://gafter.blogspot.com/2007/03/compact-object-comparator.html

Questo e 'esattamente quello che stavo cercando.

Answer 3

Hai risposto nel tuo commento:

uguale restituito falso ma il codice hash di identità era lo stesso, si supponga o1 == o2

Sfortunatamente non puoi darlo per scontato.Nella maggior parte dei casi funzionerà, ma in alcuni casi eccezionali non funzionerà.E non puoi sapere quando.Quando si verifica un caso del genere, ciò comporterebbe, ad esempio, la perdita di istanze in TreeSets.

Answer 4

Non penso che lo faccia poiché questa clausola non è soddisfatta:

Infine, l'implementatore deve garantire che x.compareTo(y)==0 implichi che sgn(x.compareTo(z)) == sgn(y.compareTo(z)), per tutti gli z.

Poiché equal(o1, o2) dipende dall'implementazione di equals di o1, due oggetti che sono logicamente uguali (come determinato da equals) hanno ancora due identitàHashCodes diversi.

Quindi, quando li confronti con un terzo oggetto (z), potrebbero finire per produrre valori diversi per compareTo.

Ha senso?

Answer 5

Probabilmente dovresti sollevare un'eccezione se si arriva a quest'ultimo return 0 line --quando avviene una collisione di hash.Ho una domanda però:stai eseguendo un ordinamento totale sugli hash, il che immagino vada bene, ma non dovrebbe essere passata qualche funzione per definire un ordine lessicografico?

    int h1 = System.identityHashCode(o1);
    int h2 = System.identityHashCode(o2);
    if (h1 != h2) {
        return h1 < h2 ? -1 : 1;
    }

Posso immaginare che tu abbia gli oggetti come una tupla di due numeri interi che formano un numero reale.Ma non otterrai l'ordine corretto poiché stai solo prendendo un hash dell'oggetto.Dipende tutto da te se intendi hashing, ma per me non ha molto senso.

Answer 6

Sono d'accordo che questo non è l'ideale, da qui il commento.Eventuali suggerimenti?

Penso che ora ci sia un modo per risolverlo, perché non puoi accedere all'unica cosa che può distinguere due istanze:il loro indirizzo in memoria.Quindi ho solo un suggerimento:riconsidera la tua esigenza di avere un processo di ordinazione totale generale in Java :-)

Answer 7

Non sono proprio sicuro del System.identityHashCode(Object).Questo è più o meno ciò che == è usato per.Potresti preferire usare il file Object.hashCode() - è più in parallelo con Object.equals(Object).