Collezioni e mappe in Java

Collezioni in Java

Ogni collettore ha le sue regole: come inserisce gli elementi, come li tiene ordinati, come permette di cercare gli elementi, ecc. Questo comporta diversi costi in termini di numero di operazioni da fare per le operazioni essenziali sulla collezione che sono: ricerca, inserimento e rimozione.

Una collection è un oggetto che raggruppa in un’unica unità più elementi. Collection rappresenta gruppi di oggetti che possono essere duplicati oppure no, alcune possono essere ordinate e altre no.

Nelle collezioni non si possono memorizzare tipi primitivi; se si volesse, si potrebbero usare le classi wrapper, le cui funzionalità sono semplificate da boxing e unboxing:

• Boxing: è possibile assegnare direttamente tipi primitivi a oggetti wrapper; è il compilatore che inserisce le istruzioni per gestire il wrapping.
• Unboxing: è possibile assegnare direttamente oggetti wrapper a tipi primitivi; è il compilatore che inserisce le chiamate a costruttori e metodi.

Grazie a boxing e unboxing, anche la gestione delle collezioni che memorizzano informazioni riconducibili a tipi primitivi è semplificata.

List

List cattura il concetto di sequenza: gruppi di elementi posti in un qualche ordine. Implementazioni: ArrayList, LinkedList, Vector.

La LinkedList non soffre del problema dell'inserimento; se ad esempio aggiungo dei conti correnti in una banca, non avrò dei costi di riallocamento. Nella LinkedList ogni elemento ha una reference al successivo e la classe LinkedList ha il riferimento al primo elemento, cioè alla testa. Quindi la LinkedList tiene traccia di chi è il primo e ogni item si lega l'uno con l'altro; il limite è l’ampiezza della memoria.

La List<E> estende Collection, può avere duplicati, oltre alle operazioni offerte da Collection, offre altre operazioni come:

• Accesso posizionale: permette di accedere agli elementi in base alla loro posizione nella lista (tipo array).
• Ricerca: permette di ricercare un elemento nella lista e ritorna la sua posizione all’interno della sequenza.

Set

Set cattura il concetto di insieme: gruppo di elementi che non contiene duplicati, e non c’è un ordine.

Essendo Set un’interfaccia, dobbiamo usare un’implementazione. Tra le tante implementazioni abbiamo l’HashSet, che lavora con le funzioni hash, ad esempio dato uno studente, restituisce un numero; se inserisco lo stesso studente, la funzione hash restituisce lo stesso numero. L'HashSet ha un costo costante: vedere se ci sono duplicati non costa niente, fa solo un mappaggio e una volta che ha la posizione accede subito. Il costo è quindi O(1) perché costante.

La funzione hash contiene un metodo chiamato hashcode che ci propone una strategia per mappare a un oggetto un numero. Lo fa in maniera molto base. Il metodo hashcode ci permette, se ad esempio il dominio ha a che fare con studenti, di scrivere la funzione hash per il nostro studente, cioè come tirare fuori il numero corrispondente. Ad esempio, potrei dire che il valore dello studente sono le ultime 3 cifre della matricola, oppure potremmo fare un'altra logica: prendo il nome, il cognome e la data di nascita, li converto tutti in interi, li sommo tutti e ottengo un solo numero. La probabilità che due studenti diversi con nome, cognome e data di nascita diversi abbiano la stessa somma ragionata in questo modo è abbastanza bassa: questa è la qualità della funzione hash. Inoltre, questo è un modo per ottenere un numero da uno studente.

Set offre tutti e soli i metodi della interface Collection, con la restrizione che le classi che la implementano si impegnano a non ammettere la presenza di elementi duplicati. Per poter parlare di duplicati sarà necessario stabilire e modellare un criterio di equivalenza tra gli elementi dell'insieme.

Il Set può essere implementato con un SortedSet che, a differenza dell'HashSet, è un insieme ordinato e può tornare utile per la ricerca sfruttando la ricerca binaria. Di base l'insieme non è ordinato, ma il SortedSet lo è.

Gerarchia delle interfacce

Una Map è un oggetto che mappa chiavi in valori; non ci possono essere chiavi duplicate. Si indica come Map<K, V>.

SortedMap mantiene l’ordinamento crescente delle chiavi. Le mappe non sono sotto classi di Collection.

Una mappa è una tabella. Una tabella è l'elemento base per rappresentare qualunque tipo di dato. Quando non sappiamo come rappresentare un dato, la tabella è considerata il tipo standard. In Java, le mappe sono tabelle di due soli elementi; una mappa è definita come un insieme di coppie chiave-valore. Le chiavi sono univoche, non ammettono duplicati, quindi è come se fosse un set sulle chiavi. L'unica condizione è l'unicità delle chiavi garantita dal set. Il mappaggio tra chiavi e valori è mantenuto come informazioni dalla struttura dati stessa.

Una mappa permette di:

