La classe HashSet

La classe HashSet fornisce una realizzazione dell'interfaccia Set utilizzando tabelle hash con la strategia di concatenamento per la risoluzione delle collisioni.

Per il calcolo del codice hash degli oggetti da memorizzare, si sfrutta il metodo public int hashCode() definito nella classe Object, e quindi invocabile su qualunque oggetto Java.

Attenzione: E' necessario che per ogni coppia di oggetti x e y, se x.equals(y) restituisce true, allora x.hashCode() = y.hashCode().
Quindi occorre ridefinire il metodo hashCode in ogni classe che ridefinisce equals.
Si veda ad esempio come è definito hashCode nelle classi Integer [locale, Medialab, Sun] e String [locale, Medialab, Sun].

L'intero restituito dal metodo hashCode() viene quindi trasformato eseguendo un'operazione di modulo rispetto alla lunghezza dell'array.

HashSet: Variabili d'istanza e costruttori

La classe HashSet ha due variabili d'istanza:

theLists, la tabella, cioè un array di liste;
modCount, un contatore di modifiche, come in LinkedList.

Ci sono 2 costruttori:

HashSet()

invoca l'altro costruttore con argomento DEFAULT_SIZE (131).

HashSet(int tableSize)

inizializza theList con un array la cui dimensione è il più piccolo numero primo maggiore di tableSize; quindi crea una lista vuota per ogni elemento della tabella.

public class HashSet implements Set {
    protected static final int DEFAULT_SIZE = 131;
    protected List [ ] theLists;
    protected int modCount;

    public HashSet() {
        this(DEFAULT_SIZE);
    }

    public HashSet(int tableSize) {
      theLists = new LinkedList[nextPrime(tableSize)];
      for (int i = 0; i < theLists.length; i++)
            theLists[i] = new LinkedList();
      modCount = 0;
    }

HashSet: Metodi (I)

Il metodo ausiliario listOf restituisce la lista designata a contenere un dato oggetto x. L'indice di tale lista viene determinato normalizzando il valore hash dell'oggetto (x.hashCode()) rispetto alla lunghezza dell'array, e trasformandolo in positivo se necessario.

    protected List listOf(Object x) {
      if (x == null)
          throw new IllegalArgumentException();
      int index = x.hashCode();
      index = index % theLists.length;
    // Potrebbe essere negativo
      if (index < 0)
          index += theLists.length;
      return theLists[index];
    }

HashSet: Metodi (II)

Utilizzando il metodo ausiliario listOf, i metodi add, remove e contains si riducono di fatto ad operare in modo opportuno sulla lista ottenuta.

    public boolean add(Object x) {
      List whichList = listOf(x);
      boolean isNew = !whichList.contains(x);
      if (isNew) {
            whichList.add(x);
            modCount++;
        }
      return isNew;
    }

$\begin{figure}\hspace{0.5cm}{\hbox{\psfig{figure=ChainHash/FigureHashSet/hash3.eps,width=5.5in}}}\end{figure}$

    public boolean remove(Object x) {
      List whichList = listOf(x);
      boolean isModified = whichList.remove(x);
      if (isModified) modCount++;
      return isModified;
    }

    public boolean contains(Object x) {
      List whichList = listOf(x);
      return whichList.contains(x);
    }

HashSet: Metodi (III)

Il metodo isEmpty deve restituire true se tutte le liste della tabelle sono vuote, false altrimenti.

    public boolean isEmpty() {
      for (int i = 0; i < theLists.length; i++) {
          if (!theLists[i].isEmpty())
              return false;
        }
      return true;
    }

Il metodo clear rende vuote tutte le liste nella tabella.

    public void clear() {
      for (int i = 0; i < theLists.length; i++)
             theLists[i].clear();
        modCount++;
    }

Il metodo iterator restituisce un iteratore per scandire gli oggetti dell'insieme.

