Java Collections – Parte II

Dopo avert visto le liste nella prima parte del tutorial sulle collection java vediamo adesso le interfacce Set e Map e le varie implementazioni disponibili. Vedremo vari esempi pratici di utilizzo di insiemi e mappe di oggetti basati sia su hash table che su strutture ad albero.

Set e Map

Set è una interfaccia che estende Collection e che identifica un insieme di oggetti in cui non possono essere presenti duplicati. Il modo in cui sono confrontati gli oggetti per capire se un oggetto è già presente dipende dall’implementazione. Rispetto a Collection l’interfaccia Set non aggiunge nessun metodo.

Map è una interfaccia che permette di definire una collection di coppie nome-valore in cui l’insieme dei nomi non contiene duplicati. Anche in questo caso il modo in cui sono confrontati gli oggetti dipende dall’implementazione.
I metodi principali sono:

put
per inserire una coppia nome-valore
get
per prendere il valore associato a una chiave

Map non estende l’interfaccia Iterable, per scorrere gli elementi può essere usato uno di questi metodi:

keySet
insieme delle chiavi
values
collezione dei valori
entrySet
insieme delle coppie nome-valore, viene utilizzata la classe Map.Entry

Un esempio di utilizzo di una mappa è il seguente:

public static void testMap(Map<Integer, String> map) {
	map.put(1, "ABC");
	map.put(2, "ABC");
	map.put(3, "DEF");
	map.put(1, "DEF");
	System.out.println(map.size() == 3);
	System.out.println(map.get(1).equals("DEF"));
 
	Set<Integer> keySet = map.keySet();
	System.out.println(keySet.contains(2));
 
	Collection<String> values = map.values();
	System.out.println(values.size() == 3);
 
	Set<Entry<Integer, String>> entrySet = map.entrySet();
	for (Entry<Integer, String> entry : entrySet) {
		System.out.println(entry.getKey() + 
			" --> " + entry.getValue());
	}
}

HashSet e HashMap

HashSet e HashMap sono implementazioni di Set e Map che usano una hash table per memorizzare i dati, i dati contenuti non sono ordinati.
La classe Hashtable è una classe ormai obsoleta (risale al jdk versione 1.0) ed ha le stesse caratteristiche della classe HashMap. L’unica differenza è che Hashtable è sincronizzata e quindi può essere usata in ambiente multithread. Anche se la classe Hashtable non è deprecata non è consigliabile l’utilizzo, nel caso in cui si voglia accedere da più thread in parallelo è possibile ottenere una mappa sincronizzata usando il metodo Collections.synchronizedMap.

Il confronto fra due oggetti viene effettuato utilizzando i metodi hashCode e equals definiti nella classe Object; per questo motivo bisogna fare attenzione quando si scrive una classe che si vuole memorizzare in una collection di questo tipo. Infatti il metodo equals di Object confronta due oggetti usando l’operatore ==, ma quasi sempre questo non è il modo giusto di confrontare due oggetti. Per questo motivo in tutti i casi in cui non voglio sapere se due oggetti sono la stessa istanza (equals di Object) ma voglio definire una condizione di uguaglianza più funzionale è necessario effettuare l’override di equals. Per quanto su detto però i due metodi hashCode e equals devono essere coerenti fra di loro: due oggetti uguali secondo il metodo equals devono avere lo stesso hashCode. Se si utilizza Eclipse come IDE di sviluppo è possibile generare automaticamente i metodi hashCode e equals scegliendo quali campi usare per il confronto. Un esempio è il seguente:

public class Persona {
	private String nome;
	private String cognome;
	private String indirizzo;
 
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + 
			((cognome == null) ? 0 : cognome.hashCode());
		result = prime * result + 
			((nome == null) ? 0 : nome.hashCode());
		return result;
	}
 
	@Override
	public boolean equals(Object obj) {
		if (this == obj) {
			return true;
		}
		if (obj == null) {
			return false;
		}
		if (getClass() != obj.getClass()) {
			return false;
		}
		Persona other = (Persona) obj;
		if (cognome == null) {
			if (other.cognome != null) {
				return false;
			}
		} else if (!cognome.equals(other.cognome)) {
			return false;
		}
		if (nome == null) {
			if (other.nome != null) {
				return false;
			}
		} else if (!nome.equals(other.nome)) {
			return false;
		}
		return true;
	}
}

