Come assicurarsi che hashCode () sia coerente con equals ()?

Quando si esegue l’override della funzione equals () di java.lang.Object, i javadoc 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 stabilisce che gli oggetti uguali devono avere uguali codici hash.

Il metodo hashCode () deve restituire un numero intero univoco per ogni object (questo è facile da fare quando si confrontano gli oggetti in base alla posizione della memoria, è sufficiente restituire l’indirizzo intero univoco dell’object)

Come dovrebbe essere sovrascritto un metodo hashCode () in modo che restituisca un intero univoco per ogni object basato solo sulle proprietà dell’object?

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? } } 

Non dice che l’hashcode per un object deve essere completamente unico, solo che l’hashcode per due oggetti uguali restituisce lo stesso codice hash. È del tutto legale che due oggetti non uguali restituiscano lo stesso codice hash. Tuttavia, più esclusiva è la distribuzione di un hashcode rispetto a un insieme di oggetti, migliori saranno le prestazioni di HashMaps e di altre operazioni che utilizzano hashCode.

Gli IDE come IntelliJ Idea hanno generatori incorporati per equals e hashCode che generalmente fanno un buon lavoro ottenendo codice “abbastanza buono” per la maggior parte degli oggetti (e probabilmente meglio di alcune funzioni hash troppo intelligenti fatte a mano).

Ad esempio, ecco una funzione hashCode che Idea genera per la tua class People:

 public int hashCode() { int result = name != null ? name.hashCode() : 0; result = 31 * result + age; return result; } 

Non entrerò nei dettagli dell’unicità di hashCode come Marc ha già affrontato. Per la tua class People , devi prima decidere che cosa significhi l’uguaglianza di una persona. Forse l’uguaglianza si basa esclusivamente sul loro nome, forse si basa sul nome e sull’età. Sarà specifico per il dominio. Diciamo che l’uguaglianza è basata sul nome e sull’età. I tuoi equals forzati sembrerebbero

 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 hashCode override è necessario eseguire l’override di hashCode . Inoltre, hashCode non può usare più campi nel suo calcolo rispetto a quelli equals . La maggior parte delle volte è necessario aggiungere o esclusivo o il codice hash dei vari campi (hashCode dovrebbe essere veloce da calcolare). Quindi un metodo di hashCode valido potrebbe essere simile a:

 public int hashCode() { return (name==null ? 17 : name.hashCode()) ^ age; } 

Si noti che quanto segue non è valido in quanto utilizza un campo equals non (altezza). In questo caso due oggetti “uguali” potrebbero avere un diverso codice hash.

 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 codici hash sono 30. Sebbene valido, ciò non è auspicabile per le prestazioni nelle raccolte basate su hash.

Un’altra domanda chiede se ci siano alcune cose basilari di basso livello che tutti i programmatori dovrebbero conoscere, e penso che le ricerche di hash siano una di quelle. Quindi ecco qui.

Una tabella di hash (si noti che non sto usando un vero nome di class) è fondamentalmente una serie di liste collegate. Per trovare qualcosa nella tabella, devi prima calcolare l’hashcode di quel qualcosa, quindi modarlo in base alla dimensione della tabella. Questo è un indice nell’array, e ottieni un elenco collegato a quell’indice. Attraverserai quindi la lista fino a trovare il tuo object.

Poiché il recupero dell’array è O (1) e l’attraversamento dell’elenco collegato è O (n), si desidera una funzione di hash che crei una distribuzione il più casuale ansible, in modo che gli oggetti vengano sottoposti a hash in elenchi diversi. Ogni object può restituire il valore 0 come hashcode e una tabella hash funzionerà ancora, ma sarebbe essenzialmente una lunga lista collegata all’elemento 0 dell’array.

Inoltre, si desidera che l’array sia di grandi dimensioni, il che aumenta le probabilità che l’object si trovi in ​​un elenco di lunghezza 1. Java HashMap, ad esempio, aumenta la dimensione dell’array quando il numero di voci nella mappa è> 75 % della dimensione dell’array. C’è un compromesso qui: si può avere un enorme array con pochissime voci e sprechi di memoria, o un array più piccolo dove ogni elemento dell’array è un elenco con> 1 voci, e sprecare tempo attraversando. Un hash perfetto assegnerebbe ogni object a una posizione unica nell’array, senza spazio sprecato.

