© Armir Bujari – abujari@math.unipd.it

Universita Degli Studi di Padova

Programmazione Concorrente & Distribuita

A.A. 2017/2018Laurea Triennale in

Informatica

22

Collezione dell’API

• Una collezione (o contenitore) è un singolo oggetto che rappresenta un gruppo di oggetti, cioè gli elementi della collezione, che tipicamente sono di diversi tipi

• Mentre gli array in Java vengono creati con una lunghezza fissata (quindi sono statici), un oggetto di tipo Collection è un array dinamico di Object. Quindi è possibile modificare dinamicamente la sua lunghezza è ed è utile quando al momento della creazione della collezione non è noto il numero massimo di oggetti da memorizzare

• Il framework e’ composto dai seguenti elementi:

• Interfacce: tipi astratti che rappresentato collezioni e permettono la manipolazione indipendentemente dalla rappresentazione;

• Implementazioni: delle interfacce che rappresentano strutture dati riutilizzabili;

• Algoritmi: Metodi computazionali per effettuare delle operazioni sulle strutture dati concrete e.g., ricerca, ordinamento degli oggetti facenti parte della collezione. Nota: gli algoritmi sono polimorfici.

33

Tassonomia delle Contenitori Java

44

Supporto alla concorrenza

• Java SE7 introduce altre classi contenitore (java.util.concurrent) le quali operazioni sono considerate essere thread-safe

55

Interfaccia List

• Rappresenta una sequenza di elementi; può contenere elementi duplicate e si ha un controllo preciso dove un elemento viene memorizzato.

• Vi sono due tipi di liste concrette

• public class ArrayList<E> extends AbstractList<E>

implements List<E>, RandomAccess, Cloneable,

Serializable: struttura dati efficiente in accesso, ~ inserimento

(costo ammortizzato), lenta in rimozione dei elementi

• public class LinkedList<E> extends

AbstractSequentialList<E> implements List<E>,

Deque<E>, Cloneable, Serializable: struttura dati efficiente

in inserimento e cancellazione a basso costo ma, in generale, lenta in accesso casuale.

66

ArrayList

• E' un array ridimensionabile che può contenere diversi oggetti incluso il null.

• Le operazioni size, isEmpty, get, set, iterator e listIterator operano in tempo constante.

• L'operazione di aggiunta elemento, add, opera in tempo constante ammortizzato; aggiungere n elementi richiede tempo O(n), tutte le altre operazioni operano in tempo lineare.

• L'implementazione fornita' non è thread-safe, bisogna garantire ciò nella logica del programma.

• L’ArrayList gestisce l'occupazione della memoria mantenendo una capacity che è sempre maggiore o uguale alla lunghezza corrente. E' solitamente maggiore, poiché quando si aggiungono elementi, la capacità cresce di una certa quantità (che dipende dall’implementazione linguaggio).

77

ArrayList - Costruttori

•ArrayList(): costruisce una lista vuota di elementi con capacity iniziale a 10

•ArrayList(Collection<? extends E> c): costruisce una lista contenente gli elementi della collezione passata come argomento. L’ordine di inserimento e’ determinato dall’iteratore della collezione

•ArrayList(int initialCapacity): costruisce un lista vuota di elementi con capacita iniziale initialCapacity.

88

ArrayList – Alcuni metodi

• boolean add(E e): inserisce l'elemento specificato in fine lista e ritorna true se la collezione è stata cambiata dal operazione

• void add(int index, E element) throws IndexOutOfBoundsException: inserisce l'elemento specificato nella posizione indicata in lista, spostando l'elemento che occupa l'indice index(se ve ne è) e tutti gli elementi successivi di una posizione a destra (aggiunge 1 ai loro indici).

• boolean contains(Object o): ritorna true se l'elemento è contenuto nella lista. Formalmente, ritorna true sse la lista contiene un elemento per cui vale (o==null ? e==null : o.equals(e)).

