Le Collezioni (Java Collections)


Modellare liste e insiemi

Esempi di liste

Scansione

Esempi di insiemi

Mappe

Liste e insiemi

Insieme

Lista (sequenza)



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Il framework Collection

Le collection di Java rappresentano�mn’architettura�mnificatapreposta all’uso e al trattamento di gruppi di oggetti.Consistono di:

Interfacce: tipi di dati astratti che rappresentano collezioni,come List, Queue, Set e MapImplementazioni astratte: parziali implemetazioni diinterfacce facilmente riadattabiliImplementazioni concrete: classi basilari cheimplementano le interfacce fondamentaliAlgoritmi: implementazioni di funzioni basilari comeordinamento e ricerca, applicabili a tutte le collezioniUtilita: funzioni basilari applicate ad array di primitivi eriferimento



Esempi di liste

Scansione

Esempi di insiemi

Mappe

La gerarchia delle interfacce



Esempi di liste

Scansione

Esempi di insiemi

Mappe

L’interfaccia Collection

public interface Collection<E> extends Iterable<E> {// Op e r a r igfa�ZYk]

int size();boolean isEmpty();boolean contains(Object element);boolean add(E element); // Optional

boolean remove(Object element); // Optional

Iterator iterator();// Op e r aragfa�kmdd±afka]e]

boolean containsAll(Collection<?> c);boolean addAll(Collection<? extends E> c); // Optional

boolean removeAll(Collection<?> c); // Optional

boolean retainAll(Collection<?> c); // Optional

void clear(); // Optional

// O p e r aragfa�km�YjjYq

Object[] toArray();<T> T[] toArray(T[] a);

}



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Contratto del metodo add(E o) - opzionale

... Returns true if this collection changed as a result ofthe call. (Returns false if this collection does not permitduplicates and already contains the specified element.)... limitations on what elements may be added to thiscollection. In particular, some collections will refuse to addnull elements, and others will impose restrictions on thetype of elements that may be added. Collection classesshould clearly specify in their documentation anyrestrictions on what elements may be added.If a collection refuses to add a particular element for anyreason other than that it already contains the element, itmust throw an exception (rather than returning false)...



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Le interfacce di Collection

Collection e la radice della gerarchia delle collection.Rappresenta gruppi di oggetti (elementi) chepossono essere duplicati oppure no. Alcunepossono essere ordinate altre no. Esistonoimplementazioni concrete di sottointerfacce qualiList e Set

List cattura il concetto di lista ordinata (o sequenza):gruppo di elementi posti in un qualche ordine.Implementazioni: ArrayList, LinkedList eVector

