Collezioni e mappe in Java

Ogni collettore ha le sue regole: come inserisce gli elementi,

· come li tiene ordinati, come permette di cercare gli elmenti

etc..., questo comporta diversi costi in termini di numero di

operazioni da fare per le operazioni essenziali sulla collezioni

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

Nele colelzioni non si possono memorizzare tipi primitivi, se si

· volesse si potrebbero usare le classi wrapper, le cui

funzionalità sono semplificare 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 collezioni che

memorizzano informazioni riconducibili a tipi primitivi è

semplificata.

List:

· cattura il concetto di equenza, 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

legano 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:

· cattura il concetto di insieme: gruppo di elementi che non

contiene duplicati, e non c’è un ordine

Essendo Set un’interfaccia allora 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, lei fa solo un mappaggio e una volta che

ha la posizione accede subito, sono quindi due operazioni,

il costo è quindi o(2)=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

studente, 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, ad esempio 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, in

java 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 garantito dal set. Il

mappaggio tra chiavi e valori è mantenuto come informaizoni

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,

invece 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 che la versione base e

HashTable che è 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 sta per i fattti 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 mappa, l'idea è che la mappa (ma ce ne sono anche altre)

non è sottoclasse diretta di collection allora il ollections fornisce

in maniera statica una serie di metodi comuni in modo che anche

le mappe possano giovare di queste implementazioni

preesistenti 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 l'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 (quale? 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 concetot di iterator

L'iteratore si occupa di 3 cose principali:

· stabilire se la struttura dati ha un elemento successivo

· mediante la hasNext();

fornisce il prossimo elemento mediante il metodo next();

· rimuove 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

E 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

strttura 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<