Il termine “hash perfetto” è un termine reale e in alcuni casi è ansible creare una funzione hash che fornisce un numero univoco per ciascun object. Questo è ansible solo quando conosci l’insieme di tutti i valori possibili. Nel caso generale, non è ansible ottenere questo e ci saranno alcuni valori che restituiscono lo stesso codice hash. Questa è una semplice matematica: se hai una stringa lunga più di 4 byte, non puoi creare un codice hash univoco a 4 byte.

Un aspetto interessante: gli array di hash sono generalmente dimensionati in base ai numeri primi, per dare la migliore possibilità di allocazione casuale quando modi i risultati, indipendentemente da come siano realmente casuali gli hashcode.

Modifica in base ai commenti:

1) Un elenco collegato non è l’unico modo per rappresentare gli oggetti che hanno lo stesso codice hash, sebbene questo sia il metodo usato da JDK 1.5 HashMap. Sebbene sia meno efficiente in termini di memoria rispetto a un semplice array, è probabile che crei 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 class HashMap utilizza una matrice dimensionata come potenza di 2; prima usava 2 ^ N + 1, che credo sia primo per N <= 32. Questo non accelera l'indicizzazione degli array di per sé, ma permette che l'indice dell'array sia calcolato con un AND bit a bit piuttosto che una divisione, come notato da Neil Coffey. Personalmente, lo metterei in discussione come un'ottica prematura, ma dato l'elenco degli autori su HashMap, presumo che ci siano dei veri benefici.

In generale il codice hash non può essere univoco, poiché ci sono più valori di possibili codici hash (interi). Un buon codice hash distribuisce bene i valori sopra gli interi. Un cattivo potrebbe sempre dare lo stesso valore ed essere sempre logicamente corretto, porterebbe solo a tabelle hash inaccettabilmente inefficienti.

I valori uguali devono avere lo stesso valore di hash per il corretto funzionamento delle tabelle hash. Altrimenti potresti aggiungere una chiave a una tabella hash, quindi provare a cercarla con lo stesso valore con un diverso codice hash e non trovarla. Oppure potresti mettere un valore uguale con un diverso codice hash e avere due valori uguali in posti diversi nella tabella hash.

In pratica, di solito si seleziona un sottoinsieme dei campi da prendere in considerazione sia nel metodo hashCode () sia nel metodo equals ().

Penso che tu l’abbia frainteso. L’hashcode non deve essere univoco per ogni object (dopotutto, è 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 collezioni standard non funzionerebbero (per esempio, si cercherebbe qualcosa nel set di hash ma non lo troverà).

Per gli attributi semplici, alcuni IDE hanno builder di funzioni hashcode.

Se non si utilizzano IDE, prendere in considerazione l’utilizzo di Apahce Commons e della class 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 restituire 0 per tutti i valori è valido, sebbene non efficiente.

Si può verificare se hashCode è consistente tramite un test unitario. Ho scritto una class astratta chiamata EqualityTestCase , che esegue una manciata di controlli hashCode. È sufficiente estendere il caso di test e implementare due o tre metodi di produzione. Il test fa un lavoro molto crudo 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 sullo stesso object più di una volta durante l’esecuzione di un’applicazione Java, il metodo hashCode deve restituire costantemente lo stesso numero intero, a condizione che non vengano modificate le informazioni utilizzate nei confronti degli uguali sull’object. Questo numero intero non deve rimanere coerente da un’esecuzione di un’applicazione a un’altra esecuzione della stessa applicazione.

Esiste una nozione di chiave aziendale, che determina l’univocità delle istanze separate dello stesso tipo. Ogni specifico tipo (class) che modella un’entity framework separata dal dominio di destinazione (ad esempio veicolo in un sistema di flotta) dovrebbe avere una chiave aziendale, che è rappresentata da uno o più campi di class. Metodi equals () e hasCode () dovrebbero essere entrambi implementati utilizzando i campi, che costituiscono una chiave aziendale. Ciò garantisce che entrambi i metodi siano coerenti tra loro.