Fondamenti di Informatica 1
Fondamenti di Informatica 1
Java Collection Framework
Facoltà di Ingegneria dell’Informazione, Informatica e
Statistica
Fondamenti di Informatica 1
Java Collection Framework
Il JCF è un’architettura unificata per
rappresentare e manipolare collezioni di dati.
Nel JCF troviamo:
•
•
•
Interfacce: definiscono insiemi di funzionalità
Classi: definiscono insiemi di realizzazioni delle
suddette interfacce
Metodi: per rispondere a problemi di carattere
generale
Quadro di sintesi del JCF
Collection
Set
SortedSet
List
Fondamenti di Informatica 1
Map
Queue (java 5)
SortedMap
Collection: nessuna ipotesi sulla presenza di elementi duplicati orelazioni
d’ordine
List:
introduce il concetto di sequenza
Set:
introduce il concetto di insieme matematico (quindi, senza
elementi duplicati)
SortedSet: introduce un ordinamento nell'insieme dei valori
Map:
realizza le mappe di corrispondenza <chiave,valore>
SortedMap: introduce un ordinamento nella mappa di corrispondenze
Fondamenti di Informatica 1
Iterator
Un iterator o iteratore è uno strumento che facilita la
navigazione all’interno della collezione attraverso
l’interfaccia:
public interface Iterator {
boolean hasNext();
Object next();
void remove(); // opzionale
}
• il metodo next() permette di scorrere uno ad uno
gli elementi della collezione;
• il metodo hasNext() permette di verificare
quando non ci sono più elementi
Fondamenti di Informatica 1
Realizzazioni
Una classe della collezione
• realizza un ADT
• fornisce implementazione di tutti i metodi
dell’interfaccia
Le interfacce Java sono:
Liste (List): ArrayList, LinkedList, Vector
Mappe (Map): HashMap, TreeMap
Insiemi (Set): TreeSet, HashSet
Fondamenti di Informatica 1
Metodi
Java realizza dei metodi per rispondere a
problemi comuni sulle collezioni di dati:
• ordinamento (e.g. sort)
• cambio di posizione (e.g. shuffle)
• manipolazioni varie (e.g. reverse, addAll)
• ricerca (e.g. binarySearch)
• composizione (e.g. frequency)
• ricerca degli estremi (e.g. max, min,..)
Fondamenti di Informatica 1
Liste e mappe
La lista implementa il concetto di multiinsieme:
possono esistere due elementi identici
La mappa memorizza coppie <chiave,valore>
(non possono esistere chiavi duplicate)
La lista
Fondamenti di Informatica 1
Una lista è
• una collezione di elementi (numeri,
stringhe, oggetti,…)
• ordinati (in sequenza): c’è sempre un
elemento in testa ed uno in coda (se la
lista non è vuota)
La lista può essere vuota.
Fondamenti di Informatica 1
LinkedList, ArrayList e Vector
Sono classi concrete che realizzano la lista e
memorizzano una collezione di qualsiasi
genere di oggetti.
Gli oggetti possono essere dello stesso tipo, o
di tipo differente, con funzionamento analogo
agli array.
Mentre la classe LinkedList utilizza una
struttura collegata, ArrayList e Vector
utilizzano internamente un array. In questo
modo “ereditano” tutti i vantaggi e gli
svantaggi delle strutture dati utilizzate.
Esempio
Fondamenti di Informatica 1
import java.util.*;
public class Prova {
public static void main(String[] args ){
// interfaccia List
// tre classi che realizzano l’interfaccia List:
List<String> listaAL= new ArrayList<String>();
List<String> listaLL = new LinkedList<String>();
List<String> listaV = new Vector<String>();
// il metodo add()
listaAL.add(“elemento in array list");
listaLL.add(“elemento in linked list");
ListaV.add(“elemento in vector");
// il metodo get()
System.out.println(listaAL.get(0));
System.out.println(listaLL.get(0));
System.out.println(listaV.get(0));
}}
Fondamenti di Informatica 1
Generics
Una Lista può essere utilizzata per memorizzare
oggetti generici (es. ContoCorrente)
List<ContoCorrente> listaCC= new ArrayList<ContoCorrente>();
listaCC.add(new ContoCorrente ("Alex", "100A", 111));
listaCC.add(new ContoCorrente (“Max", "200B", 222));
listaCC.add(new ContoCorrente ("Pippo", "100B", 333));
System.out.println(listaCC.get(2).getSaldo());
333
Fondamenti di Informatica 1
Iteratori
Gli Iterator forniscono un modo generale per
attraversare gli elementi della collezione
ArrayList<String> lista = new ArrayList<String>();
lista.add(“PRIMO");
lista.add(“SECONDO");
lista.add(“TERZO");
Iterator<String> itr = lista.iterator();
while (itr.hasNext()) {
System.out.println(itr.next());
}
PRIMO
SECONDO
TERZO
Fondamenti di Informatica 1
Cicli con definizione avanzata
Se una classe estende Iterable<E> (come abbiamo
fatto con la classe Set<E>), si può utilizzare la sintassi
avanzata nei loop:
for (E rifer : collection<E> ) {
rifer = riferimento ad ogni elemento della collezione
collection<E>
}
Esempio
ArrayList<String> lista = new ArrayList<String>();
lista.add(“PRIMO");
for (String s : lista)
System.out.println(s.toLowerCase());
PRIMO
Fondamenti di Informatica 1
Map e SortedMap
L’interfaccia Map definisce i metodi:
get(), put(), contains(), keySet(), values(),
entrySet()
TreeMap realizza Map ed implementa i metodi:
put(), get(), remove()
HashMap realizza Map ed implementa i metodi:
put(), get(), remove()
Fondamenti di Informatica 1
Set e SortedSet
Alcuni metodi Map restituiscono Set
L’interfaccia Set ha i seguenti metodi:
add(), addAll(), remove(), size(), toArray(),
…ma non c’è get()!
TreeSet: i valori sono memorizzati in ordine
e la complessità computazionale relativa
all’operazione di ricerca è O(log n)
HashSet: i valori sono memorizzati in
una tabella hash, la complessità è O(1)
Fondamenti di Informatica 1
Esercizio
Costruire una collezione di oggettierrore
ContoCorrente
(proprietario, numero e saldo) utilizzando una mappa.
Esercizio
Fondamenti di Informatica 1
import java.util.*;
public class ContoCorrente {
String numCC,nome;
int saldo;
public ContoCorrente (String nome, String numCC, int saldo){
this.nome=nome;
this.saldo=saldo;
Saldo totale=666.0
this.numCC=numCC;
Saldo di Alex=111
}
public int getSaldo(){return saldo;}
public static void main(String[] args ){
Map<String, ContoCorrente> tm=
new TreeMap<String,ContoCorrente>();
tm.put("Alex", new ContoCorrente("Alex", "100A", 111));
tm.put("Max", new ContoCorrente("Max", "200B", 222));
tm.put("Pippo", new ContoCorrente("Pippo", "100B", 333));
Collection<ContoCorrente> collezioneCC= tm.values();
double saldoTot = 0.0;
for (ContoCorrente cc : collezioneCC ) {
saldoTot += cc.getSaldo();
}
System.out.println("Saldo totale="+saldoTot);
System.out.println("Saldo di Alex="+tm.get("Alex").getSaldo());
} }
Valori in un TreeMap
Fondamenti di Informatica 1
Collection<ContoCorrente> collezioneCC= tm.values();
Iterator<ContoCorrente> iter = collezioneCC.iterator();
double saldoTot = 0.0;
while (iter.hasNext()) {
saldoTot += iter.next().getSaldo();
}
Chiavi in un TreeMap
Set<String> chiavi= tm.keySet();
// il metodo keySet() restituisce (in ordine) le chiavi
memorizzate nella mappa
Fondamenti di Informatica 1
Il metodo entrySet()
// La corrispondenza
Collection<Entry<String, ContoCorrente>> collezione = tm.entrySet();
Iterator<Entry<String, ContoCorrente>> iter2 = collezione.iterator();
while (iter2.hasNext()) {
System.out.print("<" +iter2.next().toString() + "> ");
}
<A=Alex 100A $111> <M=Max 200B $222> <P=Pippo 100B $333>
Interfaccia Collection
•add(o)
•addAll(c)
•clear()
•contains(o)
•containsAll(c)
•isEmpty()
•iterator()
•remove(o)
•removeAll(c)
•size()
Fondamenti di Informatica 1
aggiunge un nuovo elemento
aggiunge una collezione
rimuove tutti gli elementi
verifica se un elemento è
contenuto
controllo di inclusione (tutti gli
elementi sono contenuti nella
collezione?)
true se è vuota
restituisce un iteratore
elimina un elemento
rimuove una collezione
la dimensione della collezione
Interfaccia List
•add(pos,oggetto)
•add(oggetto)
•get(pos)
•remove(pos)
•set(pos,oggetto)
inserisce alla posizione pos
accoda l’oggetto
restituisce l’elemento in posizione pos
elimina l’elemento in posizione pos
sostituisce l’elemento in posizione pos
con l’oggetto
•indexOf(oggetto)
•lastIndexOf(oggetto)
•listIterator()
•sublist(inizio,fine)
Fondamenti di Informatica 1
Interfaccia Map
clear()
containsKey(chiave)
containsValue(valore)
entrySet()
get(chiave)
isEmpty()
keySet()
put(chiave,valore)
remove(chiave)
size()
values()
Fondamenti di Informatica 1
rimuove tutte le corrispondenze
verifica se una chiave è nella mappa
verifica se esiste una chiave per il
valore indicato
restituisce il Set delle coppie
<chiave, valore>
restituisce il valore di una chiave
restituisce se la mappa è vuota
restituisce il Set delle chiavi
associa alla chiave il valore
rimuove la corrispondenza per la
chiave
restituisce il numero delle coppie
restituisce la collezione dei valori
Collezioni concrete
Fondamenti di Informatica 1
Classe
Concreta
realizzazione di Descrizione
HashSet
TreeSet
ArrayList
LinkedList
Vector
HashMap
TreeMap
Hashtable
Set
SortedSet
List
List
List
Map
SortedMap
Map
tabella hash
albero binario bilanciato
array ridimensionabile
Lista collegata
array ridimensionabile
tabella hash
albero binario bilanciato
tabella hash
Fondamenti di Informatica 1
Utilizzo della classe HashSet
Set insiemeHS= new HashSet(); // instantiate a concrete set
...
insiemeHS.add(oggetto); // inserisce un elemento
...
int n = set.size(); // ottiene la dimensione
...
if (set.contains(oggetto)) {
//controlla se un elemento è contenuto
}
// utilizzo dell’iteratore
Iterator iter = insiemeHS.iterator();
while (iter.hasNext()) {
Object oggetto = iter.next();
// ricordare di eseguire il downcast
...
}
Fondamenti di Informatica 1
Utilizzo della classe HashMap
Map mappaHM = new HashMap();
mappaHM.put(chiave, valore); // inserisce una coppia <chiave,valore>
Object valore = mappaHM.get(chiave);
// ricerca il valore di una chiave
mappaHM.remove(chiave); // elimina una chiave
if (mappaHM.containsValue(valore)) { ... }
if (mappaHM.containsKey(chiave)) { ... }
Set chiavi = mappaHM.keySet();
//ottiene l’insieme delle chiavi contenute nella mappa
Iterator iter = chiavi.iterator(); // itera nell’insiem delle chiavi
while (iter.hasNext()) {
Key chiave = (Key) iter.next();
}
Fondamenti di Informatica 1
Esercizio
Scrivere un metodo per contare leerrore
parole all’interno di
una frase letta in input rispetto al numero di parole
distinte.
Suggerimento
1) Utilizzare la classe StringTokenizer e i metodi
hasMoreTokens() e nextToken()
StringTokenizer st = new StringTokenizer(frase, delimitatore);
while (st.hasMoreTokens()) {...parola=st.nextToken(); ...}
Esercizio
Fondamenti di Informatica 1
public class ContaParole {
static public void main (String[] args) {
Set parole= new HashSet();
BufferedReader in = new BufferedReader(
new InputStreamReader(System.in));
String delimitatore = " \"\'\t\n.,:;?()!-/ []”;
String frase;
int conta = 0;
try {
while ((frase= in.readLine()) != null) {
StringTokenizer st = new StringTokenizer(frase,delimitatore);
while (st.hasMoreTokens()) {
conta++;
parole.add(st.nextToken().toLowerCase());
}
}
} catch (IOException e) {}
System.out.println(“Numero di parole inserite:"+ conta);
System.out.println(“Numero di parole distinte: "+parole.size());
}
}
Ordinamento e confronti
Fondamenti di Informatica 1
Esistono due modi per definire un criterio di ordinamento:
1) Ogni classe può definire un ordinamento naturale tra le
sue istanze implementando l’interfaccia Comparable
int compareTo(Object o)
2) In modo arbitrario tra gli oggetti utilizzando
comparators e le classi che realizzano l’interfaccia
Comparator.
int compare(Object o1, Object o2)
Fondamenti di Informatica 1
Ordinamento definito dall’utente
Ordinamento inverso
public class StringComparator implements Comparator {
public int compare(Object o1, Object o2) {
if (o1 != null && o2 != null &&
o1 instanceof String &&
o2 instanceof String) {
String s1 = (String) o1;
String s2 = (String) o2;
return - (s1.compareTo(s2));
} else {
return 0;
}
}
}
Fondamenti di Informatica 1