• int indexOf(Object o): ritorna l'indice della prima occorrenza dell'elemento specificato in lista oppure -1 se la lista non contiene l'elemento. Formalmente, ritorna l'indice minore i per cui vale (o==null ? get(i)==null : o.equals(get(i))), oppure -1 se tale indice non esiste.

• E remove(int index) throws IndexOutOfBoundsException: rimuove l'elemento nella posizione indicata, spostando tutti gli elementi successivi a sinistra (sottraendo 1 dai loro indici). Ritorna l’elemento rimosso

• boolean remove(Object o): formalmente, rimuove l'elemento di indice i per cui vale (o==null ? get(i)==null : o.equals(get(i))). Ritorna true se la lista conteneva l’elemento.

99

Esempioimport java.util.*;

class Oggetto {

private String contenuto;

public Oggetto(String contenuto) {

this.contenuto = contenuto;

}

}

public class EsempioArrayList {

public static void main(String args[]) {

/*Costruisco una lista di String, tipo viene inferito in automatico - JSE7*/

ArrayList<Oggetto> obj = new ArrayList<>();

Oggetto primo = new Oggetto("PrimoOggetto");

/*Aggiungo elementi in lista */

obj.add(primo);

obj.add(new Oggetto("PCD AA. 2018/2019));

/*Rimozione elementi lista*/

obj.remove(new Oggetto("PrimoOggetto"));

obj.remove(1);

System.out.println(«Elementi lista dopo la rimozione:"+obj);

//stampa quanto segue: [Oggetto@3202a2cc]

}

}

1010

Esempioimport java.util.*;

class Oggetto {

…

public String getContenuto() {return contenuto;}

public toString() {return contenuto;}

public boolean equals(Object altroObj) {

if( !(altroObj instanceof Oggetto)) return false;

String altroContenuto = ((Oggetto)altroObj).getContenuto();

return contenuto.equals(altroContenuto);

}

}

public class EsempioArrayList {

public static void main(String args[]) {

/*Costruisco una lista di String, tipo viene inferito in automatico - JSE7*/

ArrayList<Oggetto> obj = new ArrayList<>();

Oggetto primo = new Oggetto("PrimoOggetto");

/*Aggiungo elementi in lista */

obj.add(primo);

/*Rimozione elementi lista*/

obj.remove(new Oggetto("PrimoOggetto"));

System.out.println("Elementi lista dopo la rimozione:"+obj);

//stampa quanto segue: []

}

}

1111

LinkedList

• Implementazione dell'interfaccia list come una lista doppiamente linkata.

•Tutte le operazioni hanno le performance che si aspettano da una lista dinamica doppiamente linkata.

•Le operazioni di indirizzamento lista la attraversano da inizio a fine, a seconda di dove i puntatori di scorrimento sono attualmente posizionati

•L'implementazione fornita' non è thread-safe, bisogna garantire ciò nella logica del programma.

1212

LinkedList - Costruttori

•LinkedList(): costruisce una lista vuota.

•LinkedList(Collection<? extends E> c): costruisce una lista contenente gli elementi presenti nella collezione passata come argomento, nel ordine determinato dall’iteratore della collezione.

1313

LinkedList – Alcuni metodi

• Stesse operazioni con uguale comportamento a ArrayList con l’aggiunta di altri metodi usati per modellare strutture dati specifiche e.g., Queue, Stack etc.

•Ad esempio

• boolean offer(E e): aggiunge l’elemento in coda alla

lista. Ritorna true se l’elemento è stato inserito nella lista, false altrimenti

• E peek(): Ritorna, senza rimuovere, la testa (primo

elemento) della lista.

• E pop(): Ritorna, rimuovendo il primo elemento dello stack

rappresentato dalla lista.

• void push(E e): Inserisce un elemento nello stack

rappresentato dalla lista. L’inserimento avviene in fronte alla

lista.

1414

Esempio

import java.util.*;

public class Stack<T>{

private LinkedList<T> storage = new LinkedList<T>;

public void push(T v) {storage.addFirst(v)}; //equivalente a push(v);

public T peek() {return storage.getFirst();} //equivalente a peek();

public T pop() {return storage.removeFirst();} //equivalente a pop();

public boolean empty() { return storage.isEmpty();}

public String toString() {return storage.toString();}

public static void main(String args[]) {

Stack<String> stack = new Stack<>();

for(String s: "P C D AA.2018/2019".split(" "))

stack.push(s);

while(!stack.isEmpty())

System.out.println(stack.pop());

}

}//Stampa: AA.2018/2019 D C P

1515

Interfaccia Map

• Rappresenta un array associativo che permette di associare un oggetto ad un altro oggetto – (chiave, valore). Non può contenere elementi duplicati; ogni chiave può contenere al più un valore (il valore può essere un contenitore).

• Alcune implementazioni

• public class HashMap<K,V> extends AbstractMap<K,V>

implements Map<K,V>, Cloneable, Serializable: un

insieme non ordinato di elementi in forma (chiave, valore). Eredità le performance spazio/tempo associate all’uso di una funzione hash che dovete aver già visto. Può contenere elementi null è non è thread-

safe

• public class TreeMap<K,V> extends AbstractMap<K,V>

implements NavigableMap<K,V>, Cloneable,

Serializable: un insieme di elementi in forma (chiave, valore)

ordinato sul valore della chiave. I dati sono memorizzati in un albero Rosso Nero di cui ne eredita le performance (O(logn)) per operazioni di ricerca, presenza, inserimento e rimozione). Non è thread-safe.

1616

HashMap - Costruttori

• HashMap(): costruisce una mappa vuota con initialCapacity a 16 e fattore di carico (load factor) di 0.75

• HashMap(int initialCapacity): costruisce una HashMap vuota capacita’ iniziale initialCapacity e load factor (0.75).

• HashMap(int initialCapacity, float loadFactor): costruisce una HashMap vuota secondo i parametri in ingresso.

• HashMap(Map<? extends K,? extends V> m): costruisce una nuova HashMap con gli stessi elementi (mappature) della lista in ingresso.

• Vediamo in seguito alcuni metodi della struttura e in seguito alcuni dettagli implementativi importanti da tener conto

1717

HashMap – Alcuni metodi

• void clear(): rimuove tutte le mappature dalla mappa.

• Object clone(): crea una coppia della mappa - le chiavi/valori non sono clonati (shallow copy)

• boolean containsKey(Object key): ritorna true se la mappa contiene una mappatura con la chiave specificata, altrimenti false

• Boolean containsValue(Object value): ritorna true se la mappa contiene una o più chiavi che mappano nel valore specificato, altrimenti false

• Set<Map.Entry<K,V>> entrySet(): ritorna un Set di coppie (chiave, valore) contenute nella mappa

• V get(Object key): Se presente, ritorna il valore mappato dalla chiave, altrimenti ritorna null

• Set<K>keySet(): ritorna un Set con tutte le chiavi contenute nella mappa

• V put(K key, V value): associa il valore value alla chiave key nella mappa. Se la chiave e già presente, viene sostituita. Se la chiave era presente, ritorna il valore associato, altrimenti null

• V remove(Object key): Se presente, rimuove la mappatura per le chiave key e ne ritorna il valore, altrimenti ritorna null

• int size(): ritorna il numero di elementi (chiave, valore) presenti nella mappa

1818

Esempio

import java.util.*;

/* Idealmente Random di default dovrebbe produrre una distribuzione uniforme dei numeri

*/

public class Statistics{

public static void main(String args[]) {

Random rand = new Random(47);

Map<Integer, Integer> m = new HashMap<Integer, Integer>();

for(int i=0; i < 10_000; i++) {

int r = rand.nextInt(20);

Integer freq = m.get(r);

map.put(r, (freq == null)? 1: freq+1);

}

System.out.println(m);

}

}//Nel mio computer: {15=497, 4=481, 19=464, 8=468, 11=531, 16=533, 18=478, 3=508,

7=471, 12=521, 17=509, 2=489, 13=506, 9=549, 6=519, 1=502, 14=477, 10=513,

5=503, 0=481}

1919

HashMap

Variabili d’interesse:capacity numero di bucketinitialCapacity numero di

bucket iniziali previsti (default 16)loadFactor fattore di carico

(default 0.75)threshold loadFactor * capacityif ( threshold exeeded) resize

to new capacity

Passi per individuare la posizione di un elemento all’interno struttura:1. Calcola il codice hash per la chiave

da inserire (Object::hashCode())2. Calcola la posizione (numero bucket)

come hash % (tableLength-1)

Osservazione: Valori loadfactor e initialCapacity parametri importanti

per la performance della struttura

2020

HashMap

Passi per individuare la posizione di un elemento all’interno struttura:1. Calcola il codice hash per la chiave

da inserire (Object::hashCode())2. Calcola la posizione (numero bucket)

come hash % (tableLength-1)

Ricerca lineare all’interno dei bucket per individuare il valore value mappato dalla chiave key:foreach(entry in bucket)

if(entry.key.hashCode() ==

key.hashCode() &&

((key = entry.key) ||

key.equals(entry.key)))

return entry.value;

return null;

2121

Discussione

• Nell’esempio d’uso HashMap visto in precedenza abbiamo usato un integrale per memorizzare/reperire il contenuto ad esso associato

• Si sfrutta l’autoboxing per convertire (in modo trasparente) un int Integer

• L’implementazione Integer::hashCode() ritorna il valore integrale ad esso assegnato

• Il metodo Integer::equals(Object obj) è ridefinito ed ha il comportamento atteso (operatore uguaglianza tra interi)

• Il comportamento di default dei metodi inserimento/cancellazione è quanto segue

• hashCode(): per individuare il bucket in cui l’obj e memorizzato; di

default ritorna interi distinti per oggetti distinti

• equals(Object obj): test uguaglianza parte del test sula componente chiave; di default ritorna true se l’oggetto invocazione è lo stesso di obj (uguaglianza tra reference)

• Morale: bisogna prestare attenzione e giudicare se serve la ridefinizione dei metodi sopra elencati in caso d’uso di chiavi custom

2222

Osservazione

•Sconsigliato mutare un elemento indicizzato in un collezione di tipo Map

• Se l’hashCode dell’elemento e’ cambiato esso si

puo’ trovare in una posizione sbagliata all’interno

della collezioni!

2323

Interfaccia Set

• Rappresenta una collezione di elementi che non può contenere elementi duplicati. Modella il concetto di insieme matematico. In alcune implementazione anche null può essere un elemento dell’insieme.

• Alcune implementazioni

• class HashSet<E> extends AbstractSet<E> implements

Set<E>, Cloneable, Serializable: implementa l'interfaccia Set, appoggiandosi a un struttura dati di tipo HashMap. Non da

alcune garanzie sull'ordine elementi all'interno dell'insieme e permette l'elemento null. Offre tempo costante per le operazioni

principali come l'aggiunta, rimozione, test presenza elemento, assumendo che la funzione hash distribuisce gli elementi in modo proprio nei vari bucket. Non è thread-safe.

• class TreeSet<E> extends AbstractSet<E> implements

NavigableSet<E>, Cloneable, Serializable: implementa un Set ordinato di elementi basandosi sull’ordinamento naturale.

L’implementazione e’ basata su una struttura ad’albero Rosso-Nero, garantendo costo O(log(n)) per operazioni di inserimento, rimozione etc. Non è thread-safe.

2424

HashSet - Costruttori

• HashSet(): costruisce un nuovo insieme vuoto; la struttura HashMapdi appoggio ha capacita iniziale di 16 e load factor di 0.75.

• HashSet(Collection<? extends E> c): costruisce un nuovo insieme contenente gli elementi della collezione argomento.

• HashSet(int initialCapacity): costruisce un nuovo insieme vuoto; la struttura HashMap di appoggio ha capacita iniziale initialCapacity e un load factor di 0.75.

• HashSet(int initialCapacity, float loadFactor): costruisce un nuovo insieme vuoto con capacita iniziale e load factor come specificati.

• Osservazione: Vale quanto detto nella costruzione e manutenzione di una struttura HashMap

2525

HashSet – Alcuni metodi

• boolean add(E e): inserisce l'elemento e nell'insieme se non esiste già

• void clear(): rimuove tutti gli elementi dalla lista

• Object clone(): ritorna una coppia dei elementi dell’insieme passato come argomento, gli elementi stessi non sono clonati (shallow copy).

• boolean contains(Object o): Ritorna true se l'elemento è contenuto nell'insieme, altrimenti false. Formalmente, ritorna true sse(o==null ? e==null : o.equals(e)), altrimenti false

• boolean isEmpty(): Ritorna true se l'insieme non contiene elementi, altrimenti false

• boolean remove(Object o): Se presente, rimuove l'elemento dall'insieme. Ritorna true se l'elemento era contenuto, altrimenti false

• int size(): Ritorna il numero di elementi contenuti nell'insieme (cardinalità insieme).

• Osservazione: vale la stessa considerazione riguardo i test presenza visto precedentemente per la HashMap

2626

Esempio

import java.util.*;

public class SetOfInteger{

public static void main(String args[]) {

Random rand = new Random(47);

Set<Integer> intset = new HashSet<Integer>();

for(int i=0; i<10_000; i++) {

intset.add(rand.nextInt(30));

}

System.out.println(intset);

}

}//Nella mia machina stampa:[15, 8, … 0] senza duplicati

2727

TreeSet - Costruttori

• TreeSet(): costruisce un insieme vouto ad’albero, ordinate secondo l’ordine naturale determinato dai suoi elementi

• TreeSet(Collection<? extends E> c): costruisce un nuovo insieme ad’albero a partire dai elementi collezione, ordinate secondo l’ordine loro naturale

• TreeSet(Comparator<? super E> comparator): costruisce un nuovo insieme vuoto ordinato, con ordine imposto dall’oggetto passato come argomento

• TreeSet(SortedSet<E> s): costruisce un insieme con ordine e elementi specificati dall’argomento.

• Osservazione: l’atteso comportamento della struttura dipende dall’ordine imposto tra i suoi elementi costituenti. Per impostare l’ordine, gli oggetti contenuti (o l’insieme) dovrebbe implementare i metodi forniti dalla interfacce java.lang.Comparable o java.util.Comparator

2828

TreeSet – Alcuni metodi

• boolean add(E e): Se non presente, aggiunge l'elemento nell'insieme. Ritorna true se l'inserimento è andato a buon fine, altrimenti false

• boolean remove(Object o): Se presente, ritorna true se l'elemento e' stato rimosso, altrimenti false

• E ceiling(E e): Ritorna il min{ x.lista | x>=e}, oppure null se tale elemento non esiste.

• E first(): Ritorna il primo elemento più piccolo presente nell'insieme.

• E higher(E e): Ritorna il min { x.lista | x > e} oppure null se tale elemento non esiste.

• E last(): ritorna l'elemento più grande presente nell'insieme.

• NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive):ritorna una vista di una porzione dell'insieme dove gli elementi sono compresi tra fromElement e toElement.

