Informatica I - mappe e dizionari in java

Mappa e dizionario

Mappa

Una mappa è un ADT con le seguenti proprietà:

• Contiene dati (non in sequenza) che sono coppie di tipo chiave/valore.
• Non può contenere coppie con identica chiave: ogni chiave deve essere unica nell’insieme dei dati memorizzati.
• Consente di inserire nuove coppie chiave/valore.
• Consente di effettuare ricerca e rimozione di valori usando la chiave come identificatore.

Dizionario

L'ADT dizionario ha molte similitudini con l'ADT mappa. Valgono tutte le proprietà dell'ADT mappa, tranne una: non si richiede che le chiavi siano uniche.

Analogia con un dizionario di uso comune

• Le chiavi sono le singole parole.
• I valori sono le definizioni delle parole nel dizionario.
• Le chiavi (parole) possono essere associate a più valori (definizioni) e quindi comparire più volte nel dizionario.
• La ricerca di un valore avviene tramite la sua chiave.

Dizionari ordinati e non-ordinati

Si distinguono dizionari ordinati e dizionari non-ordinati, cioè in Java, che le chiavi appartengano ad una classe che implementa Comparable.

Caso specifico

La nostra trattazione è limitata ad un caso ben preciso: Dizionari ordinati a chiave unica (cioè mappe).