Si deve sviluppare una classe iterabile HashSetConcatenato<T> con funzionalità simili a quelle della classe
LinkedHashSet<T> di java.util. Si tratta di una classe collezione di tipo set (insieme matematico) che deve
implementare tutti i metodi dell’interfaccia java.util.Set<T> più i metodi equals, hashCode, toString e iterator
(struttura di iterazione). Una collezione HashSetConcatenato<T> si basa su una tabella hash (array),
diciamola th, in cui gli elementi di tipo T sono memorizzati/ritrovati in base al loro hashCode. Tuttavia,
un’iterazione su un oggetto HashSetConcatenato riflette l’ordine di inserimento degli elementi. Tutto ciò è
simile a quanto avviene per un oggetto LinkedHashSet<T> ma differisce da un HashSet<T> che, come è noto,
non è in grado di assicurare alcun ordine degli elementi durante un’iterazione. Come spiegato a lezione, la
posizione (indice) che compete ad un oggetto x di tipo T può essere determinata come segue:
int h=x.hashCode();
if( h<0 ) h=-h;
int indice=h%th.length;
Naturalmente sono possibili le collisioni: più elementi possono corrispondere ad una stessa cella dell’array. Gli
elementi che collidono su una stessa posizione, vanno memorizzati su una lista concatenata (bucket) a
puntatori espliciti. I nodi delle liste bucket sono collegati tra loro sia in ragione delle collisioni che in relazione
all’ordine di inserimento.
, le liste bucket sono realizzate come liste semplici (puntatori a tratto pieno). La lista
doppia che riflette l’ordine di inserimento utilizza, invece, due ulteriori campi puntatore dei nodi; tali puntatori
sono mostrati a tratto leggero (detti prox e prior i due campi puntatore rispettivamente al prossimo nodo e al
precedente nodo nella lista d’ordine di inserimento, i puntatori prox sono evidenziati tratteggiati). In figura si
suppone che x, y e z collidano tra loro, cosi come v e q. Inoltre, z è stato inserito per primo, quindi è stato
inserito w, quindi v, y, q ed infine x. In quest’ordine verranno restituiti gli elementi della tabella hash durante
un’iterazione. La testa della lista dell’ordine di inserimento è mostrata sulla destra in basso.
Tutte le liste bucket possono essere gestite a stack. La lista dell’ordine di inserimento va, invece, gestita a coda.
La classe HashSetConcatenato<T> deve disporre di almeno due costruttori. Quello di default crea l’array
secondo una dimensione implicita, es. il numero primo 53. Il secondo costruttore riceve la capacità iniziale
dell’array, che si aspetta essere un numero primo. Allorquando il grado di riempimento (size) della tabella supera
il 75% della sua capacità, la tabella va riallocata utilizzando una dimensione doppia (es. un numero primo
prossimo al doppio della capacità attuale) ed il suo contenuto ridistribuito sul nuovo array.
Rispondi quotando
