danilo.pianini@unibo.itgianluca.aguzzi@unibo.itangelo.filaseta@unibo.itCompiled on: 2025-12-05 — versione stampabile
Arrays e CollectionsSet, List e Mapjava.utilCollection – contenitore di elementi atomici; 2 sottotipi di collezioni
List (sequenze)Set (no duplicazioni)Map – contenitore di coppie chiave-valore (memoria associativa)Collection, List, Set, Map, Iterator, ComparableArrayList, LinkedList, HashSet, TreeSet, HashMapCollections, ArraysUn meccanismo usato per gestire eventi ritenuti fuori dalla normale esecuzione (errori), ossia per dichiararli, lanciarli, intercettarli
for (final var i: array) { ... }
java.lang.Iterable<X>Iterable e IteratorIterable (contratto degli oggetti iterabili) ha un metodo per generare e restituire un (nuovo) Iteratornext(), hasNext() (e remove()), che può quindi iterare su una collezione una sola volta
Iterablecollection che implementa Iterable<T> allora il foreach diventa:for (final T element: collection) { ... }
// o, equivalentemente:
for (final var element: collection) { ... }
package java.lang;
import java.util.Iterator;
public interface Iterable<T> {
/**
* Returns an iterator over a set of elements of type T.
*
* @return an Iterator.
*/
Iterator<T> iterator();
}
package java.util;
public interface Iterator<E> {
boolean hasNext();
E next();
void remove(); // throws UnsupportedOperationException
}
package java.util;
public interface Collection<E> implements Iterable<E> { .. }
import java.util.*;
public class UseCollectionIterator {
static void main() {
// Uso la LinkedList
final List<Double> list = new LinkedList<>();
// Inserisco 50 elementi
for (int i = 0; i < 50; i++) {
list.add(Math.random());
}
// Stampo con un foreach
int count = 0;
for (final double d: list) {
System.out.println(++count + " " + d);
}
// 1 0.10230513602737423
// 2 0.4318582138894327
// 3 0.5239222319032795
// ..
}
}
Collection<E> (implementa Iterable<E>)List e Set)Collection, dal quale prende tutti gli elementiUnsupportedOperationExceptionc.contains(o)) lavorano sulla base del metodo Object.equals() da chiamare sugli elementi
Object, influendo su alcuni metodi di CollectionCollection: estratto dell’interfacciapublic interface Collection<E> extends Iterable<E> {
// Query Operations
int size(); // number of elements
boolean isEmpty(); // is the size zero?
boolean contains(Object o); // does it contain an element equal to o?
Iterator<E> iterator(); // yields an iterator
Object[] toArray(); // convert to array of objects
<T> T[] toArray(T[] a); // puts in `a`, or create new if too small
// Modification Operations
boolean add(E e); // adds e
boolean remove(Object o); // remove one element that is equal to o
// Bulk Operations
boolean containsAll(Collection<?> c); // contain all elements in c?
boolean addAll(Collection<? extends E> c); // add all elements in c
boolean removeAll(Collection<?> c); // remove all elements in c
boolean retainAll(Collection<?> c); // keep only elements in c
void clear(); // remove all element
// ...and other methods introduced in Java 8
}
Arrays.asList(), metodo statico che converte un array in una ListCollection.toArray(), metodo istanza che converte una collezione in un arraypackage it.unibo.collections.collection;
import java.util.*;
public class UseCollection {
static void main() {
// Uso ArrayList come implementazione, ma dichiaro e uso l'interfaccia
final Collection<Integer> coll = new ArrayList<>();
coll.addAll(Arrays.asList(1, 3, 5, 7, 9, 11)); // var-args
System.out.println(coll); // [1, 3, 5, 7, 9, 11]
coll.add(13); // Invocazione di metodi dell'interfaccia Collection
coll.add(15);
coll.add(15);
coll.remove(7);
System.out.println(coll); // [1, 3, 5, 9, 11, 13, 15, 15]
coll.removeAll(Arrays.asList(11, 13, 15));
coll.retainAll(Arrays.asList(1, 2, 3, 4, 5));
System.out.println(coll); // [1, 3, 5]
System.out.println(coll.contains(3)); // true
System.out.println(Arrays.toString(coll.toArray()));
final var a = coll.toArray();
System.out.println(Arrays.deepToString(a));
}
}
.of(...) e .copyOf(c) su List, Set, …
Arrays.asList visto precedentemente, invece, crea una lista mutabile (e consente valori null)public class UseFactories {
public static void main(String[] s) {
// Metodi statici di creazione per Set e List *immutabili*
final Set<Integer> set = Set.of(1, 2, 3, 4, 5, 6);
System.out.println(set);
final List<String> list = List.of("a", "b", "c", "a");
System.out.println(list);
final var set2 = Set.copyOf(list);
System.out.println(set2);
// set2.add("d"); // UnsupportedOperationException
System.out.println(list.hashCode());
}
}
Set e List: introduzioneSetObject.equals() a dare truenullCollectionListLa scelta fra queste due tipologie non dipende da motivi di performance, ma da quale modello di collezione serva!
Set e List: interfaccepublic interface Set<E> extends Collection<E> { }
public interface List<E> extends Collection<E> {
// Additional Bulk Operations
boolean addAll(int index, Collection<? extends E> c);
// Positional Access Operations
E get(int index); // get at position index
E set(int index, E element); // set into position index
void add(int index, E element); // add, shifting others
E remove(int index); // remove at position index
// Search Operations
int indexOf(Object o); // first equals to o
int lastIndexOf(Object o); // last equals to o
// List Iterators (enable traversal in both directions, modifications etc.)
ListIterator<E> listIterator(); // iterator from 0
ListIterator<E> listIterator(int index); // ..from index
// View
List<E> subList(int fromIndex, int toIndex);
}
void m(final List<Integer> lst) {
// Dichiaro Set, non HashSet o altra implementazione, e istanzio una sua implementazione
final Set<String> names = new LinkedHashSet<>();
}
new, a parte casi molto particolariSetSetObject.equals())Set possono avere prestazioni miglioriObject.hashCode() come funzione di hash,
usata per posizionare gli elementi in uno store di elevate dimensioniLinkedHashSet e HashSetLinked ha ordine di iterazione predicibile (quello degli elementi inseriti)TreeSetComparable, oppure che venga fornito un ComparatorLinked)HashSetObject.hashCode())sizee
e.hashCode() % sizef
f.hashCode() % size, usando Object.equals()HashMap, che approfondiremo in futuroHashSetpublic class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
// Set vuoto, usa hashmap con capacità 16
public HashSet() {...}
// Set con elementi di c, usa hashmap del 25% più grande di c
public HashSet(Collection<? extends E> c) {...}
// Set vuoto
public HashSet(int initialCapacity, float loadFactor) {...}
// Set vuoto, loadFactor = 0.75
public HashSet(int initialCapacity) {...}
/* Gli altri metodi di Collection seguono... */
}
equals() e hashCode()Object uguaglia lo stesso oggetto e l’hashing restituisce la posizione in memoria..equals() e hashCode() opportunamenteequals devono avere lo stesso hashCodeHashSethashCode() sfruttando il metodo di libreria
Objects.hash(Object...)
equalsdjb2, murmur3)TreeSet<E>Comparable
Integer implementa Comparable<Integer>Comparator esterno fornito alla newTreeSetpublic interface Comparable<T> {
/*
* returns:
* 0 if this is equal to other
* positive int (1 is preferred) if this > other
* negative int (-1 is preferred) if this < o
*/
public int compareTo(T other);
}
Consente di definire una nozione di ordine naturale sugli oggetti di una classe
Pre-implementato in molte classi di libreria (più di 100!)
class Integer extends Number implements Comparable<Integer> { ... }
class String extends Object implements Comparable<String>, ... { ... }
Implementabile in modo personalizzato nelle nostre classi
public class Person implements Comparable<Person> {
private final int birthYear;
private final String surname;
/*
* Sort by year, and if they are equal by name
*/
public int compareTo(final Person other) {
final var byYear = this.birthYear > other.birthYear ? 1 : (this.birthYear < other.birthYear ? -1 : 0);
// Alternatively, just:
// final var byYear = Integer.compare(this.birthYear, other.birthYear)
return byYear == 0 ? this.name.compareTo(other.name) : byYear;
}
}
// String implements Comparable<String>
final var internal = new TreeSet<String>();
internal.add("zzz");
internal.add("lll");
internal.add("aaaaa");
internal.add("10");
internal.add("2");
// String uses lexicographical ordering!
System.out.println(internal); // [10, 2, aaaaa, lll, zzz]
Se a una collezione ordinata non è fornito un Comparator esterno specifico,
allora sfrutterà l’ordinamento naturale del tipo degli elementi
(quindi se il tipo T degli elementi non implementa Comparable<? super T>, un’eccezione verrà sollevata)
Va passato un comparatore personalizzato (una classe che implementa Comparator), due casi d’uso:
Comparablepublic class StringByLength implements Comparator<String> {
// Sort by length, then lexicographically
public int compare(final String s1, final String s2) {
final var byLength = Integer.compare(s1.length(), s2.length());
return byLength == 0 ? s1.compareTo(s2) : byLength;
}
}
final var external = new TreeSet<String>(new StringByLength());
external.add("zzz");
external.add("lll");
external.add("aaaaa");
external.add("10");
external.add("2");
// Custom ordering!
System.out.println(external); // [2, 10, lll, zzz, aaaaa]
Comparator<? super E> (Approfondimento)Data una classe SortedSet<E> il suo comparatore ha tipo Comparator<? super E>, perché non semplicemente Comparator<E>?
Comparator ha metodi che hanno E solo come argomentoComparator<? super E> è una generalizzazione contravariante di Comparator<E>
Comparator<in E>:
Comparator che accetta oggetti di tipo E in inputComparator che non restituisce mai oggetti di tipo EPerson, e che questo sia usabile anche per tutte le specializzazioni successivamente costruite (è la situazione tipica)SortedSet<Student> deve poter usare il Comparator<Person>!
Comparator<? super E>
Comparator<Person> a un SortedSet<Student>ListListpublic interface List<E> extends Collection<E> {
// Additional Bulk Operations
// aggiunge gli elementi in pos. index
boolean addAll(int index, Collection<? extends E> c);
// Positional Access Operations
E get(int index);
E getFirst();
E getLast();
E set(int index, E element);
void add(int index, E element);
E remove(int index);
// Search Operations
int indexOf(Object o); // basato su Object.equals
int lastIndexOf(Object o); // basato su Object.equals
// List Iterators
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
// View
List<E> subList(int fromIndex, int toIndex);
}
ListArrayListLinkedListArrayListadd() è tempo costante ammortizzato, ossia, $n$ add si effettuano in $O(n)$Per migliorare le performance (e l’occupazione in memoria) in taluni casi l’utente esperto può usare funzioni aggiuntive
newtrimToSize() e ensureCapacity() per modifiche in itinereLinkedListlista doppiamente linkata (che può essere traversata dall’inizio o dalla fine)
ArrayListArrayList)Deque,
usata per rappresentare una coda bidirezionale
(double-ended queue), potenzialmente con dimensione limitataArrays e CollectionsArrays e Collectionsjava.util.ArraysbinarySearch()), ordinamento (quicksort, sort()), copia (copyOf()), riempimento (fill())toString, equals, hashCode), anche ricorsivejava.util.CollectionsArrays: qualche esempio di metodi
public class Arrays {
public static void sort(Object[] a, int fromIndex, int toIndex) {...}
public static <T> void sort(T[] a, Comparator<? super T> c) {...}
...
public static int binarySearch(int[] a, int key) {...}
public static int binarySearch(char[] a, char key) {...}
public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c) {...}
...
public static <T> List<T> asList(T... a) {...}
public static <T> T[] copyOfRange(T[] original, int from, int to) {...}
public static void fill(Object[] a, int from, int to, Object val) {...}
public static boolean deepEquals(Object[] a1, Object[] a2) {...}
public static int deepHashCode(Object a[]) {...}
public static String deepToString(Object[] a) {...}
public static String toString(long[] a) {...}
public static String toString(int[] a) {...}
public static String toString(Object[] a) {...}
}
Collections: qualche esempio di metodi// nota: tutti metodi public static!!
public class Collections {
// ordinamenti e varie
<T extends Comparable<? super T>> void sort(List<T> list) {...}
<T> void sort(List<T> list, Comparator<? super T> c) {...}
<T> int binarySearch(List<? extends Comparable<? super T>> list, T key)
<T> T min(Collection<? extends T> coll, Comparator<? super T> comp)
// modifiche
void reverse(List<?> list) {...}
void shuffle(List<?> list) {...}
<T> void fill(List<? super T> list, T obj) {...}
<T> void copy(List<? super T> dest, List<? extends T> src) {...}
// letture varie
int indexOfSubList(List<?> source, List<?> target) {...}
boolean disjoint(Collection<?> c1, Collection<?> c2) {...}
int frequency(Collection<?> c, Object o) {...}
// costruzioni di collezioni
<T> List<T> emptyList() {...}
<T> Set<T> emptySet() {...}
<T> List<T> nCopies(int n, T o) {...}
<T> Set<T> singleton(T o) {...}
<T> List<T> singletonList(T o) {...}
}
java.util.MapMap<K,V>K in VObject.equals)public interface Map<K,V> {
// Query Operations
int size();
boolean isEmpty();
boolean containsKey(Object key); // usa Object.equals
boolean containsValue(Object value); // usa Object.equals
V get(Object key); // accesso a valore
// Modification Operations
V put(K key, V value); // inserimento chiave-valore
V remove(Object key); // rimozione chiave(-valore)
// Bulk Operations
void putAll(Map<? extends K, ? extends V> m);
void clear(); // cancella tutti
// Views
Set<K> keySet(); // vista sul set dei valori
Collection<V> values(); // vista sulla collezione di chiavi
}
MapHashMapHashSet di coppie Key, ValueLinkedHashMapTreeMapTreeSet di coppie Key, ValueTreeSetpackage it.unibo.collections.generic.map;
import java.util.LinkedHashMap;
import java.util.Map;
public class UseMap {
static void main() {
// Dichiaro l'interfaccia, istanzio un'implementazione concreta
final Map<Integer, String> map = new LinkedHashMap<>();
map.put(345211, "Bianchi");
map.put(345122, "Rossi");
map.put(243001, "Verdi");
System.out.println(map); // {345211=Bianchi, 243001=Verdi, 345122=Rossi}
map.put(243001, "Neri"); // Rimpiazza Verdi
final Map<String,Integer> map2 = Map.of("foo", 5, "bar", 7);
for(final Map.Entry<String,Integer> entry: map2.entrySet()) { // modo prestante per accedere alle coppie
System.out.println("Chiave: " + entry.getKey() + ", Valore: " + entry.getValue());
}
for (final int i: map.keySet()) { // modo per accedere alle sole chiavi
System.out.println("Chiave: " + i);
}
for (final String s: map.values()) { // modo per accedere ai soli valori
System.out.println("Valore: " + s);
}
}
}
danilo.pianini@unibo.itgianluca.aguzzi@unibo.itangelo.filaseta@unibo.itCompiled on: 2025-12-05 — versione stampabile