2929

Esempio

import java.util.*;

class Oggetto implements Comparable {

private int contenuto;

public Oggetto(int contenuto) {

this.contenuto = contenuto;

}

public int getContenuto() {return contenuto;}

public int compareTo(Oggetto altroOggetto) {

return contenuto – altroOggetto.getContenuto();

}

}

public class OrderedSet{

public static void main(String args[]) {

Random rand = new Random(47);

Set<Oggetto> ordintset = new TreeSet<Oggetto>();

for(int i=0; i<10_000; i++) {

ordintset.add(new Oggetto(rand.nextInt(30)));

}

System.out.println(ordintset);

}

}//Nella mia machina stampa:[0, 1, 2 … 29] in ordine senza duplicati

3030

Collections

• public class Collections extends Object: consiste esclusivamente di metodi statici e generici che operano su o ritornano collezioni. Contiene metodi polimorfici che operano su collezioni che ritornano una nuova collezione a seconda della modalità richiesta

• Alcuni metodi (vedere la API per maggiori informazioni):

• static <T> boolean addAll(Collection<? super T> c, T...

elements): aggiunge tutti gli elementi passati in argomento (elements) alla

collezione c

• static <T> int binarySearch(List<? extends Comparable<?

super T>> list, T key): cerca nella lista in argomento (list) per