Utilizzando questa classe in un Set si può notare che inserendo due persone con stesso nome e cognome ma indirizzo diverso viene inserito solo il primo dei due oggetti:

Persona p1 = new Persona("Mario", "Rossi", "Via Firenze 1");
Persona p2 = new Persona("Mario", "Rossi", "Via Roma 2");
Persona p3 = new Persona("Mario", "Bianchi", "Via Milano 3");
Set<Persona> set = new HashSet<Persona>();
set.add(p1);
set.add(p2);
set.add(p3);
System.out.println(set.size() == 2);

Una HashMap serve per associare a un oggetto chiave un oggetto valore. Per esempio può servire per contare il numero di duplicati contenuti in una lista:

List<Persona> l = new ArrayList<Persona>(1000);
Random random = new Random();
for (int i = 0; i < 1000; i++) {
	int r = random.nextInt(100);
	l.add(new Persona("Nome" + r, "Cognome" + r, "Indirizzo" + r));
}
Map<Persona, Integer> map = new HashMap<Persona, Integer>();
for (Persona p : l) {
	Integer numeroOccorrenze = map.get(p);
	if (numeroOccorrenze == null) {
		numeroOccorrenze = 0;
	}
	map.put(p, numeroOccorrenze + 1);
}
Set<Entry<Persona, Integer>> entrySet = map.entrySet();
for (Entry<Persona, Integer> entry : entrySet) {
	Persona persona = entry.getKey();
	Integer numeroOccorrenze = entry.getValue();
	System.out.println(persona.getNome() + " " + persona.getCognome() 
		+ ": " + numeroOccorrenze);
}

Dalla versione 1.4 di Java sono state introdotte le classi LinkedHashSet e LinkedHashMap. Sono logicamente uguali a HashSet e HashMap ma mantegono anche una lista ordinata per tempo di inserimento in modo da ritornare gli elementi ordinati quando si scorrono usando un Iterator.

TreeSet e TreeMap

TreeSet e TreeMap sono due classi concrete che implementano le interfacce Set e Map usando un albero per contenere i dati.

Set<Persona> set = new TreeSet<Persona>();
set.add(new Persona("Mario", "Bianchi", "Via Firenze 1"));
set.add(new Persona("Giorgio", "Rossi", "Via Roma 2"));

La seconda invocazione del metodo add lancia una eccezione (java.lang.ClassCastException: Persona cannot be cast to java.lang.Comparable) in quanto non abbiamo specificato come ordinare i dati; gli oggetti inseriti in un albero sono sempre ordinati. E’ possibile specificare l’ordinamento in due modi:

  • implementando l’interfaccia Comparable;
  • passando un oggetto Comparator al costruttore di TreeSet o TreeMap.

Un esempio di implementazione di Comparable che ordina prima per nome e poi per cognome è la seguente:

public class Persona implements Comparable<Persona> {
	private final String nome;
	private final String cognome;
	private final String indirizzo;
 
	@Override
	public int compareTo(Persona o) {
		int r = nome.compareToIgnoreCase(o.nome);
		if (r == 0) {
			r = cognome.compareToIgnoreCase(o.cognome);
		}
		return r;
	}
	//....
}

Inserendo due oggetti nell’insieme possiamo controllare l’ordine degli elementi ritornati dall’iterator:

Set<Persona> set = new TreeSet<Persona>();
Persona p1 = new Persona("Mario", "Bianchi", "Via Firenze 1");
Persona p2 = new Persona("Giorgio", "Rossi", "Via Roma 2");
set.add(p1);
set.add(p2);
 
Iterator<Persona> iterator = set.iterator();
System.out.println(p2 == iterator.next());
System.out.println(p1 == iterator.next());

Se vogliamo ordinare una collection in base a un ordine diverso da quello specificato nel metodo compareTo o se non vogliamo (o possiamo) modificare la classe possiamo specificare un Comparator. Vediamo un esempio di Comparator che ordina prima per cognome e poi per nome:

