Marco Faella » 15.La libreria Java Collection Framework: la classe HashSet e le liste

La classe HashSet

HashSet è un Set realizzato internamente come tabella hash.
Utilizza il metodo hashCode della classe Object per selezionare il bucket in cui posizionare un elemento.
Per ulteriori dettagli sulle tabelle hash, si consulti un testo di algoritmi e strutture dati.

I principali metodi di HashSet hanno la seguente complessità media:

size      O(1)
isEmpty      O(1)
add      O(1)
contains      O(1)
remove      O(1)

Tuttavia, le prestazioni reali dipendono dalla bontà della funzione hash utilizzata.

Coerenza tra equals ed hashCode

Come previsto dall’interfaccia Set, HashSet utilizza il metodo equals per identificare gli elementi.
Quindi, equals ed hashCode devo rispettare la seguente regola di coerenza.
Per ogni coppia di elementi x ed y

se x.equals(y) è vero allora x.hashCode() == y.hashCode()

Si noti che le versioni di equals ed hashCode presenti in Object rispettano tale regola.
Infatti, se x.equals(y) è vero, allora x ed y puntano al medesimo oggetto, e quindi x ed y hanno lo stesso hashCode.

Coerenza tra equals ed hashCode (segue)

Esaminiamo il caso di una classe che non rispetta la regola di coerenza tra equals ed hashCode.
Supponiamo che una classe Employee ridefinisca equals in modo che confronti il nome degli impiegati, ma non ridefinisca hashCode di conseguenza.
Dati due oggetti Employee x ed y con lo stesso nome, essi risulteranno uguali secondo equals, ma avranno codici hash diversi.

Se inseriamo l’oggetto x in un HashSet:

Set s = new HashSet<Employee>();
s.add(x);

una successiva chiamata a s.contains(y) potrebbe restituire “false”!

Infatti, il codice hash di y potrebbe indurre la struttura dati a cercare l’oggetto in questione in un bucket diverso da quello in cui è stato inserito x.

Ridefinizione di hashCode

Perché HashSet funzioni in maniera efficiente, ed in particolare perché le operazioni principali abbiano complessità costante, è necessario che la classe componente (cioè, la classe degli elementi contenuti) disponga di un opportuno metodo hashCode.
Senza entrare nel dettaglio della teoria delle funzioni di hash, è importante che il metodo hashCode assegni ad ogni oggetto un numero intero il più possibile uniformemente distribuito.

Ad esempio, supponiamo che la classe Employee disponga dei campi name (String) e salary (int), e che siano considerati uguali gli impiegati che hanno questi due campi uguali.
Il metodo hashCode dovrebbe restituire un intero derivato dai valori dei due campi.
Per i tipi non numerici, come le stringhe, conviene partire dal loro codice hash.
Poi, si devono combinare gli interi ottenuti dai vari campi in un unico numero, che verrà restituito.
Un modo comune di combinare due interi, senza correre il rischio di andare in overflow, è rappresentato dall’or esclusivo (XOR) bit a bit, eseguito in Java dall’operatore “^”.
Quindi, per l’esempio in questione, si potrebbe procedere come segue:

public int hashCode(){
return name.hashCode() ^ salary;
}

Mutabilità degli elementi

Un altro problema che affligge sia TreeSet che HashSet riguarda la mutabilità degli elementi.
Gli elementi vengono inseriti in queste strutture dati in base al valore dei loro campi:

• Un TreeSet posiziona gli elementi sulla base di confronti con altri oggetti;
• Un HashSet li posiziona sulla base del loro codice hash.

Se un elemento viene modificato dopo essere stato inserito in una di queste strutture dati, il posizionamento di quell’elemento non corrisponderà più al valore dei suoi campi.
In questo caso, la struttura dati si comporterà in modo inatteso.

Ad esempio, supponiamo che la classe Employee ridefinisca sia equals sia hashCode, in modo che operino sulla stringa che rappresenta il nome dell’impiegato.
Inseriamo l’impiegato x in un HashSet:

Set s = new HashSet<Employee>();
Employee x = new Employee("Mario");
s.add(x);

se il nome di x viene modificato:
x.setName("Luigi");
una successiva chiamata a s.contains(x) potrebbe restituire “false”!

Esercizio (esame 19/2/2009)

Si implementi la classe Container, che rappresenta un contenitore per liquidi di dimensione fissata.
Ad un contenitore, inizialmente vuoto, si può aggiungere acqua con il metodo addWater, che prende come argomento il numero di litri.
Il metodo getAmount restituisce la quantità d’acqua presente nel contenitore.
Il metodo connect prende come argomento un altro contenitore, e lo collega a questo con un tubo. Dopo il collegamento, la quantità d’acqua nei due contenitori (e in tutti quelli ad essi collegati) sarà la stessa.

Esempio d’uso (l’output è sulla slide successiva):

Container a=new Container(), b=new Container(), c=new Container(), d=new Container();

a.addWater(12);
d.addWater(8);
a.connect(b);
System.out.println(a.getAmount()+" "+b.getAmount()+" "+c.getAmount()+" "+d.getAmount());
b.connect(c);
System.out.println(a.getAmount()+" "+b.getAmount()+" "+c.getAmount()+" "+d.getAmount());
c.connect(d);
System.out.println(a.getAmount()+" "+b.getAmount()+" "+c.getAmount()+" "+d.getAmount());

Esercizio (esame 19/2/2009) (segue)

Output dell’esempio d’uso:

6.0 6.0 0.0 8.0
4.0 4.0 4.0 8.0
5.0 5.0 5.0 5.0

La classe ArrayList

ArrayList è un’implementazione di List, realizzata internamente con un array di dimensione dinamica.
Ovvero, quando l’array sottostante è pieno, esso viene riallocato con una dimensione maggiore, e i vecchi dati vengono copiati nel nuovo array:

• questa operazione avviene in modo trasparente per l’utente;
• il metodo size restituisce il numero di elementi effettivamente presenti nella lista, non la dimensione dell’array sottostante.

Il ridimensionamento avviene in modo che l’operazione di inserimento (add) abbia complessità ammortizzata costante:

• per ulteriori informazioni sulla complessità ammortizzata, si consulti un testo di algoritmi e strutture dati.

Le liste e l’accesso posizionale

L’accesso posizionale (metodi get e set) si comporta in maniera molto diversa in LinkedList rispetto ad ArrayList.
In LinkedList, ciascuna operazione di accesso posizionale può richiedere un tempo proporzionale alla lunghezza della lista:

• difatti, per accedere all’elemento di posto n è necessario scorrere la lista, a partire dalla testa, o dalla coda, fino a raggiungere la posizione desiderata.

In ArrayList, ogni operazione di accesso posizionale richiede tempo costante.

Pertanto, è fortemente sconsigliato utilizzare l’accesso posizionale su LinkedList.
Se l’applicazione richiede l’accesso posizionale, è opportuno utilizzare un semplice array, oppure la classe ArrayList.
Il fatto che l’accesso posizionale sia indicato per ArrayList e sconsigliato per LinkedList è anche segnalato dal fatto che, delle due, solo ArrayList implementa l’interfaccia RandomAccess.
RandomAccess è una interfaccia “di tag”, come Cloneable

• ovvero, è una interfaccia vuota;
• serve a segnalare che la classe che la implementa offre l’accesso posizionale in maniera efficiente.