Set cattura il concetto di insieme: gruppo di elementiche non contiene duplicati (non contiene e1 e e2se e1.equals(e2)©. Implementazioni: HashSet



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Gerarchia (parziale) di Collection (List e Set)

Collection

List Set

HashSetArrayList LinkedList

�@7IB=�A9HC8=�5;;=IBH=J=�89@@W=BH9F:577=5�List!!public void add(int index, E element)!Inserts!the!specified!element!at!the!specified!posi2on!in!this!list!(op2onal!opera2on).!!Shi7s!the!element!currently!at!that!posi2on!(if!any)!and!any!subsequent!elements!to!the!right!(adds!one!to!their!indices).!public E get(int index)!Returns!the!element!at!the!specified!posi2on!in!this!list.!public int indexOf(Object o) [lastIndexOf(Object o)]!Returns!the!index!of!the!first![last]!occurrence!of!the!specified!element!in!this!list,!or!C1!if!this!list!does!not!contain!the!element.!public E remove(int index)!Removes!the!element!at!the!specified!posi2on!in!this!list!(op2onal!opera2on).!!Shi7s!any!subsequent!elements!to!the!le7!(subtracts!one!from!their!indices).!!Returns!the!element!that!was!removed!from!the!list.!



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Esempio

class Gatto {// co s t r u t t o r e

public Gatto(int i)// re s t i t u i s c e l ’ i d e n t i f i c a t i v o unico

public int getID()}

public class Cane {// co s t r u t t o r e

public Cane(int i)// re s t i t u i s c e l ’ i d e n t i f i c a t i v o unico

public int getID()}



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Esempio: uso di non-generici

import java.util.*;

public class CaniEGatti {public static void main(String[] args) {

/* de f i n i z i o n e tipica : uso del

r i f e r i m e n t o piu ’ astratto */

List gatti = new ArrayList();for(int i = 0; i < 7; i++)

gatti.add(new Gatto(i));

/* nessun problema ad a g g i u n g e r e

oggetti di tipo diverso */

for (int i = 0; i < 3; i++)gatti.add(new Cane(i));

}}



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Svantaggi

Uno svantaggio tipico e la perdita di informazione sul tipoquando si inseriscono oggetti nel contenitore. Infatti:

poiche non vi sono restrizioni sul tipo di oggetti inseribilinel contenitore, e possibile inserire senza problemi cani inuna collezione di gatti (fonte di potenziali errori)a causa della perdita del tipo, occorre eseguire unaforzatura (cast) “corretta”, a run time, all’attodell’estrazione dell’oggetto per non incorrere inun’eccezione



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Esempio

import java.util.*;

public class CaniEGatti {public static void main(String[] args) {

List gatti = new ArrayList();for(int i = 0; i < 7; i++)


gatti.add(new Cane(7));

/* Eccezione rilevata a run time */

for(int i = 0; i < gatti.size(); i++)((Gatto)gatti.get(i)).id();

}}



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Parametrizzare la lista

Per ovviare ai problemi precedenti e lecito definire una nuovaclasse lista parametrizzatY

List<Gatto> gatti = new ArrayList<Gatto>();List<Cane> cani = new ArrayList<Cane>();

for (int i = 0; i < 7; i++) // aggiungi



cani.add(new Cane(i));

for (Gatto g : gatti) // estrai

out.println(g);for (Cane c : cani)

out.println(c);



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Vantaggi nell’uso di generici

I principali vantaggi dovuti all’introduzione dei tipi generici sono:

Il compilatore puo verificare qulasiasi operazione add dioggetti alla collezioneil tipo dell’oggetto estratto da una collezione e noto, quindinon vi e la necessita di operare un cast a un tipo diverso(fonte di potenziali errori se il cast e fatto su tipi nonomologhi)



Esempi di liste

Scansione

Esempi di insiemi

Mappe

ArrayList vs LinkedList

ArrayList ottimizzato l’accesso casuale (basato su array),non ottimizzati l’inserimento e l’eliminazioneall’interno della lista (grosso modo equivalente aVector)

LinkedList ottimizzato l’accesso sequenziale, l’inserimento el’eliminazione, indicato per implementare pile(LIFO) e code (FIFO), infatti contiene i metodi:addFirst(), addLast(), getFirst(),getLast(), removeFirst( ),removeLast()

�@5GG9�Collections!!MeHe!a!disposizione!metodi!per!effeHuare!operazioni!generiche!con!le!Collezioni.!•  Ordinare!una!lista!(sort)!•  Mescolare!una!lista!(shuffle)!•  Scambiare!elemen2!di!una!lista!(swap)!•  Copiare!una!lista!(copy)!•  …!Ne!esiste!una!equivalente!anche!per!gli!array!(Arrays).!

�@5GG9�Collections!!Esempio:!metodi!sort!!static void sort(List<T> list)!Sorts!the!specified!list!into!ascending!order,!according!to!the!natural'ordering!of!its!elements.!

!!static void sort(List<T> list, Comparator<? super T> c) !Sorts!the!specified!list!according!to!the!order!induced!by!the!specified!comparator. !!

�@5GG9�Collections!!Esempio:!metodo!sort!Ordiniamo!una!lista!di!Integer!secondo!l’ordine!naturale.!List<Integer> listaInteri = new ArrayList<Integer>();!listaInteri.add(5);!listaInteri.add(2);!listaInteri.add(9);!Collections.sort(listaInteri);!System.out.println("Lista di interi ordinata: ");!for (int i:listaInteri) {! System.out.println(i);!

} !!

$BH9F:577=5�Comparable!! Per!definire!l’ordinamento!naturale!di!una!classe,!la!classe!deve!implementare!l’interfaccia!Comparable.!E’#buona#norma#che#il#metodo#compareTo#sia#simmetrico#e#consistente#con#equals!##java.u7l#Interface#Comparable<T>#T!C!the!type!of!objects!that!this!object!may!be!compared!to!!int!compareTo(T#o)!Compares!this!object!with!the!specified!object!for!order.!Returns!a!nega2ve!integer,!zero,!or!a!posi2ve!integer!as!this!object!is!less!than,!equal!to,!or!greater!than!the!specified!object.!

�CAD5F5HCF=�! Un!comparatore!implementa!un!metodo!compare!per!comparare!due!oggeV!secondo!un!ordine!totale.!Puo’!essere!usato!come!secondo!argomento!del!metodo!Collections.sort.!E’#buona#norma#che#il#metodo#compare#sia#simmetrico#e#consistente#con#equals!##java.util Interface Comparator<T>!T!C!the!type!of!objects!that!may!be!compared!by!this!comparator!!int compare(T o1, T o2)!Compares!its!two!arguments!for!order.!Returns!a!nega2ve!integer,!zero,!or!a!posi2ve!integer!as!the!first!argument!is!less!than,!equal!to,!or!greater!than!the!second.!

�CAD5F5HCF=!!Esempio:!GaHo!comparabile!!public class Gatto implements Comparable<Gatto> {! // ....! @Override! public int compareTo(Gatto gatto) {! if (gatto.getID() == getID()) {! return 0;! } else if (gatto.getID() < getID()) {! return -1;! } else {! return 1;! }! }!

} !!

�CAD5F5HCF=!!Esempio:!GaHo!comparabile!Creiamo#un#comparatore#che#ordini#i#gaB#in#base#al#nome.!!public class NomeGattoComparator implements Comparator<Gatto> {!! @Override! public int compare(Gatto g1, Gatto g2) {! return g1.getNome().compareTo(g2.getNome());! }!

} !!

