Utilizzo di HashTable senza eseguire l'override di hashcode ()

L'idea con HashTable quando provi a recuperare un oggetto è che la struttura dati calcola il codice hash dell'oggetto usando il metodo GetHashCode() e poi passa attraverso un elenco usando il metodo Equals() .

Con l'implementazione predefinita di GetHashCode() , due oggetti perfettamente simili potrebbero finire per produrre diversi codici hash, il che significa che se non usi la stessa identica istanza, non troverai mai il tuo oggetto in HashTable .

In generale, vuoi essere sicuro di due cose quando implementi i codici hash:

• Se A.Equals(B) poi A.GetHashCode()==B.GetHashCode()
• Cerca di ottenere una distribuzione dei codici hash correttamente distribuita per ottenere la massima efficienza dalla tabella hash (se sono disponibili pochi codici hash, finirai per cercare un elenco).

La risposta è "niente di male a meno che tu non abbia sostituito equals() ".

Il punto generale è che se due oggetti sono uguali, ad esempio se

 a.equals(b)

quindi devono avere lo stesso codice hash i.e.

 a.hashCode() == b.hashCode()

anche se due oggetti hanno codici hash diversi, non devono essere uguali.

Questo è particolarmente rilevante quando si mettono oggetti in una tabella hash. Questo perché una tabella hash è una matrice di elenchi (di solito chiamati bucket). Il bucket hash viene indicizzato utilizzando il codice hash, in genere si utilizza hashCode % arraySize .

Quindi quando metti un oggetto nella tabella hash, prendi il codice hash della chiave e lo usi per determinare il bucket. Quindi inserisci una coppia chiave-valore nel bucket. Quando si desidera recuperare un oggetto dalla tabella hash, si prende il codice hash della chiave per trovare il bucket e si prova la chiave di tutte le coppie chiave-valore nel bucket con .equals() per determinare quale oggetto è quello che si volere.

Quindi se hai due oggetti chiave che sono uguali ma hanno codici hash diversi e ne usi uno come chiave in una tabella hash, non sarai in grado di cercarlo usando l'altro oggetto chiave perché sarai guardando nel secchio sbagliato.

L'implementazione di equals() in Object restituisce true solo se i due oggetti sono effettivamente lo stesso oggetto e hashCode() restituisce il riferimento all'oggetto. Tuttavia, se esegui l'override di equals() (ad esempio, String fa in modo che le stringhe diverse che contengono la stessa sequenza di caratteri siano uguali), devi sostituire hashCode()

What's gonna happen if we do not override hashcode method for our class, then add it to HashTable and then try to get objects?

Dipende da cosa significa "aggiungere a HashTable". Java Hashtable non ha alcun metodo add . L'intervistatore probabilmente intendeva il metodo put , che contiene un tasto e un valore . Il valore può essere qualsiasi cosa (potrebbe essere pari a null in HashMap, che è la versione attuale di Hashtable). Non accade nulla di speciale indipendentemente dal fatto che abbiate o meno sostituito l'hashcode dell'oggetto value o qualsiasi altro metodo.

Probabilmente l'intervistatore voleva dire che l'hashcode dell'oggetto chiave non sarebbe stato sovrascritto. Solo allora i problemi di identità dell'oggetto, come indicato in altre risposte, entrano in gioco. Anche in questo caso, non è necessario sovrascrivere l'hashcode della chiave. Ad esempio, se utilizzi String s come chiavi, hanno già un'implementazione hashcode appropriata in esse. Inoltre, non possono essere sottoclassi. Inoltre, se fai sostituisci hashcode ma non sovrascrive equals, potresti ottenere un comportamento sorprendente ...

Se la domanda fosse davvero esattamente ciò che hai scritto, avrei stuzzicato l'intervistatore con queste domande. Un buon programmatore non presume che l'intervistatore abbia probabilmente inteso questo o quello. Chiede invece.

non troverai il tuo oggetto se ottieni un oggetto diverso che è equal sull'oggetto che hai messo

o per dare un esempio:

MyClass obj1 = new MyClass(1);
MyClass obj2 = new MyClass(1);
assert obj1.equals(obj2);
assert obj1.hashcode()!=obj2.hashcode(); //this is wat happens if you don't inclde hashcode
table.put(obj1,2);
table.get(obj2) // will likely return null but that is a gamble
table.get(obj1) // but this will return the object passed in

la ragione di ciò è che HashTable (e HashMap) useranno l'hashcode per limitare lo spazio che deve cercare per trovare l'oggetto e che si basa sul presupposto che se obj1.equals(obj2) e obj1.hashcode == obj2.hashcode()

Vorrei solo aggiungere che tutti questi concetti devono avere identità e confronto .

C'è un contratto con il codice hash:

1.) Ogni volta che viene invocato sullo stesso oggetto 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 uguali sull'oggetto. Questo numero intero non deve rimanere coerente da un'esecuzione di un'applicazione a un'altra esecuzione della stessa applicazione.

2.) Se due oggetti sono uguali secondo il metodo equals (Object), allora chiamare il metodo hashCode su ciascuno dei due oggetti deve produrre lo stesso risultato intero.

3.) Non è necessario che se due oggetti non sono uguali secondo il metodo equals (java.lang.Object), allora chiamare il metodo hashCode su ciascuno dei due oggetti deve produrre risultati interi distinti. Tuttavia, il programmatore dovrebbe essere consapevole del fatto che produrre risultati interi distinti per oggetti non uguali può migliorare le prestazioni degli hashtables.

Il risultato è che se i codici hash sono uguali, le voci nella tabella si sovrascrivono e questo potrebbe sorprendere per alcuni ...

Spero che questo aiuti.

La risposta è: oggetti simili (tutti i campi con uguali valori) non creerebbero lo stesso codice hash, quindi avresti bisogno esattamente dello stesso (identico) oggetto che è stato usato per put per recuperare da hashtable, che non è fattibile nella maggior parte dei casi.

Supponendo che la tua classe estenda solo Object , l'implementazione di hashCode() della tua classe dipenderà dall'identità di oggetto . Cioè che il codice hash di due istanze diverse sarà (quasi certamente) diverso, anche se hanno lo stesso identico valore.

Questo significa che molto probabilmente non troverai più l'oggetto nella Mappa (puoi trovarlo per caso, comunque).

Se il metodo hashcode non è sovrascritto, la risposta a questa domanda dipende molto se lo stesso oggetto chiave utilizzato a "put" verrà utilizzato anche per "get" :

a) Se viene utilizzato lo stesso oggetto chiave - "get" troverà il valore. Perché localizzerà il bucket usando lo stesso "key" e quindi troverà il valore oggetto.

b) Se viene utilizzato un altro oggetto chiave "equivelente" - Dal momento che probabilmente l'hashcode sarà diverso a causa dell'implementazione predefinita del metodo hashcode in Object e quindi potrebbe entrare in un bucket diverso e potrebbe non essere in grado di ottenere il valore dell'oggetto.