2013-04-08 9 views
8

Sto sovrascrivendo i metodi equals e hashcode per un oggetto contenitore semplice per due interi. Ogni int riflette l'indice di un altro oggetto (non importa quale sia l'oggetto). Il punto della classe è rappresentare una connessione tra i due oggetti.Sovrascrittura di Java equivale a() e hashcode() per due interi intercambiabili

La direzione della connessione non è importante, pertanto il metodo equals deve restituire true indipendentemente dal modo in cui i due valori si trovano nell'oggetto E.g.

connectionA = new Connection(1,2); 
connectionB = new Connection(1,3); 
connectionC = new Connection(2,1); 

connectionA.equals(connectionB); // returns false 
connectionA.equals(connectionC); // returns true 

Ecco quello che ho (modificato dal codice sorgente per intero):

public class Connection { 
    // Simple container for two numbers which are connected. 
    // Two Connection objects are equal regardless of the order of from and to. 

    int from; 
    int to; 

    public Connection(int from, int to) { 
     this.from = from; 
     this.to = to; 
    } 

    // Modifed from Integer source code 
    @Override 
    public boolean equals(Object obj) { 
     if (obj instanceof Connection) { 
      Connection connectionObj = (Connection) obj; 
      return ((from == connectionObj.from && to == connectionObj.to) || (from == connectionObj.to && to == connectionObj.from)); 
     } 
     return false; 
    } 

    @Override 
    public int hashCode() { 
     return from*to; 
    } 
} 

Questo funziona però la mia domanda è: C'è un modo migliore per raggiungere questo obiettivo?

La mia preoccupazione principale è con il metodo hashcode() restituirà lo stesso codice hash per ogni due numeri interi che moltiplicano per uguagliare lo stesso numero. Per esempio.

3*4 = 12 
2*6 = 12 // same! 

La documentazione, http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Object.html#hashCode(), afferma che

Non è necessario che se due oggetti non sono uguali secondo le metodo equals (java.lang.Object), quindi chiamare il metodo hashCode su ognuno dei due oggetti deve produrre risultati interi distinti. Tuttavia, il programmatore deve essere consapevole del fatto che la produzione di distinti risultati interi per oggetti non uguali può migliorare le prestazioni degli hash .

Se qualcuno può vedere un modo semplice per ridurre il numero di codici hash corrispondenti, sarei grato di una risposta.

Grazie!

Tim

PS Sono consapevole che c'è una java.sql.Connection che potrebbe causare alcuni fastidi di importazione. L'oggetto ha in realtà un nome più specifico nella mia applicazione, ma per brevità l'ho abbreviato in Connection qui.

risposta

3

Questo è ampiamente accettato approccio:

@Override 
public int hashCode() { 
    int res = 17; 
    res = res * 31 + Math.min(from, to); 
    res = res * 31 + Math.max(from, to); 
    return res; 
} 
+1

Questo non funzionerà in questo caso poiché da e per non è necessariamente uguale. Invece, magari ordinali prima. – ddmps

+0

Ho appena provato questo in Excel. Pescis è corretto, non dà lo stesso res se si scambiano i numeri (a meno che non siano gli stessi). –

+0

@Pescis "non funzionerà", puoi essere più specifico? –

2

credo, qualcosa di simile a

@Override 
public int hashCode() { 
    return to*to+from*from; 
} 

è abbastanza buono

+0

cos'è "abbastanza buono"? –

+0

per in (1..1000) e due in (1..from) ho avuto 330159 collisioni. La risposta accettata ha 497477 collisioni. – infthi

+0

hai ragione, +1 –

1

In genere io uso XOR per il metodo di codice hash.

@Override 
public int hashCode() { 
    return from^to; 
} 
+1

a seconda della dimensione dei numeri, e in particolare di, questo non causa rapidamente overflow? –

+2