• Ottenere il valore associato a una chiave.
• Cancellare una coppia in cui compare una chiave.
• Inserire una nuova coppia nella mappa.
• Ottenere una collezione contenente tutte le chiavi o tutti i valori.

I valori sono associati a una e una sola chiave, i valori non sono univoci; quindi, data una chiave abbiamo sempre un solo valore, mentre il valore può essere associato a più chiavi. Il modo usato da Java per fare in modo che le chiavi siano univoche è mediante l'implementazione della HashTable oppure HashMap. HashTable e HashMap sono la stessa cosa; si usano due nomi per la programmazione concorrente. HashMap è la versione base e HashTable è resistente alla concorrenza: ha un costo maggiore, ma non fanno fare errori concorrenziali. Bisogna quindi valutare quando usare o meno quelli sincronizzati.

Una funzione hash è una funzione che, dato un dominio D di partenza, restituisce per ogni elemento del dominio uno e un solo elemento del codominio. Questa funzione ha la caratteristica di non essere invertibile. Un'altra proprietà delle funzioni hash è che il codominio è di solito nettamente più piccolo del dominio in termini di dimensioni.

Potrebbero esserci delle collisioni: potrebbe capitare che a due elementi del codominio venga associato solo un elemento del dominio. La qualità della funzione hash si misura in termini della probabilità di collisione: più bassa è la probabilità di collisione e più buona è la funzione hash.

La classe Collections

La classe Collections sta per i fatti suoi perché non estende nessuno e nessuno la estende. Essa rappresenta un collettore delle funzionalità comuni di base per le strutture dati, ad esempio il sort, che ora diventa anche compatibile ad esempio con mappe. L'idea è che la mappa (ma ce ne sono anche altre) non è sottoclasse diretta di Collection, allora Collections fornisce in maniera statica una serie di metodi comuni in modo che anche le mappe possano giovare di queste implementazioni preesistenti in Java. Se vorremo usare l'ordinamento, useremo Collections.sort e gli passiamo l'ArrayList.

Iterator

L’iterator è un’entità che rappresenta un concetto: rappresenta il fatto che una struttura debba poter essere scansionata o iterata. Ci permette di iterare sulla struttura dati, quindi il primo elemento, il secondo, etc. L'iteratore è come se fosse un dito che punta a ciascun elemento; è un indice che si aggiorna man mano che ci spostiamo attraverso la struttura. Nella lista, nel momento in cui parto dalla head e mi sposto di uno step andando al primo item dopo la head, nel for per tenere traccia dell'item a cui sono arrivato mi aiuta il concetto di iteratore: è un indice specifico per una struttura.

La particolarità di questo iterable è che fondamentalmente definisce un certo metodo (forse è messo negli esempi delle prossime slide), questo metodo è necessario e richiesto dal fatto che la struttura è iterabile, vuol dire che in qualsiasi momento io posso avere accesso all'iteratore di quella struttura.

Tutte le collezioni, eccetto la mappa perché non ha senso iterare su una mappa, hanno il concetto di iterabilità, quindi mi permettono di ottenere l'iteratore. Una collection estende il concetto di iterator.

L'iteratore si occupa di tre cose principali:

• Stabilire se la struttura dati ha un elemento successivo mediante il metodo hasNext().
• Fornire il prossimo elemento mediante il metodo next().
• Rimuovere dalla collezione l'ultimo elemento che è stato restituito dalla chiamata di next(), questo mediante il metodo remove().

Metodi del iterator:

• boolean hasNext(); ritorna true se e solo se esiste un altro elemento da scandire.
• next(); restituisce il prossimo elemento della collezione nella scansione corrente ed avanza.
• void remove(); rimuove dalla collezione l'ultimo elemento che è stato restituito dalla chiamata di next().

Questo metodo (penso hasNext();) è importante perché se ci troviamo in un loop, la condizione di uscita di questo loop potrebbe essere una richiesta alla struttura dati. Gli chiediamo quindi se ha ancora degli elementi, non lo chiediamo all'iteratore ma direttamente alla struttura dati. Si parla di meccanismo di iterazione implicita, sappiamo che si può fare perché le collezioni sono legate all'iteratore, quindi le collezioni sono di tipo iterabile, quindi hanno l'iteratore. Quindi è chiaro che la struttura dati si autoitera dicendo qual è il successivo. Quindi se siamo in un ciclo for in cui chiediamo alla struttura di dirci qual è il suo prossimo, se poi durante il loop chiediamo alla struttura dati di cancellare un elemento succederà che la struttura dati perde il segno perché gli stiamo cambiando il contenuto, perché abbiamo provato a cancellare un elemento che lei usa per puntare al successivo. Quindi le creiamo un problema, quindi la cancellazione di una struttura dati di questo tipo è molto pericolosa, quindi non possiamo cancellare mentre iteriamo, quindi lo chiediamo all'iteratore, così rimuoviamo sulla struttura dati e l'iteratore non perde il segno perché sa già chi è il suo prossimo.