Hashtable e override di equals() e hasCode()

[Donovant]

Riprto qui quello che stavo scrivendo in un altro thread, in cui questo era un po' OT.

"adbin":

tra equals() e hashCode() esiste un "contratto" ben preciso (la documentazione di Object lo spiega, anche se solo a parole). E se si fa l'override di equals() allora va fatto anche l'override di hashCode() in modo coerente con il contratto.

"adbin":

Una tabella hash generalmente è implementata come una lista di bucket, tutti gli oggetti con lo stesso hash code vanno a finire nello stesso bucket. In ogni bucket c'è una lista di entry (chiave+valore) che deve essere scandita per trovare la chiave.

"adbin":

Molto semplice:
Se due oggetti sono uguali secondo equals() allora i loro hash code devono essere uguali. Questa è la regola fondamentale e più importante...

Citato ivi scritto, mi piacerebbe sapere come fare l'override di equals() e hashCode(), se (come nell'altro topic) utilizzo una Hashtable<Integer, String> ht ???

equals(); lascio quella di String, quindi va bene ht.get(k1).equals(ht.get(k2) )
ma per hashCode(); ???....cioè non capisco come fare a far si che se k1 e k2 siano 2 stringhe uguali, questo "contratto" possa andare anche per hashCode...

[andbin]

Originariamente inviato da Donovant
Citato ivi scritto, mi piacerebbe sapere come fare l'override di equals() e hashCode(), se (come nell'altro topic) utilizzo una Hashtable<Integer, String> ht ???

Non devi fare un bel niente. Per una Map è importante che le chiavi rispettino questo contratto. E Integer (le tue chiavi) implementa già correttamente sia equals() che hashCode(), rispettando il contratto.

Originariamente inviato da Donovant
equals(); lascio quella di String, quindi va bene ht.get(k1).equals(ht.get(k2) )
ma per hashCode(); ???....cioè non capisco come fare a far si che se k1 e k2 siano 2 stringhe uguali, questo "contratto" possa andare anche per hashCode...

Sinceramente non ho capito la tua necessità o il tuo dubbio ..... E' quando definisci una "tua" classe che se fai l'override di equals() dovresti fare l'override anche di hashCode() rispettando il contratto. E questo sopratutto se oggetti di questa tua classe sono usati come chiavi in una Map.

Vuoi un esempio di violazione "palese" del contratto?? Faccio una classe Persona con 3 proprietà: nome, cognome e annoNascita (int).
Per implementare equals() vado a confrontare solo nome e cognome dei 2 oggetti. Per implementare hashCode() vado ad usare tutte le 3 proprietà.

Ma immagina 2 oggetti con questo stato:
Mario Rossi 1947
Mario Rossi 1985

I due oggetti sono uguali secondo equals() ma ..... quasi certamente i due hashcode sono differenti!!! (dipende comunque dalla implementazione di hashCode() ma se uno la fa in modo logico sono sicuramente diversi).

La regola è che equals() deve essere "accurato" (in termini dei campi presi in considerazione) almeno quanto hashCode(). Per dirla in altro modo: tutti i campi presi in considerazione da hashCode() devono anche essere presi in considerazione da equals().

[Donovant]

Capito....quindi se 2 valori di una Hashtable sono uguali, il loro hashCode differisce per la chiave??? visto che cmq se metto 2 stringhe di stesso valore ottengo hashcode differenti in hashtable.

[andbin]

Originariamente inviato da Donovant
quindi se 2 valori di una Hashtable sono uguali, il loro hashCode differisce per la chiave??? visto che cmq se metto 2 stringhe di stesso valore ottengo hashcode differenti in hashtable.

Non c'è alcuna relazione particolare tra una chiave di una Map e il valore associato!!! Cioè è proprio solo una associazione nel senso: ad una chiave è associato un valore. Ma la cosa finisce qui. Non esiste alcuna altra relazione/contratto.

Quindi continuo a non capire la tua questione ... o il tuo dubbio.

[Donovant]

Questo lo avevo capito...ma siccome k1 String1 e k2 String hanno 2 hashcode diversi, l'unica mia spiegazione è che si utilizza nel calcolo "forse" anche la kiave....boh.

Non riesco a capire il fatto che tu dici che chiavi diverse con stessa STRINGA abbiano hashcode uguali, mentre a me non risulta quando stampo con System.out....

[andbin]

Originariamente inviato da Donovant
ma siccome k1 String1 e k2 String hanno 2 hashcode diversi

Non riesco a capire il fatto che tu dici che chiavi diverse con stessa STRINGA abbiano hashcode uguali

No ... non ci siamo.

In una Map basata su una "tabella hash" (precisazione importante ... non l'ho fatta prima) è fondamentale che gli oggetti delle chiavi rispettino il contratto tra equals() e hashCode(). Fin qui probabilmente l'hai capito.

Se questo contratto viene rispettato, non è possibile che in una Map ci siano 2 chiavi uguali. È possibile che due chiavi diverse abbiano lo stesso hashcode. Questo sì. Ma non è un problema. Perché comunque la Map per cercare una chiave prima usa hashCode() per individuare il "bucket" e poi scansiona la lista linkata sotto il bucket usando equals() su tutte le chiavi nella lista finché non trova la chiave uguale a quella cercata.

Se due chiavi diverse hanno lo stesso hashcode ... beh, andranno a finire sotto il medesimo bucket. Ma tanto sono diverse, motivo per cui appunto possono coesistere.

Ti è più chiaro adesso?

[Donovant]

Oh ora perfetto....quindi stesso hashcode stesso buket e poi da li scansiona con equals...certo certo, ora è chiarissimo.
Grazie.