Informatica I - la realizzazione di un dizionario

Un dizionario può essere realizzato usando la struttura dati array: ogni cella dell’array contiene un

riferimento ad una coppia chiave/valore. La coppia chiave/valore sarà un oggetto di tipo Pair (da definire)

PRESTAZIONI DI UN DIZIONARIO

A seconda degli ambiti applicativi è possibile:

 mantenere le chiavi ordinate nell’array

 La ricerca ha prestazioni O(log n) (perché si può usare la ricerca per bisezione)

 La rimozione ha prestazioni O(n) (perché bisogna effettuare una ricerca, e poi spostare

mediamente n/2 elementi per mantenere l’ordinamento)

 L’inserimento ha prestazioni O(n) (perché si può usare l’ordinamento per inserimento in un array

ordinato), altrimenti usando un diverso algoritmo occorre riordinare l’intero array, con

prestazioni almeno O(n log n)

 mantenere le chiavi non ordinate nell’array

 La ricerca ha prestazioni O(n) (perché bisogna usare la ricerca lineare)

 La rimozione ha prestazioni O(n) (perché bisogna effettuare una ricerca (lineare), e poi spostare

nella posizione trovata l'ultimo elemento dell'array (l’ordinamento non interessa)

 L’inserimento ha prestazioni O(n) (perché bisogna rimuovere (sovrascrivere) un elemento con la

stessa chiave, se c'è, e poi inserire il nuovo elemento nella ultima posizione dell’array. [Se non si

richiede che le chiavi siano uniche nel dizionario, la rimozione non è necessaria e l'inserimento è

O(1)]

Quindi: - Se si fanno frequenti inserimenti e sporadiche ricerche e rimozioni la scelta migliore è l’array non

ordinato

- Se il dizionario viene costruito una volta per tutte, poi viene usato soltanto per fare ricerche la

scelta

migliore è l’array ordinato

LA CLASSE PAIR

Un dizionario contiene elementi formati da coppie Chiave – Valore. Per realizzare un dizionario tramite

array, dobbiamo allora realizzare una classe Pair e gli elementi del dizionario saranno contenuti nell’array

Pair[ ]:

Gli oggetti di tipo Pair devono avere due campi di esemplare:

 key (di tipo Comparable perché trattiamo dizionari ordinati)

 value (di qualsiasi tipo, ovvero di tipo Object)