Controllo delle chiavi in una HashMap

[vincyilbiondo]

Ragazzi ho ancora problemi con un altro esercizio

Dovevo gestire una Biblioteca, utilizzando una struttura dati Mappa, ma non era specificato quale implementazione.

Le possibili scelte erano: LinkedHashMap, TreeMap e HashMap, e ho scelto di provare per prima con la HashMap.

Vi posto soltanto la parte di codice che mi dà problemi.

Questa è la classe Libro, che poi sarà utilizzata come CHIAVE per la mappa:

public class Libro{
	
	private String autore;
	private String titolo;
	
	
	public Libro(String autore, String titolo)
	{
		this.autore=autore;
		this.titolo=titolo;
	}


	public String getAutore() {
		return autore;
	}


	public String getTitolo() {
		return titolo;
	}
	
	public String toString()
	{
		return ("Autore: " + autore + "\n" + "Titolo: " + titolo + "\n");
	}
}

Questa è la classe InfoLibro, che poi verrà usata come VALORE per la mappa:

public class InfoLibro {
	
	private int copieLibro;
	private int copieInPrestito;
	
	
	public InfoLibro (int copieLibro)
	{
		this.copieLibro=copieLibro;
		copieInPrestito=0;
	}


	public int getCopieLibro() {
		return copieLibro;
	}


	public void setCopieLibro(int copieLibro) {
		this.copieLibro = copieLibro;
	}


	public int getCopieInPrestito() {
		return copieInPrestito;
	}


	public void setCopieInPrestito(int copieInPrestito) {
		this.copieInPrestito = copieInPrestito;
	}
	
	
	public String toString()
	{
		return ("Copie Libro: " + copieLibro + "\n" + "Copie in prestito: " + copieInPrestito + "\n");
	}

Questa è la classe Libreria (ho allegato solo una parte del codice), che sarà il mio Buffer condiviso tra Produttore-Consumatore:

import java.util.HashMap;


public class Libreria {

	private HashMap<Libro, InfoLibro> libreria;
	
	
	
