Informatica I - la realizzazione di un dizionario

Dizionari e prestazioni con array

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).