Realizzazioni del TDA Insieme

Vedremo due realizzazioni del tipo di dati astratto Insieme:
  • Nella prima, HashSet, una istanza (cioè un insieme) memorizza i suoi elementi in una tabella hash;

    •  
  • Nella seconda, TreeSet, un insieme memorizza gli elementi in una albero binario di ricerca.
Le due realizzazioni sono molto diverse concettualmente, e presentano vantaggi e svantaggi complementari.

Tabelle hash

Le tabelle hash sono strutture dati che permettono di memorizzare arbitrari insiemi di oggetti, fornendo un accesso molto efficiente agli elementi memorizzati.

Supportano un insieme ristretto di metodi, quali inserzione, ricerca, cancellazione. Godono delle seguenti proprietà:

  1. riescono ad avere un tempo medio di accesso costante che le rende veloci in pratica;
  2. il costo nel caso pessimo è lineare ma questo è un evento altamente improbabile;
  3. i relativi metodi sono semplici da programmare;
  4. non richiedono che sugli oggetti memorizzati sia definito un ordinamento totale (in pratica, non si richiede che realizzino l'interfaccia Comparable, come invece per gli alberi binari di ricerca).

Funzionamento basico di una tabella hash
Supponiamo di voler memorizzare degli oggetti in una tabella di dimensione n (cioè con n posizioni, comprese tra 0 e n-1). La memorizzazione degli oggetti avviene assegnando ad ogni oggetto un numero intero i, detto codice hash, tra 0 e n-1 e posizionando l'oggetto nell'i-esima posizione della tabella. La ricerca di un oggetto avviene calcolando il suo codice hash e quindi accedendo alla corrispondente posizione della tabella.

La realizzazione più comune delle tabelle hash si basa sull'uso di array: 

  • la memorizzazione di un oggetto avviene assegnando l'oggetto all'elemento dell'array corrispondente al suo codice hash; 
  • la ricerca di un oggetto avviene calcolando il suo codice hash e quindi accedendo al corrispondente elemento dell'array.
La funzione che calcola il codice hash di un oggetto, detta funzione hash, deve soddisfare le seguenti proprietà:
  • essere semplice, per non appesantire l'esecuzione del programma;
  • mappare oggetti uguali (nel senso di equals) in numeri uguali.
In particolare quest'ultima proprietà è fondamentale per la correttezza della realizzazione del TDA Insieme.

Funzioni hash: due esempi
Se gli elementi da memorizzare nella tabella hash sono interi, una semplice di funzione hash è data dall'operatore modulo con la dimensione della tabella come secondo argomento:
 

    hashValue = (int) (x % tableSize)
 


Per le stringhe, si può usare la seguente:
 

public static int hash(String s) {
    int hashVal = 0;
    for (int i=0; i<s.length(); i++)
        hashVal = 37 * hashVal + s.charAt(i);
    return hashVal;
}

Il calcolo della funzione hash suddetta trasforma una stringa$a_0 a_1 a_2 a_3 \cdots$ in un intero  usando la regola di Horner per la valutazione di polinomi: .


L'intero restituito dal metodo hash viene quindi convertito eseguendo un'operazione di modulo rispetto alle dimensioni della tabella. Se negativo (ciò può accadere a causa del trabocco generato dal metodo hash), il risultato del modulo viene trasformato (traslato) in positivo:
 

    int  index = hash(s);
    index = index % tableSize;
    if (index < 0) index += tableSize;
 


Il fenomeno delle collisioni
Fissate la dimensione della tabella e la funzione hash, c'è una collisione se applicando la funzione a due oggetti diversi e normalizzando i risultati rispetto alla dimensione della tabella (con l'operazione di modulo) si ottiene lo stesso valore. 

Per ridurre la frequenza di collisioni è utile usare tabelle con un numero primo di posizioni. 

Le collisioni sono inevitabili se la cardinalità dell'insieme che si vuole memorizzare è maggiore della dimensione della tabella. Ad esempio, se vogliamo memorizzare gli interi nell'itervallo [1, 14] in una tabella di dimensione 11, usando la funzione hash che calcola il modulo, abbiamo:

;  ;   .

Nel seguito indicheremo con hash'(x) il risultato di hash(x) normalizzato alla dimensione della tabella. 

Risoluzione di collisioni
In caso di collisioni, una tabella hash non può essere utilizzata nel modo descritto sopra: se  x e y sono due oggetti diversi e hash'(x) = hash'(y), non possiamo memorizzarli entrambi nella stessa posizione della tabella. 

Esistono diverse strategie di risoluzione delle collisioni. Nella strategia di concatenamento, la tabella è realizzata con un array di liste o catene (chain), nelle quali vengono inseriti gli oggetti. Quindi un oggetto x sarà contenuto nella lista che si trova in posizione hash'(x), insieme a tutti gli oggetti in collisione con esso.

Ad esempio, supponiamo di voler inserire, nell'ordine, gli interi: 42, 15, 100, 25, 73, 68, 84, 57, 3, 99, 27, 62 in una tabella realizzata con un array di lunghezza 5. Assumendo che la funzione hash riduca gli interi dati modulo 5, la tabella risulta essere la seguente.
 

Per ridurre la frequenza di collisioni, occorre che la dimensione della tabella tableSize sia sufficientemente grande rispetto al numero n di oggetti da memorizzare, in modo che la lunghezza media delle liste ($\alpha = n/ \, \verb*+tableSize+$, chiamato fattore di carico ) sia una costante piccola. Questo fattore determina la complessità delle operazioni di inserimento e di ricerca.