	public Libreria ()
	{
		libreria = new HashMap<Libro, InfoLibro>();
	}
	
	
	public void inserisciLibro(Libro l, int copie)
	{
		if (libreria.containsKey(l))   //se il libro è già presente nella libreria
		{
			InfoLibro temp = libreria.get(l);
			temp.setCopieLibro(temp.getCopieLibro() + copie);
		}
		
		else  //libro non presente nella libreria
		{
			libreria.put(l, new InfoLibro(copie));
		}		
	}

Questo è il MainTest_1:

public class TestLibreria {

	
	public static void main(String[] args) {
		
		
		Libreria libreria;		
		
		libreria = new Libreria();
		
		Libro l1, l2, l3;
		
		
		l1 = new Libro("Autore 1", "Titolo 1");
		l2 = new Libro("Autore 2", "Titolo 2");
		l3 = l1;
		
		
		libreria.inserisciLibro(l1, 3);
		libreria.inserisciLibro(l2, 2);
		libreria.inserisciLibro(l1, 10);
		libreria.inserisciLibro(l3, 10);

                System.out.println(libreria.toString());

Questo è MainTest_2:

public class TestLibreria {

	
	public static void main(String[] args) {
		
		
		Libreria libreria;
		
		libreria = new Libreria();
		
		libreria.inserisciLibro(new Libro("Autore 1", "Titolo 1"), 3);
		libreria.inserisciLibro( new Libro("Autore 2", "Titolo 2"), 2);
		libreria.inserisciLibro( new Libro("Autore 1", "Titolo 1"), 10);
		libreria.inserisciLibro( new Libro("Autore 2", "Titolo 2"), 10);
		
		System.out.println(libreria.toString());

Se eseguo il MainTest_1 come output ottengo:

Autore: Prova_Autore 1
Titolo: Prova_Titolo 1
Copie Libro: 23
Copie in prestito: 0

Autore: Prova_Autore 2
Titolo: Prova_Titolo 2
Copie Libro: 2
Copie in prestito: 0

Se eseguo il MainTest_2 come output ottengo:

Autore: Prova_Autore 1
Titolo: Prova_Titolo 1
Copie Libro: 3
Copie in prestito: 0

Autore: Prova_Autore 2
Titolo: Prova_Titolo 2
Copie Libro: 2
Copie in prestito: 0

Autore: Prova_Autore 1
Titolo: Prova_Titolo 1
Copie Libro: 10
Copie in prestito: 0

Autore: Prova_Autore 2
Titolo: Prova_Titolo 2
Copie Libro: 10
Copie in prestito: 0

Praticamente nel test 1 le chiavi uguali vengono riconosciute (cioè i Libri) mentre nel test 2 no; infatti nel test 1 vengono aggiornate le copie dei libri disponibili invece nel test 2 anche se cerco di inserire libri già presenti non vengono riconosciuti come libri già esistenti nella biblioteca e quindi non vengono aggiornati i numeri delle copie ma vengono aggiunti nuovamente nella HashMap come se fossero nuovi libri.

L'unica differenza è che nel test 1 al metodo inserisciLibro della Libreria passiamo un riferimento di un oggetto Libro creato già, mentre nel secondo test passiamo un riferimento di un oggetto Libro creato al momento; quindi anche se creiamo due oggetti con lo stesso Autore e Titolo, essi hanno riferimento diversi.

Quindi ho ipotizzato che la put della HashMap non controlla il contenuto dell'oggetto Libro ma si limita soltanto a confrontare i riferimenti della chiavi.

E' corretta questa ipotesi?
Grazie

[francesco.muia]

Se magari nella tua implementazione di Libro (e anche ad InfoLibro non farebbe male), implementassi il metodo equals e hashcode magari hashMap saprebbe come confrontarli.

[vincyilbiondo]

Grazie al tuo suggerimento ho cercato un po' ed ho trovato questo argomento dei metodi hashcode() e equals().

Quindi se ho capito: se uso la HashMap o la LinkedHashMap devo implementare questi due metodi nella classe della Chiave (ed eventualmente anche nella classe del Valore) in modo da poter confrontare la chiavi, e se non implemento questi due metodi poiché non sà come confrontare le chiavi, mi compara i riferimenti delle chiavi.

Ho provato però lo stesso programma usando una TreeMap, senza implementare i metodi hashcode() e equals() e funziona bene. Forse perchè con la TreeMap si deve fornire un comparatore per effettuare l'inserimento in ordine, e quindi in questo modo vede anche se è presente già la stessa chiave?

Ragazzi siete la mia salvezza

[francesco.muia]

E' corretto quello che dici, fornendo un comparatore il treeMap usa appunto quest'ultimo per effettuare la comparazione degli oggetti.

[andbin]

Originariamente inviato da vincyilbiondo
Quindi se ho capito: se uso la HashMap o la LinkedHashMap devo implementare questi due metodi nella classe della Chiave

Sì.

Originariamente inviato da vincyilbiondo
(ed eventualmente anche nella classe del Valore)

Per HashMap/LinkedHashMap no. Se ti serve implementarli anche per i valori per altri motivi ... ok.

Originariamente inviato da vincyilbiondo
se non implemento questi due metodi poiché non sà come confrontare le chiavi, mi compara i riferimenti delle chiavi.

Sì, restano equals/hashCode di Object che si basano solo sulla "identità" degli oggetti (in pratica sui reference).

Originariamente inviato da vincyilbiondo
Ho provato però lo stesso programma usando una TreeMap, senza implementare i metodi hashcode() e equals() e funziona bene. Forse perchè con la TreeMap si deve fornire un comparatore per effettuare l'inserimento in ordine, e quindi in questo modo vede anche se è presente già la stessa chiave?

TreeMap non è una "hash table". Ma è un albero binario. E l'ordinamento/ricerca delle chiavi si basa su Comparable o Comparator.

[Apicio]

Avrei una domanda un pò strana ed OffTopic, ma visto che se ne è parlato, la butto lì: quando uso equals() ed hashCode(), li faccio SEMPRE generare in automatico da Eclipse. In rete ho cercato, ma ad onore del vero non ho trovato nulla riguardo il "creare" da zero una hashCode(). Quello che chiedo è: faccio e farò sempre bene ad usare quella generata in automatico da Eclipse?

[andbin]

Originariamente inviato da Apicio
In rete ho cercato, ma ad onore del vero non ho trovato nulla riguardo il "creare" da zero una hashCode(). Quello che chiedo è: faccio e farò sempre bene ad usare quella generata in automatico da Eclipse?

Gli equals/hashCode generati da un IDE sono di certo appropriati e validi (a parte bachi, sempre possibili, del IDE chiaramente). Però l'IDE potrebbe essere un po' limitato: nel senso che ad esempio Eclipse mostra una dialog per selezionare i campi ma quei campi selezionati vengono usati sia da equals che da hashCode. Insomma entrambi i metodi usano sempre gli stessi campi se è l'IDE a generarli.

In realtà non è obbligatorio che prendano in considerazione gli stessi campi. Tuttavia esiste una condizione essenziale affinché sia rispettato il contratto: la implementazione di equals deve essere "accurata" (nel senso di quali proprietà considerare) almeno quanto la implementazione di hashCode.


P.S. Se n'era parlato anche in questa discussione.

[Apicio]

Ti ringrazio molto credo che finché non approfondirò l'argomento mi limiterò a lasciarli generare da Eclipse.

[andbin]

- due oggetti equals(uguali) devono avere lo stesso codice hash.

Sì.

- due oggetti con lo stesso hashcode non devono essere equals

No, o perlomeno è detto molto male.
Se due oggetti hanno lo stesso hash code, possono essere O non essere uguali. Non è infatti questo lo scenario importante.

Lo scenario davvero importante e fondamentale è quello detto all'inizio. In più se due oggetti sono "diversi" (per equals() ), allora possono avere o no lo stesso hash code ma se producono hash code differenti allora è meglio e più performante (per le hash-table).

Infine, cosa che non hai citato ma fa parte del "corollario": se due oggetti hanno hash code diversi, allora i due oggetti DEVONO essere diversi per equals().

Se rispetti le suddette regole eviterai il problema delle collisioni

Salvo casi "particolari" (es. Integer contiene un int, il hash code è quel int e quindi sono tutti distinti), difficilmente si possono evitare "collisioni".
L'obiettivo di hashCode() NON è quello di evitare collisioni. Queste ci possono potenzialmente sempre essere e non sono il grosso problema. L'obiettivo è quello di produrre hash code il più possibilmente distinti e ben distribuiti.

[LeleFT]

E anche qui, come nell'altra.


Ciao.