l'oggetto richiesto (key) usando l'algoritmo di ricerca binaria

• static <T> void fill(List<? super T> list, T obj): rimpiazza

tutti gli elementi della lista (list) con l'elemento obj

• static <T extends Comparable<? super T>> void

sort(List<T> list): ordina la lista in ordina ascendente, secondo

l'ordina naturale imposto dai sui elementi

• static <T> void copy(List<? super T> dest, List<? extends

T> src): coppia tutti gli elementi da una lista all’altra.

3131

Arrays

• public class Arrays extends Object: come per la Collections che opera su collezioni, Arrays fornisce metodi statici che operano su strutture lineari (array, liste) e fornisce metodi di conversione array liste (dimensione fissa) e viceversa

• Alcuni metodi (vedere la API per maggiori informazioni)

• static <T> List<T> asList(T... a): ritorna una lista a

dimensione fissa, una coppia dall'array fornito in argomento

• static int binarySearch(Object[] a, int fromIndex,

int toIndex, Object key): ricerca per l'oggetto key all'interno

dell'array nel range specificato

• static <T> T[] copyOf(T[] original, int newLength):

crea una coppia dell'array passato in argomento, troncando o

riempendo l'eccesso, alla lunghezza specificata

• static String deepToString(Object[] a): ritorna una