�CAD5F5HCF=�9�sort!!Esempio:!ordinamento!di!gaV!in!base!al!nome!!List<Gatto> gatti = new ArrayList<Gatto>();!gatti.add(new Gatto(1, "Tom"));!gatti.add(new Gatto(1, "Felix"));!gatti.add(new Gatto(1, ”Star"));!!System.out.println("Lista gatti:");!for (Gatto gatto:gatti) {! System.out.println(gatto.getNome());!}!Collections.sort(gatti, new NomeGattoComparator());!System.out.println("Lista gatti ordinata:");!for (Gatto gatto:gatti) {! System.out.println(gatto.getNome());!}!



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Scansione: for-each e Iteratori

Il costrutto for-each:

for (Object o : collection)System.out.println(o);

L’interfaccia Iterator:

public interface Iterator<E> {boolean hasNext();E next();void remove();

}



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Uso: for-each e Iteratori

Si usa l’iteratore�Yd�hgklg�\a �for-each quando:

si deve rimuovere il corrente oggetto (esempio filtraggio)static void filter(Collection c) {

for (Iterator i = c.iterator(); i.hasNext();) {if (!cond(i.next()))i.remove();

}

si deve rimpiazzare un elemento nella lista o nell’arraydurante l’attraversamento

ListIterator<E> extends Iterator<E>

occorre iterare su molteplici collezioni simultaneamente



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Uso di Iterator

ProblemaUsare Iterator per modificare la classe CaniEGatti al finedi eliminare dalla lista gatti i gatti con ID dispari e dalla listacani i cani con ID pari



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Codifica

List<Gatto> gatti = new ArrayList<Gatto>();List<Cane> cani = new ArrayList<Cane>();




cani.add(new Cane(i));

// iterator

for (Iterator<Gatto> eG = gatti.iterator(); eG.hasNext();){if ((eG.next().getID() % 2) == 1)eG.remove();

}for (Iterator<Cane> eC = cani.iterator(); eC.hasNext();) {if ((eC.next().getID() % 2) == 0)eC.remove();

}



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Indice

1 Le Collezioni (Java Collections)Modellare liste e insiemiEsempi di ListeScansione: for-each e IteratoriEsempi di insiemiMappe



Esempi di liste

Scansione

Esempi di insiemi

Mappe

L’interfaccia Set

public interface Set<E> extends Collection<E> {// Op e r a z i o n i base

int size();boolean isEmpty();boolean contains(Object element);boolean add(E element); // Optional

boolean remove(Object element); // Optional

Iterator iterator();

// Op e r a z i o n i su c o l l e z i o n i

boolean containsAll(Collection<?> c);boolean addAll(Collection<? extends E> c); // Optional

boolean removeAll(Collection<?> c); // Optional

boolean retainAll(Collection<?> c); // Optional

void clear(); // Optional

// O p e r a r igfa�km�YjjYq

Object[] toArray();<T> T[] toArray(T[] a);



Esempi di liste

Scansione

Esempi di insiemi

Mappe

La classe HashSet

Una della classi piu utili nella gestione di insieme di oggetti e laclasse HashSet

Set<T> insieme = new HashSet<T>(c);

Osservazione: Notare che si usa il tipo interfaccia Set per lavariabile insieme (pratica fortemente raccomadata). Siproduce codice molto flessibile. Per esempio, per averel’elenco ordinato:

Set<T> insieme = new TreeSet<T>(c);



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Il codice hash associato agli oggetti

Funzione hashUnY funzione hash in Java e una funzione che mappa unoggetto in un numero intero (codice hash)

Propriet

`

a:

oggetti logicamente uguali devono avere lo stesso codicehashOggetti distinti possono avere lo stesso codice hash(collisione), l’importante e che questo fatto sia piuttostoinfrequenteDeve essere una funzione semplice e “veloce” dacalcolare, possibilmente dipendente da campi della classe



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Il metodo hashCode()

Contratto di Object.hashCodeIl metodo hashCode deve produrre lo stesso numero anchequando invocato piu volte sullo stesso oggetto. Se due oggettisono uguali in accordo al metodo equalk(Object o), allora ilmetodo hashCode invocato su entrambi gli oggetti deveprodurre lo stesso numero. Non e richiesto che oggetti diversiproducano codici hash distinti

Osservazioni: normalmente questo contratto viene disatteso!Per usare HashSet e fondamentale osservarlo!Regola: si deve sovrascrivere hashCode() in tutte le classiove viene sovrascritto equalk(Object o)



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Esempi di codici hash

...System.out.println("cane".hashCode());System.out.println("cane".hashCode());System.out.println("gatto".hashCode());Quadrato q = new Quadrato(1);System.out.println(q.hashCode());q = new Quadrato(1);System.out.println(q.hashCode());q = new Quadrato(2);System.out.println(q.hashCode());Persona p = new Persona("Paolo","Rossi");System.out.println(p.hashCode());p = new Persona("Paolo","Rossi");System.out.println(p.hashCode());p = new Persona("Paola","Rossi");System.out.println(p.hashCode());...



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Stampa dei Risultati

Esecuzione del metodo main della classe HashCodeEx:

HashCode di: "cane" -> 3046037HashCode di: "cane" -> 3046037HashCode di: "gatto" -> 98127573HashCode di: Quadrato(1) -> 19972507 //non definitoHashCode di: Quadrato(1) -> 7754385 //non definitoHashCode di: Quadrato(2) -> 2548785 //non definitoHashCode di: Persona("Paolo","Rossi") -> -1832489941HashCode di: Persona("Paolo","Rossi") -> -1832489941HashCode di: Persona("Paola","Rossi") -> -1832490375



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Uso di HashSet

ProblemaUsare la classe HashSet (TreeSet) per trovare le paroleduplicate in una stringa passata come argomento sulla linea dicomando

>java TrovaDuplicati ciao mamma ciao

Duplicati: ciao2 parole distinte: [mamma, ciao]

Duplicati: ciao2 parole distinte (ordinate): [ciao, mamma]



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Esempio

import java.util.*;

class TrovaDuplicati {public static void main(String args[]) {

Set<String> s = new HashSet<String>();for (String a : args)

if (!s.add(a))System.out.println("Duplicati: " + a);

System.out.println(s.size() + " parole distinte: " + s);

s = new TreeSet<String>();for (String a : args)

if (!s.add(a))System.out.println("Duplicati: " + a);

System.out.println(s.size() + " parole distinte (ordinate): " + s);}

}



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Indice

1 Le Collezioni (Java Collections)Modellare liste e insiemiEsempi di ListeScansione: for-each e IteratoriEsempi di insiemiMappe



Esempi di liste

Scansione

Esempi di insiemi

Mappe

L’interfaccia Mappa

public interface Map<K,V> {// Operariona�ZYk]V put(K key, V value);V get(Object key);V remove(Object key);boolean containsKey(Object key);boolean containsValue(Object value);int size();boolean isEmpty();// Operariona�km�afka]eavoid putAll(Map<? extends K,? extends V> t);void clear();

// Collezionipublic Set<K> keySet();public Collection<V> values();public Set<Map.Entry<K,V>> entrySet();



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Mappe

Map Un gruppo di coppie di oggettichiave-valore. Una Map puorestiluire un Set di chiavi, unaCollection di valori o un Setdelle sue coppie.Idea: associare oggetti (chiave) aoggetti (valore), invece diassociare numeri a oggetti (comeArrayList) HashMap

Map



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Uso di HashMap

ProblemaUsare la classe HashMap (TreeMap) per calcolare leoccorrenze di ogni singola parola�ljY�d]� stjaf_`] passat]�[ge]argomento sulla linea di comando

>java FrequenzaParole ciao mamma ciao

2 parole distinte:{mamma=1, ciao=2}

2 parole distinte (ordinate):{ciao=2, mamma=1}



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Esempio

public class FrequenzaParole {public static void main(String args[]) {

Map<String, Integer> m = new HashMap<String, Integer>();for (String a : args) {

Integer freq = m.get(a);m.put(a, (freq == null ? 1 : freq + 1));

}System.out.println(m.size() + " parole distinte:");System.out.println(m);

m = new TreeMap<String, Integer>();for (String a : args) {

Integer freq = m.get(a);m.put(a, (freq == null ? 1 : freq + 1));

}System.out.println(m.size() + " parole distinte:");System.out.println(m);

}}



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Problema

ProblemaScrivere un programma che mostri la pseudo casualita delgeneratore di numeri casuali implementato nella classejava.util.Random utilizzando la classe Contatore percontare le occorrenze dei numeri.

Metodo: genero molti (10000) numeri nell’intervallo [1, 10] emostro la frequenza con cui si manifestano, quindi stampo lacoppia (numero, frequenza)



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Risultato

>java DistUniformeDemoFrequenze di 10000 numeri (tra 1 e 10) generati a caso:

[1=974, 2=1000, 3=954, 4=1010, 5=993, 6=1049, 7=996,8=1000, 9=977, 10=1037]



Esempi di liste

Scansione

Esempi di insiemi

Mappe

Problema con mappe ordinate per chiave

ProblemaScrivere un programma che gestisca una rubrica telefonica:una chiave (ordinabile), per es. cognome e un valore per es.Persona.Si consiglia l’uso di java.util.TreeMap

Le Collezioni (Java Collections) - Intranet...

Documents

Transcript of Le Collezioni (Java Collections) - Intranet...