public class CognomeComparator implements Comparator<Persona> {
	@Override
	public int compare(Persona p1, Persona p2) {
		int r = p1.getNome().compareTo(p2.getNome());
		if (r == 0) {
			r = p1.getCognome().compareTo(p2.getCognome());
		}
		return r;
	}
}

Rifacendo lo stesso esempio ma passando questa volta al costruttore una istanza di CognomeComparator possiamo vedere che l’ordine degli elementi è invertito:

Set<Persona> set = new TreeSet<Persona>(new CognomeComparator());
Persona p1 = new Persona("Mario", "Bianchi", "Via Firenze 1");
Persona p2 = new Persona("Giorgio", "Rossi", "Via Roma 2");
set.add(p1);
set.add(p2);
 
Iterator<Persona> iterator = set.iterator();
System.out.println(p1 == iterator.next());
System.out.println(p2 == iterator.next());

BitSet

Una classe utile da usare al posto di una Map è BitSet che utilizza un vettore di bit per memorizzare i dati. BitSet contiene anche dei metodi per eseguire operazioni su bit.

BitSet b = new BitSet();
b.set(10);
b.set(100, 200);
b.set(120, 150, false);
System.out.println(b.get(130));

Collections e Arrays

La classe Collections contiene molti metodi statici di utilità per manipolare collezioni di dati; fra gli altri sono presenti i metodi:

  • emptyList, emptySet e emptyMap: ritornano Collection vuote non modificabili;
  • singleton, singletonList e singletonMap: ritornano Collection non modificabili con un solo elemento;
  • sort: ordina una lista;
  • reverse: inverte l’ordine degli elementi in una lista.

La classe Arrays ha alcuni metodi simile a quelli di Collections, ma manipola array e non collezioni; alcuni metodi ultili sono:

  • binarySearch: esegue una ricerca binaria su un array di dati ordinati;
  • sort: ordina un array;
  • asList: converte un array in una lista non modificabile. Accetta un varargs di argomenti e quindi può essere usato per creare in modo semplice una lista:
    List<Integer> l = Arrays.asList(1, 2, 3);

Conclusioni

Finisce qui questo tutorial in due parti sull’utilizzo delle collezioni di oggetti in Java.
Se tutto questo non vi basta potete provare a usare le Commons Collections (sono per jdk 1.4, non usano i generics) o le Google Collections. Queste ultime sono confluite nel progetto Guava, che contiene un superset delle vecchie e deprecate Google Collections Library oltreché una serie di altre librerie di utilità.

  • Cicraf

    vorrei farti una domanda: nei tuoi esempi adoperi il polimorfismo per le interfacce ad esempio:  Set set = new TreeSet();iose io volessi chiamare un metodo implementato dalla classeTreeSet dovrei fare prima un casting giusto?

    • http://twitter.com/fabioCollini Fabio Collini

      Ciao, giustissimo! Usando Set nella dichiarazione della variabile non ti leghi a una specifica implementazione e quindi puoi cambiarla anche successivamente senza problemi (questa cosa è più utile per i parametri dei metodi che non per le variabili locali).
      Se hai bisogno di usare metodi di TreeSet ti conviene definire subito la variabile come TreeSet per evitare di aggiungere il cast.
      Alla fine è una questione di abitudine o di gusti personali, ormai grazie a Eclipse anche prendendo la scelta sbagliata con un po’ di refactoring si corregge tutto!

  • Anonimus

    Ciao,scusami ma come implemento un porg java che ordina gli oggetti di una collezione in base a dei confronti.In particolare testare il prg sulle stringhe contenute in un file in modo che la sequenza ottenuta risulti ordinata rispetto alle lunghezze crescenti e a parità di lunghezza in ordine alfabetico e in ordine alfabetico inverso.implementare tutte le astrazioni necessarie e favorire il riutilizzo del codice.Inoltre nella classe di test effettuare il controllo che il file sia presente nel fyle system prima di procedere all’apertura

    • http://twitter.com/fabioCollini Fabio Collini

      Ciao, per ordinare una lista di oggetti puoi usare il metodo Sort di Collections usando oggetti Comparable o un Comparator. Anche in questo post se ne parla, se lo rileggi puoi ottenere informazioni utili.