rappresentazione String dei contenuti del array

• static boolean deepEquals(Object[] a, Object[] a2):

Ritorna true se i contenuti dell'array passati in argomento sono uguali

• static void sort(Object[] a): ordina gli oggetti dell'array in

argomento secondo l'ordina naturale da loro imposto

3232

I/O Stream: generalità

• Uno stream (flusso) è o una sorgente o una destinazione di byte

• Ci sono quindi due prime grandi categorie di stream: input streame output stream. E' possibile leggere dati da uno stream di input, ma non scriverci. Viceversa per uno stream di output

• java.io è il package di I/O, che intenderemo sempre importato

• java.io comprende le seguenti gerarchie di stream che differiscono a seconda del tipo di dato su cui operano

• Byte Stream: gestisce I/O di dati raw binari.

• Character Stream: gestisce I/O di caratteri, convertendo in e da caratteri –byte a seconda dei locale machina.

• Buffered Streams: I/O ottimizzato per ridurre il numero di chiamate alle API native.

• Scanning and Formatting: permette ai programmi di leggere e scrivere testo formattato.

• I/O from the Command Line: lettura/scrittura dai stream standard e Console.

• Data Streams: gestiscono I/O binario dei dati primitivi e stringe

• Object Streams: gestione I/O di oggetti

3333

Lettura/Scrittura su stream

• Indipendentemente dal tipo di stream è la modalità in cui si opera, lo scheletro classico per fare I/O è il seguente

appertura dello stream

while (ce informazione da {leggere | scrivere })

{leggi | scrivi } informazione

chiusura dello stream

• Osservazione: bisogna (quasi) sempre accertarsi della chiusura dello stream. E.g., in caso di un FileInput/OutputStream se ciò non avviene, si avrà un file aperto anche se esso non è più in uso in lettura/scrittura.

• Le operazioni di I/O, compresa l’apertura e chiusura dei stream, possono lanciare delle eccezioni che devono essere gestiti opportunamente