    public Iterator iterator() {
      return new ProtectedItr();
    }

Analisi di complessità

Denotando con $\alpha$ il fattore di carico, cioè il rapporto tra il numero di oggetti memorizzati nella tabella e la sua dimensione theLists.length, si può dimostrare che la complessità dei metodi visti è proporzionale a $1 + \alpha$ . Quindi è una costante piccola quando lo è $\alpha$ .

È possibile migliorare il codice rendendo la tabella dinamica in maniera analoga a quanto fatto con le realizzazioni tramite array di pile e code. Quando il fattore di carico $\alpha$ supera una certa soglia, viene riallocata una tabella di dimensione maggiore, e viene riapplicata la funazione hash a tutti gli oggetti usando il nuovo valore di theLists.length. È preferibile ancora una volta scegliere un numero primo come valore di theLists.length.

Nel caso ci siano problemi di occupazione di memoria, è opportuno adottare una strategia di risoluzione delle collisioni basata sul metodo di indirizzamento aperto, che non usa liste.

Calcolo di numeri primi

I seguenti sono metodi ausiliari per la primalità. Il metodo primes(int n) restituisce un array di booleani lungo n che vale true nelle posizioni corrispondenti ai numeri primi; il metodo nextPrime(int n) restituisce il più piccolo numero primo maggiore di n.

Il metodo nextPrime(int n) si basa sul risultato [Bertrand, Chebyshev] seguente: per n > 1 esiste un numero primo compreso tra n e 2n. nextPrime(int n) invoca primes(2*n) sicuro che il prossimo primo sarà trovato tra n e 2n.

Il metodo primes(int n) realizza il crivello di Eratostene, elencando tutti i numeri primi minori di un numero dato in ingresso. L'idea è semplice: dato un numero primo, tutti i suoi multipli non sono primi. Consideriamo un insieme, che inizialmente contiene tutti i numeri maggiori o uguali a due. Ogni volta che individuiamo un numero primo, escludiamo dall'insieme tutti i suoi multipli. Più precisamente, cominciamo con l'escludere dall'insieme i multipli di 2, poi quelli di 3, poi quelli di 5 (4 non viene considerato in quanto già escluso come multiplo di 2), e così via.

    protected static int nextPrime(int n) {
      if (n > 1) {
         boolean[ ] P = primes(2*n);
         for (int i = n; i < P.length; i++)
             if (P[i]) return i;
        }
      return 2;
    }

protected static boolean[ ] primes(int n) {
boolean [ ] primeList = new boolean[n];

      primeList[0] = primeList[1] = false;
      for (int i = 2; i < n; i++)
             primeList[i] = true;

      int i = 1;
      while (i*i < n) {
// Trova il prossimo primo a partire da i
          while (!primeList[++i]);
// Adesso i e' uguale a tale primo
          int k = i*i;
          while (k < n) {
              primeList[k] = false;
              k += i;
            }
        }
      return primeList;
    }

La classe ProtectedItr: variabili d'istanza

Descriviamo ora la realizzazione degli iteratori su tabelle hash fornita dalla classe interna ProtectedItr. Una istanza di ProtectedItr visita gli elementi dell'insieme scandendo tutte le liste della tabella hash a partire da quella di posizione 0. Le variabili d'istanza sono:

expectedModCount, usata per individuare modifiche concorrenti;
listCursor, un iteratore sulla lista corrente;
tableCursor, che contiene l'indice della prossima lista non vuota, oppure theLists.length se non esiste.

protected class ProtectedItr implements Iterator {
    protected int tableCursor;
    protected Iterator listCursor;
    protected int expectedModCount;

ProtectedItr: costruttore

Il metodo ausiliario nextList() assegna a tableCursor l'indice della prossima lista non vuota, se esiste, oppure theLists.length se non esiste.

