Come assicurarsi che hashCode () sia coerente con equals ()?
https://stackoverflow.com/questions/410236
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Quando si sovrascrive la funzione equals () di java.lang.Object, i javadocs suggeriscono che,
è generalmente necessario sovrascrivere il metodo hashCode ogni volta che questo metodo viene sovrascritto, in modo da mantenere il contratto generale per il metodo hashCode, che afferma che oggetti uguali devono avere codici hash uguali.
Il metodo hashCode () deve restituire un numero intero univoco per ogni oggetto (questo è facile da fare quando si confrontano oggetti in base alla posizione della memoria, è sufficiente restituire l'indirizzo numero intero univoco dell'oggetto)
Come deve essere ignorato un metodo hashCode () in modo che restituisca un numero intero univoco per ciascun oggetto basato solo sulle proprietà di quell'oggetto?
public class People{
public String name;
public int age;
public int hashCode(){
// How to get a unique integer based on name and age?
}
}
/*******************************/
public class App{
public static void main( String args[] ){
People mike = new People();
People melissa = new People();
mike.name = "mike";
mike.age = 23;
melissa.name = "melissa";
melissa.age = 24;
System.out.println( mike.hasCode() ); // output?
System.out.println( melissa.hashCode(); // output?
}
}
Soluzione
Non dice che l'hashcode per un oggetto debba essere completamente unico, solo che l'hashcode per due oggetti uguali restituisce lo stesso hashcode. È assolutamente legale che due oggetti non uguali restituiscano lo stesso hashcode. Tuttavia, più una distribuzione hashcode è unica su un insieme di oggetti, migliori sono le prestazioni che otterrai da HashMaps e altre operazioni che utilizzano hashCode.
Gli IDE come IntelliJ Idea hanno generatori integrati per uguali e hashCode che generalmente fanno un buon lavoro nel trovare " abbastanza buono " codice per la maggior parte degli oggetti (e probabilmente migliore di alcune funzioni hash troppo intelligenti create a mano).
Ad esempio, ecco una funzione hashCode che Idea genera per la tua classe People:
public int hashCode() {
int result = name != null ? name.hashCode() : 0;
result = 31 * result + age;
return result;
}
Altri suggerimenti
Non entrerò nei dettagli dell'unicità di hashCode come Marc ha già affrontato. Per la tua classe People, devi prima decidere cosa significa uguaglianza di una persona. Forse l'uguaglianza si basa esclusivamente sul loro nome, forse si basa sul nome e sull'età. Sarà specifico del dominio. Diciamo che l'uguaglianza si basa sul nome e sull'età. Il tuo equals sovrascritto sembrerebbe
public boolean equals(Object obj) {
if (this==obj) return true;
if (obj==null) return false;
if (!(getClass().equals(obj.getClass())) return false;
Person other = (Person)obj;
return (name==null ? other.name==null : name.equals(other.name)) &&
age==other.age;
}
Ogni volta che si esegue l'override hashCode è necessario eseguire l'override <=>. Inoltre, <=> non può usare più campi nel suo calcolo rispetto a <=>. Il più delle volte è necessario aggiungere o esclusivo o il codice hash dei vari campi (hashCode dovrebbe essere veloce da calcolare). Quindi un metodo <=> valido potrebbe apparire come:
public int hashCode() {
return (name==null ? 17 : name.hashCode()) ^ age;
}
Nota che quanto segue non è non valido poiché utilizza un campo che <=> non ha (altezza). In questo caso due & Quot; equivale a & Quot; gli oggetti potrebbero avere un codice hash diverso.
public int hashCode() {
return (name==null ? 17 : name.hashCode()) ^ age ^ height;
}
Inoltre, è perfettamente valido per due oggetti non uguali avere lo stesso codice hash:
public int hashCode() {
return age;
}
In questo caso Jane 30 anni non è uguale a Bob 30 anni, ma entrambi i loro codici hash sono 30. Se valido, ciò non è auspicabile per le prestazioni in raccolte basate su hash.
Un'altra domanda si pone se ci sono alcune cose di base di basso livello che tutti i programmatori dovrebbero sapere, e penso che le ricerche di hash siano una di queste. Quindi ecco qui.
Una tabella hash (nota che non sto usando un vero nome di classe) è fondamentalmente una matrice di elenchi collegati. Per trovare qualcosa nella tabella, prima devi calcolare l'hashcode di quel qualcosa, quindi modificarlo in base alla dimensione della tabella. Questo è un indice nell'array e si ottiene un elenco collegato a quell'indice. Attraversi quindi l'elenco fino a trovare l'oggetto.
Poiché il recupero dell'array è O (1) e l'attraversamento dell'elenco collegato è O (n), si desidera una funzione hash che crei una distribuzione il più casuale possibile, in modo che gli oggetti vengano sottoposti a hash in elenchi diversi. Ogni oggetto potrebbe restituire il valore 0 come hashcode e una tabella hash funzionerebbe comunque, ma sarebbe essenzialmente una lunga lista collegata all'elemento 0 dell'array.
In genere si desidera anche che l'array sia di grandi dimensioni, il che aumenta le probabilità che l'oggetto sia in un elenco di lunghezza 1. Java HashMap, ad esempio, aumenta la dimensione dell'array quando il numero di voci nella mappa è > 75% delle dimensioni dell'array. C'è un compromesso qui: puoi avere un array enorme con pochissime voci e sprecare memoria, o un array più piccolo in cui ogni elemento dell'array è un elenco con & Gt; 1 ingresso e traversata del tempo perso. Un hash perfetto assegnerebbe ogni oggetto a una posizione unica nell'array, senza spazio sprecato.
Il termine " hash perfetto " è un termine reale e in alcuni casi è possibile creare una funzione hash che fornisce un numero univoco per ciascun oggetto. Questo è possibile solo quando si conosce l'insieme di tutti i possibili valori. Nel caso generale, non è possibile raggiungere questo obiettivo e ci saranno alcuni valori che restituiscono lo stesso hashcode. Questa è matematica semplice: se hai una stringa lunga più di 4 byte, non puoi creare un hashcode univoco a 4 byte.
Una curiosità interessante: gli array di hash sono generalmente dimensionati in base ai numeri primi, per offrire le migliori possibilità di allocazione casuale quando modifichi i risultati, indipendentemente da quanto casuali siano gli hashcode.
Modifica in base ai commenti:
1) Un elenco collegato non è l'unico modo per rappresentare gli oggetti che hanno lo stesso hashcode, anche se questo è il metodo utilizzato da HashMap 1.5 JDK. Sebbene meno efficiente in termini di memoria rispetto a un semplice array, crea probabilmente meno churn durante il rehashing (poiché le voci possono essere scollegate da un bucket e ricollegate a un altro).
2) A partire da JDK 1.4, la classe HashMap utilizza un array dimensionato come potenza di 2; prima di ciò usava 2 ^ N + 1, che credo sia primo per N < = 32. Questo non accelera l'indicizzazione dell'array di per sé, ma consente di calcolare l'indice dell'array con un bit bit AND di una divisione, come notato da Neil Coffey. Personalmente, lo metterei in dubbio come ottimizzazione prematura, ma dato l'elenco degli autori su HashMap, suppongo che ci sia un vero vantaggio.
In generale il codice hash non può essere univoco, in quanto vi sono più valori dei possibili codici hash (numeri interi). Un buon codice hash distribuisce i valori sugli interi. Un cattivo potrebbe sempre dare lo stesso valore ed essere ancora logicamente corretto, porterebbe solo a tabelle hash inaccettabilmente inefficienti.
I valori uguali devono avere lo stesso valore hash affinché le tabelle hash funzionino correttamente. Altrimenti potresti aggiungere una chiave a una tabella hash, quindi provare a cercarla con un valore uguale con un codice hash diverso e non trovarla. Oppure potresti inserire un valore uguale con un codice hash diverso e avere due valori uguali in punti diversi nella tabella hash.
In pratica di solito si seleziona un sottoinsieme dei campi da prendere in considerazione sia nel metodo hashCode () che nel metodo equals ().
Penso che tu l'abbia frainteso. L'hashcode non deve essere univoco per ogni oggetto (dopo tutto, è un codice hash) anche se ovviamente non vuoi che sia identico per tutti gli oggetti. Tuttavia, è necessario che sia identico a tutti gli oggetti uguali, altrimenti cose come le raccolte standard non funzionerebbero (ad esempio, si cercherebbe qualcosa nel set di hash ma non lo si troverebbe).
Per attributi semplici, alcuni IDE hanno costruttori di funzioni hashcode.
Se non usi gli IDE, considera l'utilizzo di Apahce Commons e della classe HashCodeBuilder
L'unico obbligo contrattuale per hashCode è che sia coerente . I campi utilizzati nella creazione del valore hashCode devono essere uguali o un sottoinsieme dei campi utilizzati nel metodo equals. Ciò significa che la restituzione di 0 per tutti i valori è valida, sebbene non efficiente.
Si può verificare se hashCode è coerente tramite un test unitario. Ho scritto una classe astratta chiamata EqualityTestCase , che esegue una manciata di controlli hashCode. Uno deve semplicemente estendere il test case e implementare due o tre metodi di fabbrica. Il test fa un lavoro molto grezzo di test se l'hashCode è efficiente.
Questo è ciò che la documentazione ci dice come per il metodo del codice hash
@ javadoc
Ogni volta che viene invocato lo stesso oggetto più di una volta durante un'esecuzione di un'applicazione Java, il metodo hashCode deve essere coerente restituisce lo stesso numero intero, a condizione che no informazioni utilizzate in confronti uguali sull'oggetto viene modificato. Questo intero non deve rimanere coerente da una esecuzione di un'applicazione a un'altra esecuzione della stessa applicazione.
Esiste una nozione di chiave aziendale, che determina l'unicità di istanze separate dello stesso tipo. Ogni tipo specifico (classe) che modella un'entità separata dal dominio di destinazione (ad esempio un veicolo in un sistema di flotte) dovrebbe avere una chiave aziendale, che è rappresentata da uno o più campi di classe. I metodi equals () e hasCode () devono entrambi essere implementati utilizzando i campi, che costituiscono una chiave aziendale. Ciò garantisce che entrambi i metodi siano coerenti tra loro.