@ drone.ah - 1) No. 2) Non importa se lo facesse ... questo è un codice hash non un calcolo significativo. (L'operatore '^' è esclusivo O !!) –

+0

@StephenC Fair point. c'è comunque, ancora il problema che da^a! = a^da cui è un requisito. –

6

Sono state proposte tre soluzioni che "funzionano". (Per lavoro, intendo che soddisfano i requisiti di base di un codice hash ... che input diversi danno risultati diversi ... e soddisfano anche il requisito aggiuntivo di "simmetria" dell'OP.)

Questi sono:

# 1 
    return from^to; 

    # 2 
    return to*to+from*from; 

    # 3 
    int res = 17; 
    res = res * 31 + Math.min(from, to); 
    res = res * 31 + Math.max(from, to); 
    return res; 

Il primo si ha il problema che il campo dell'uscita è delimitata dalla gamma dei valori di ingresso effettivi. Ad esempio, se assumiamo che gli input siano entrambi numeri non negativi pari o inferiori a 2 i e 2 j rispettivamente, l'uscita sarà inferiore o uguale a 2 max (i, j). È probabile che ti dia poca "dispersione" nella tabella hash ... e una maggiore frequenza di collisioni. (C'è anche un problema quando from == to!)

Il secondo e il terzo sono migliore del primo, ma si sono ancora suscettibili di ottenere più collisioni di quanto sia auspicabile che from e to sono piccoli.


Vorrei suggerire un 4 ° alternativa, se è fondamentale che a ridurre al minimo le collisioni per piccoli valori di from e to.

#4 
    int res = Math.max(from, to); 
    res = (res << 16) | (res >>> 16); // exchange top and bottom 16 bits. 
    res = res^Math.min(from, to); 
    return res; 

Questo ha il vantaggio che se from e to sono entrambi nell'intervallo 0..2 -1, si ottiene un codice hash univoco per ciascuna coppia distinta (non ordinato).


1 - non so se questo è il termine tecnico corretto per questo ...

+0

Un piccolo problema con il tuo # 4 è che alcune tabelle hash possono mappare i codici hash da inserire in modo tale da annullare il lavoro che hai fatto separando i valori. Suggerirei di calcolare 'bigprime1 * (da + a) -bigprime2 * min (da, a)'. Non è necessario calcolare sia max che min, poiché sum-max = min. XOR sembra popolare nell'hashing, ma in un linguaggio con una semantica di overflow definita non so se abbia vantaggi significativi rispetto all'aggiunta. – supercat

0

Mi chiedo perché nessuno ha offerto la soluzione migliore di solito: Normalizzare i dati:

Connection(int from, int to) { 
     this.from = Math.min(from, to); 
     this.to = Math.max(from, to); 
} 

Se è impossibile, allora io suggerirei qualcosa come

27644437 * (from+to) + Math.min(from, to) 
  • Utilizzando un moltiplicatore diverso da 31, si evitano collisioni come in this question.
  • Utilizzando un grande moltiplicatore si diffondono meglio i numeri.
  • Utilizzando un moltiplicatore dispari si garantisce che la moltiplicazione sia bidirezionale (cioè, nessuna informazione viene persa).

  • Utilizzando un primo si guadagna nulla, ma tutti lo fanno e non ha alcun svantaggio.

+0

Può anche valere la pena notare che la seconda struttura indicata è biiettiva rispetto a x per tutte le coppie della forma '(x, x)' ed è quasi biettiva per le coppie della forma '(x, x + delta)'. Al contrario, le forme che moltiplicano un valore per 31 e aggiungono l'altro produrranno sempre un risultato che è un multiplo di 32 quando usato con due valori uguali, 64 quando usato con quattro, 128 quando usato con otto, 256 se usato con 16, ecc. – supercat

+0

@supercat '27644437 * x + x = 0x1A5D216 * x' che è sempre uniforme, quindi non può essere bidirezionale. Ma è il meglio che può in quanto non è un multiplo di 4. Ho sempre sostenuto che 31 è un terribile moltiplicatore mentre non pensavo a 'hash (x, x) 'essendo un multiplo di 32. – maaartinus

+0

Finisce fino a 27644437 * (x + x) + x, che è dispari. Per quanto riguarda i meriti di 31, non sarebbe così male se ogni passo calcolasse 31 * prev-x piuttosto che 31 * prev + x. Ovviamente renderebbe hash di ogni valore (x, -x) a un multiplo di 32, ma quelli sono probabilmente molto meno comuni (x, x). Ciò che è veramente orribile è x^y. Che mappa ogni (x, x) a zero, ed è quasi altrettanto cattivo con (x, x + 1), mappando metà di quelli a 1, un quarto a 3, un ottavo a 7, ecc. Ciò che è assurdo è che x + generalmente non è più costoso di x^y, ma le persone hanno qualche strano attaccamento a xor. BTW, 'from + to' potrebbe essere un hash decente. – supercat

Problemi correlati