    void nextList() {
     do {
             ++tableCursor;
           } while ((tableCursor < theLists.length)
                      && theLists[tableCursor].isEmpty());
     }

Il costruttore cerca la prima lista non vuota e costruisce un iteratore su tale lista assegnandolo a listCursor. Se tutte le liste sono vuote (la tabella è vuota) a listCursor viene assegnato null.

    ProtectedItr() {
      tableCursor = -1;
        nextList();
      if (tableCursor < theLists.length) {
              listCursor = theLists[tableCursor].iterator();
                nextList();
            } else {
              listCursor = null;
            }
          expectedModCount = modCount;
   }

ProtectedItr: metodi

Il metodo hasNext() restituisce true (indicando che c'è un altro oggetto da visitare) se la lista che si sta visitando con listCursor non è finita, oppure se è finita ed esiste un'altra lista non vuota da visitare.

    public boolean hasNext() {
          if (modCount != expectedModCount)
               throw new ConcurrentModificationException();
          if (listCursor == null)
               return false;
          if (listCursor.hasNext())
               return true;
          return (tableCursor < theLists.length);
     }

Il metodo next() restituisce il prossimo oggetto da visitare nell'iterazione, se esiste. Se la lista che si sta visitando con listCursor non è finita, se ne restituisce il prossimo elemento. Altrimenti si crea un iteratore sulla prossima lista non vuota, e se ne restituisce il primo elemento dopo aver aggiornato il valore di tableCursor con nextList().

    public Object next() {
       if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
       if (! hasNext())
            throw new NoSuchElementException();
       if (listCursor.hasNext())
            return listCursor.next();
       listCursor = theLists[tableCursor].iterator();
         nextList();
       return listCursor.next();
     }

Il metodo remove() cancella l'oggetto restituito dall'ultima chiamata al metodo next(), richiamando remove() sull'iteratore della lista corrente.

    public void remove() {
        if (modCount++ != expectedModCount++)
             throw new ConcurrentModificationException();
        if (listCursor == null)
             throw new NoSuchElementException();
          listCursor.remove();
          }
     }

Esercizi su realizzazione di Set

1) Scrivere la classe ListSet che realizza gli insiemi usando le liste concatenate.

2) Scrivere la classe VectorSet che realizza gli insiemi usando Vector.

3) Si definisca l'interfaccia RichSet, che estende Set aggiungendo i metodi elencati di seguito. Si fornisca quindi un'implementazione dell'interfaccia RichSet estendendo la classe ListSet, VectorSet, oppureHashSet. Definire infine una classe TestRichSet per testare i nuovi metodi.

il metodo public Set interseca(Set S) che restituisce l'insieme contenente gli elementi comuni con S, senza alterare né l'insieme originale, né S;
il metodo public Set faiDifferenza(Set S) che restituisce l'insieme contenente gli elementi non comuni con S, senza alterare né l'insieme originale, né S;
il metodo public boolean unione(Set S) che aggiunge all'insieme tutti gli elementi appartenenti ad S. Il metodo restituisce true se l'insieme è stato modificato, false altrimenti.
il metodo public Object [] unico(Object [] V) che restituisce un array ottenuto eliminando gli elementi ripetuti in V (in accordo a obj1.equals(obj2)), senza alterare l'array originale.
il metodo public Object [] multiplo(Object [] V) che restituisce un array ottenuto eliminando gli elementi che compaiono una sola volta in V (in accordo a obj1.equals(obj2)), senza alterare l'array originale.
il metodo public Object [] toArray() che restituisce un vettore contenente tutti gli elementi appartenenti all'insieme;
il metodo public boolean retainAll(Set A) che modifica l'insieme conservando solo gli elementi che appartengono ad A, ovvero rimuove dall'insieme tutti gli elementi che non sono contenuti in A. Il metodo restituisce true se l'insieme è stato modificato, false altrimenti.
public int cardinality(); che restituisce il numero di elementi nell'insieme;
public void print(); che stampa gli elementi dell'insieme;
public RichSet Clone(); che restituisce una copia dell'insieme su cui è invocato.