Contenitori

Materiale http://math.hws.edu/eck/cs124/javanotes7/c10/

Le interfacce principali delle colllezioni

Le interfacce e le classi che tratteremo per gestire collezioni di oggetti in Java e che fanno parte delle classi standard del linguaggio Java, fanno parte del package java.util.

Tipi generici nelle collezioni

Se vogliamo costruire una collezione di istanze di Shape, noi possiamo usare List per contenerle:

List shapes = new ArrayList(); // Create a List to hold shapes

// Create some centered shapes, and store them in the list
shapes.add(new CenteredCircle(1.0, 1.0, 1.0));

// This is legal Java—but is a very bad design choice
shapes.add(new CenteredSquare(2.5, 2, 3));

// List::get() returns Object, so to get back a
// CenteredCircle we must cast
CenteredCircle c = (CentredCircle)shapes.get(0);

// Next line causes a runtime failure
CenteredCircle c = (CentredCircle)shapes.get(1);

In questo modo abbiamo utilizzato le classi delle collezioni, senza fruttare il fatto che le collezioni sono dei tipi parametrici. Si dice utilizzando i tipo raw (grezzo) della collezione in questo caso l'ArrayList. Questo è possibile (è il vecchio modo, come venivano utilizzate le classi delle collezioni), ma notate i cast espliciti che devono essere eseguiti nelle operazioni di get() in quanto ritornano il tipo Object.

Come già detto, l'operazione di cast espicito, viene controllata a run time, in fase di esecuzione e non in compilazione: se il cast non è corretto viene sollevata l'eccezione ClassCastException. (vedi esempio sopra, riga 15).

Per oviare a quasto problema, sono stati introdotti i tipi parametrici e in particolare il loro utilizzo nelle classi del Java Collection Framework (classi contenitore).

// Create a List-of-CenteredCircle
List<CenteredCircle> shapes = new ArrayList<CenteredCircle>();

// Create some centered shapes, and store them in the list
shapes.add(new CenteredCircle(1.0, 1.0, 1.0));

// Next line will cause a compilation error
shapes.add(new CenteredSquare(2.5, 2, 3));

// List<CenteredCircle>::get() returns a CenteredCircle, no cast needed
CenteredCircle c = shapes.get(0);

Ora è possibile eseguire il controllo in fase di compilazione e non sono più necessati i cast espliciti del tipo di ritorno delle operazioni di get.

JAVA COLLECTION FRAMEWORK

Una struttura generica di dati del Java Collection Framework può essere divisa in due categorie: collections e maps.

Una collections è più o meno, quello che richiama la parola: una collezione di oggetti. Una map associa oggetti di un insieme con oggetti di un altro, nello stesso modo in cui un dizionario associa le definizioni alle parole o un'agenda telefonica associa i numeri di telefono ai nomi di persone.

Una map è simile a quella che abbiamo visto come lista associativa.

I Java le collezioni e le map sono rappresentati da due interfacce, Collection<T> e Map<T,S>. Qui "T" e "S" stanno per qualiasi tipo eccetto, i tipi primitivi.

Ci sono poi due tipi di collections: lists e sets.

Una list è una collection in cui gli oggetti sono organizzati in una sequenza lineare. Una lista ha il primo elemento, il secondo e così via. Per ogni elemento della lista, escluso l'ultimo, c'è un elemento che lo segue.

Per le collezioni che sono di tipo set, la loro caratteristica, è che nessun oggetto, ci può essere più di una volta nel set; gli elementi del set non sono pensati necessariamente di essere in un qualsiasi ordine particolare.

Le idee di list e set, sono rappresentate da due interfacce List<T> e Set<T>. Queste sno sottointerfacce di Collection<T>. Quindi, se un oggetto implementa l'interfaccia List<T> o Set<T> autometicamente implementa l'interfaccia Collection<T>. L'interfaccia Collection<T> specifica operazioni generali. che possono essere applicate a tutte le collezioni. List<T> e Set<T>, aggiungono operazioni addizionali che sono appropriate le le liste e i set, rispettivamente.

Certamente, ogni oggetto che è una collezione, list o set, deve appartenere a una classe concreta che implementa la corrispondente interfaccia. Per esempio, la classe ArrayList<T> implementa l'interfaccia List<T> e quindi implementa Collection<T>. Questo significa che tutti i metodi che sono definiti nelle interfacce list e collection possono essere utilizzati con l'ArrayList.

Vediamo ora i metodi disponibili in tutte le collezioni e poi vedremo le classi che implementano concretamente le interfacce List<T> e Set<T>.

L'interfaccia Collection<T> specifica i metodi per avere delle operazioni di base su tutte le collezioni di oggetti:

• coll.size()

• coll.isEmpty()

• coll.clear()

• coll.add( tobject)

• coll.contains(object)

• coll.remove(object)

• coll.containsAll(coll2)

• coll.addAll(coll2)

• coll.removeAll(coll2)

• coll.retainAll(coll2)

• coll.toArray()

Siccome questi metodi sono parte dell'interfaccia Collection<T>, devono essere definiti per ogni oggetto che implementa questa interfaccia. C'è un problema in questo, tuttavia. Per esempio, la dimensione di alcune collezioni non può essere cambiata dopo che sono state create. Metodi per aggiungere o rimuovere un elemento da queste collezioni, non ha senso. Sebbene su queste collezioni si possono chiamare questi metodi. a runtime viene sollevata l'eccezione UnsupportedOperationException.

C'è anche una questione di efficienza. Anche se un'operazione è definita per diversi tipi di collezione, non sono egualmente efficienti per ogni tipo di collezione. Es operazione di add di un oggetto su collezioni di ArrayList e LinkedList.

Anche il metodo size() può variare di molto per tipo di collezione, per alcune può significare contare gli elementi della collezione. Il numero di passi in questo caso è equivalente agli elementi della collezione.

Altre tipi di collezione possono invece avere una variabile d'istanza che mantiene il calore della size e quindi invocare il metodo size() ritorna il valore della variabile.

Quando si lavora con le collezioni, è una buona idea avere contezza di quanto è efficiente un'operazione e scegliere anche in base a questo l'implementazione più appropriata.

Vedi javadoc java.util.Collection<E>.

ITERATORS e FOE-EACH LOOP

L'interfacia Collection<T>, definisce un metodo che può essere utilizzato per ottenere un'iteratore per ogni collezione: se coll è una collezione allora coll.iterator() ritorna un iteratore che può essere utilizzato per attraversare la collezione.

L'iteratore è definito da interfaccai parametrica Iterator<T>, che definisce solo tre metodi:

• iter.next()

• iter.hasNext()

• iter.remove()

Esempio:

Iterator<String> iter; // Declare the iterator variable.
iter = coll.iterator(); // Get an iterator for the collection.
while ( iter.hasNext() ) {
    String item = iter.next(); // Get the next item.
    System.out.println(item);
}

Esempio per rimuovere elementi nulli:

Iterator<Color> iter = coll.iterator():
while ( iter.hasNext() ) {
Color item = iter.next();
if (item == null)
    iter.remove();
}

Un iterator è spesso utilizzato per eseguire la stessa operazione su tutti gli elementi di una collezione: in molti casi si può evitare l'utilizzo dell'iterator per questo scopo utilizzando il for-each loop:

for ( T x : coll ) { // for each object x, of type T, in coll
    // process x
}

Esempio:

for ( String name : namelist ) {
    System.out.println( name );
}

Vedi javadoc java.util.Iterator<E>.

Egualianza e comparazione

Ci sono diversi metodi dell'interfaccia Collection che testano gli oggetti al loro interno per l'ugualianza. Per esempio il metodo coll.contains(object) e coll.remove(object) cercano un elemento nella collezione che sia uguale a object.

Se noi scriviamo una nostra classe, noi potremmo voler ridefinire il metodo equals() in quella classe per ottenere il corretto comportamento per quando gli oggetti son conftrontati per l'ugualianza. Pee esempio la classe Card per lavorare correttamente con le collezioni, potrebbe essere definita cosi:

public class Card {  // Class to represent playing cards.
   
   private int suit;  // Number from 0 to 3 that codes for the suit --
                      // spades, diamonds, clubs or hearts.
   private int value; // Number from 1 to 13 that represents the value.
   
   public boolean equals(Object obj) {
       try {
          Card other = (Card)obj;  // Type-cast obj to a Card.
          if (suit == other.suit && value == other.value) {
                // The other card has the same suit and value as
                // this card, so they should be considered equal.
             return true;
          }
          else
             return false;
       }
       catch (Exception e) {
              // This will catch the NullPointerException that occurs if obj
              // is null and the ClassCastException that occurs if obj is
              // not of type Card.  In these cases, obj is not equal to
              // this Card, so return false.
           return false;
       }
    }
   
    .
    . // other methods and constructors
    .
}

Senza il metodo equals() ridefinito nella classe Card, i metodo countains() e remove() dell'interfaccia Collection<Card> non funzionerebbero come ci si aspetterebbe.

Un problema simile si incontra quando bisogna ordinare gli elementi della lista. L'ordinamento concerne nel sistemare gli elementi in ordine crescente (ascendente), rispetto a un certo criterio.

Gli oggetti che devono essere comparati, dovrebbero implementare l'interfaccia java.lang.Comparable. In effetti, Comparable, è definita come un'interfaccia parametrica, Comparable<T>, che rappresenta la capacità di essere paragonato a un oggetto di tipo T. L'interfaccia Comparable<T> definisce un solo metodo:

public int compareTo(T obj)

Il valore ritornato da obj1.compareTo(obj2) deve essere negativo se e sole se obj1 viene prima do obj2, quando gli oggetti sono disposti in ordine crescente. Ritorna un valore positivo se e solo se obj1 è dopo nell'ordinamento di obj2. Ritorna 0 se obj1 e obj2 sono considerati uguali rispetto all'ordinamento.

La classe String implementa l'interfaccia Comparable<String> e definisce il metodo compareTo in modo appropriato.

Se creiamo una nostra classe e vogliamo poter ordinare gli oggetti appartenenti a quella classe, dobbiamo fare la medesima cosa. Per esempio:

/**
 * Represents a full name consisting of a first name and a last name.
 */
public class FullName implements Comparable<FullName> {

   private String firstName, lastName;  // Non-null first and last names.
   
   public FullName(String first, String last) {  // Constructor.
      if (first == null || last == null)
         throw new IllegalArgumentException("Names must be non-null.");
      firstName = first;
      lastName = last;
   }
   
   public boolean equals(Object obj) {
      try {
         FullName other = (FullName)obj;  // Type-cast obj to type FullName
         return firstName.equals(other.firstName) 
                                && lastName.equals(other.lastName);
      }
      catch (Exception e) {
         return false;  // if obj is null or is not of type FullName
      }
   }
   
   public int compareTo( FullName other ) {
      if ( lastName.compareTo(other.lastName) < 0 ) {
             // If lastName comes before the last name of
             // the other object, then this FullName comes
             // before the other FullName.  Return a negative
             // value to indicate this.
         return -1;
      }
      else if ( lastName.compareTo(other.lastName) > 0 ) {
             // If lastName comes after the last name of
             // the other object, then this FullName comes
             // after the other FullName.  Return a positive
             // value to indicate this.
         return 1;
      }
      else {
             // Last names are the same, so base the comparison on
             // the first names, using compareTo from class String.
         return firstName.compareTo(other.firstName);
      }
   }
   
   .
   . // other methods 
   .
}

C'è un altro modo per permettere l'ordinamento degli oggetti in Java, ed è fornire un oggetto separato che è capace di fare la comparazione. Questo oggetto deve implementare Comparator<T>, dove T è il tipo dell'oggetto che deve essere comparato. L'interfaccia Comparator<T> definisce il metodo:

public int compare( T obj1, T obj2)

Il metdo compara due oggetti di tipo T e ritorna un valore che è negativo, positivo o zero, in base al fatto che obj1 venga prima di obj2, dopo di obj2 o assieme a obj2 rispetto all'ordinamento. I Comparator sono utili quando devo ordinare oggetti che non implementano l'interfaccia Comparable o per definire diversi tipi di ordinamento sulla stessa collezione di oggetti.

Vedi javadoc java.lang.Comparable<T> e java.util.Comparator<T>.

Lists e Sets

ArrayList e LinkedList

Tutte le lista implementano metodi dell'interfaccia Collection<T>, questi metodi includono, size(), isEmpty(), add(T), remove(Object) e clear(). Il metdoto add(T) aggiunge un elemento alla fine della lista. Il metodo remove(Object), implica la ricerca il primo oggetto uguale, e dovendo eseguire una ricerca lineare non è molto efficiente: deve scorrere la lista dall'inizio fino a che non trova l'elemento.

L'interfaccia List<T> aggiunge dei metodi per accedere agli elementi della lista in base alla loro posizione numerica all'interno della lista:

• list.get(index)

• list.set(index,obj)

• list.add(index,obj)

• list.remove(index)

• list.indexOf(obj)

Questi metodi nono definiti in entrambe la classi ArrayList<T> e LinkedList<T>, sebbene alcuni di loro, come get e set, sono efficienti sole nel caso dell'ArrayList.

La classe LinkedList<T> aggiunge alcuni metodi, che non sono definiti nell'ArrayList<T>. Se linkedList è un oggetto di tipo LinkedList<T>, possiamo avere:

• linkedlist.getFirst()

• linkedlist.getLast()

• linkedlist.removeFirst()

• linkedlist.removeLast()

• linkedlist.addFirst(obj)

• linkedlist.addLast(obj)

Ci sono delle ridondanza qui, apparentemente per far si che sia semplice utilizzare una LinkedList come se fosse uno stack o una coda. Per esempio, si può utilizzare una LinkedList come uno stack utilizzando i metodi push() e pop() o come una coda utilizzando i metodi add() e remove() per implemenate l'accodamento o il deaccodamento.

Se list è un oggetto di tipo List<T>, allora il metodo list.iterator(), definita nell'interfaccia Collection<T>, ritorna un Iterator, che può essere utilizzata per attraversare la lista dall'inizio alla fine. Inoltre per le List c'è un tipo speciale di iterator chiamato ListIterator, che offre capacità addizionali. ListIterator<T> è un' interfaccia che estende l'interfaccia Iterator<T>.

Il metodo list.listIterator() ritorna un oggetto di tipo ListIterator<T>.

Un ListIterator ha i metodi dell'Iterator quindi hasNext(), next() e remove() ma anche i metodi hasPrevious(), previous(), add(obj) e set(obj) che permettono di muoversi all'indietro nella lista, di aggiungere un elemento nella posizione corrente dell'iterator e rimpiazzare uno degli elementi nella lista.

In questo diagramma, gli elementi della lista son rappresentati dai quadrati e le frecce indicano le possibili posizioni del cursore.

Se iter è una variabile di tipo ListIterator<T>, allora iter.netxt() nuove l'iteratore uno spazio sulla destra lungo la lista e ritorna l'elemento che l'iteratore ha oltrepassato quando si è mosso. Il metodo iter.previous() muove l'iteratore uno spazio sulla sinistra lungo la lista e ritorna l'elemento che ha oltrepassato. Il metodo iter.remove() rimuove un elemento dalla lista; l'elemento che viene rimosso, è l'ultimo che è stato oltrepassato da iter.next() o iter.previous(). Il metodo iter.set(obj) lavora allo stesso modo; rimpiazza l'elemento che sarebbe stato rimosso da iter.remove(). Il metodo iter.add(obj) aggiunge un elemento nella posizione corrente dell'iteratore (dove obj deve essere di tipo T).

ListIterator<String> iter = stringList.listIterator();

// Move the iterator so that it points to the position where
// newItem should be inserted into the list.  If newItem is
// bigger than all the items in the list, then the while loop
// will end when iter.hasNext() becomes false, that is, when
// the iterator has reached the end of the list.

while (iter.hasNext()) {
   String item = iter.next();
   if (newItem.compareTo(item) <= 0) {
         // newItem should come BEFORE item in the list.
         // Move the iterator back one space so that
         // it points to the correct insertion point,
         // and end the loop.
      iter.previous();
      break;
   } 
}

iter.add(newItem);

Vedi javadoc java.util.List<T>, java.util.ArrayList<E>, java.util.LinkedList<E> e java.util.ListIterator<E>.

Sorting

Collections.sort(list);

o anche:

Collections.sort(list,comparator);

Vediamo un esempio con una classe test1.Student e test1.ArrayListSorting per eseguire il sorting:

test1/Student.java

package test1;

public class Student {
	
	private String studentName;
	private int rollNo;
	private int studentAge;

	public Student(int rollNo, String studentName, int studentAge) {
		this.rollNo = rollNo;
		this.studentName = studentName;
		this.studentAge = studentAge;
	}

	public String getStudentName() {
		return studentName;
	}

	public void setStudentName(String studentName) {
		this.studentName = studentName;
	}

	public int getRollNo() {
		return rollNo;
	}

	public void setRollNo(int rollNo) {
		this.rollNo = rollNo;
	}

	public int getStudentAge() {
		return studentAge;
	}

	public void setStudentAge(int studentAge) {
		this.studentAge = studentAge;
	}

	@Override
	public String toString() {
		return "Student [studentName=" + studentName + ", rollNo=" + rollNo + ", studentAge=" + studentAge + "]";
	}
		
}

test1/ArrayListSorting.java

package test1;

import java.util.*;

public class ArrayListSorting  {

     public static void main(String args[]){
	   ArrayList<Student> arraylist = new ArrayList<Student>();
	   arraylist.add(new Student(223, "Marco", 26));
	   arraylist.add(new Student(245, "Luca", 24));
	   arraylist.add(new Student(209, "Antonio", 32));

	   Collections.sort(arraylist);

	   for(Student str: arraylist){
			System.out.println(str);
	   }
     }
}

Eseguendo la compilazione:

D:\PROGETTI\workspace\SortingOnArrayList>javac -cp src src\test1\ArrayListSorting.java
src\test1\ArrayListSorting.java:13: error: no suitable method found for sort(ArrayList<Student>)
           Collections.sort(arraylist);
                      ^
    method Collections.<T#1>sort(List<T#1>) is not applicable
      (inference variable T#1 has incompatible bounds
        equality constraints: Student
        upper bounds: Comparable<? super T#1>)
    method Collections.<T#2>sort(List<T#2>,Comparator<? super T#2>) is not applicable
      (cannot infer type-variable(s) T#2
        (actual and formal argument lists differ in length))
  where T#1,T#2 are type-variables:
    T#1 extends Comparable<? super T#1> declared in method <T#1>sort(List<T#1>)
    T#2 extends Object declared in method <T#2>sort(List<T#2>,Comparator<? super T#2>)
1 error

D:\PROGETTI\workspace\SortingOnArrayList>

Messaggio d'errore criptico che vuol dire che la funzione Collections.sort(arrayList) si aspetta un oggetto di tipo java.util.List contenente oggetti che implementino java.lang.Comparable.

La signature del metodo sort in Collections infatti dice:

static <T extends Comparable<? super T>> void	sort(List<T> list)

Ancora non si può capire tutto (la signature riguardo i tipi parametrici, in questo caso è complessa), ma dice che il tipo generico T (tipo degli oggetti all'interno della collezione) deve estendere java.lang.Comparable.

Correggiamo facendo si che Student implementi Comparable, in cui li ordiniamo in base all'età. Facciamo una nuova versione nel package test2:

test2/Student.java

package test2;

public class Student implements Comparable<Student>{
	private String studentName;
	private int rollNo;
	private int studentAge;

	public Student(int rollNo, String studentName, int studentAge) {
		this.rollNo = rollNo;
		this.studentName = studentName;
		this.studentAge = studentAge;
	}

	public String getStudentName() {
		return studentName;
	}

	public void setStudentName(String studentName) {
		this.studentName = studentName;
	}

	public int getRollNo() {
		return rollNo;
	}

	public void setRollNo(int rollNo) {
		this.rollNo = rollNo;
	}

	public int getStudentAge() {
		return studentAge;
	}

	public void setStudentAge(int studentAge) {
		this.studentAge = studentAge;
	}

	@Override
	public int compareTo(Student o) {
		int compareAge = o.studentAge;
		return this.studentAge - compareAge;
	}
	
	@Override
	public String toString() {
		return "Student [studentName=" + studentName + ", rollNo=" + rollNo + ", studentAge=" + studentAge + "]";
	}
}

Ora anche in test2 aggiungiamo la classe ArrayListSorting , per eseguire il programma che verifichi il sorting.

Eseguendo la compilazione delle classi test2.ArrayListSorting e test2.Student:

D:\PROGETTI\workspace\SortingOnArrayList>javac -cp src src\test2\ArrayListSorting.java

D:\PROGETTI\workspace\SortingOnArrayList>

Ora la compilazione viene eseguite correttamente.

Eseguendo il programma test2.ArrayListSorting si verifica che il contenuto dell'ArrayList<Student> viene ordinato correttamente in base all'età:

Student [studentName=Luca, rollNo=245, studentAge=24]
Student [studentName=Marco, rollNo=223, studentAge=26]
Student [studentName=Antonio, rollNo=209, studentAge=32]

Ora se volessimo ordinare la collezione di Student in base alla proprietà rollNo o in base allo studentName?

Possiamo implementare due differenti java.util.Comparator<Student> uno che ordini in base al rollNo e uno in base a studentName:

test3/Student.java

package test3;

import java.util.Comparator;

public class Student {

	private String studentName;
	private int rollNo;
	private int studentAge;

	/* Comparator for sorting the list by Student Name */
	public static Comparator<Student> StuNameComparator = new Comparator<Student>() {

		public int compare(Student s1, Student s2) {
			String studentName1 = s1.getStudentName().toUpperCase();
			String studentName2 = s2.getStudentName().toUpperCase();

			// ascending order
			return studentName1.compareTo(studentName2);

			// descending order
			// return StudentName2.compareTo(StudentName1);
		}
	};

	/* Comparator for sorting the list by roll no */
	public static Comparator<Student> StuRollno = new Comparator<Student>() {

		public int compare(Student s1, Student s2) {

			int rollno1 = s1.getRollNo();
			int rollno2 = s2.getRollNo();

			/* For ascending order */
			return rollno1 - rollno2;

			/* For descending order */
			// rollno2-rollno1;
		}
	};

	public Student(int rollNo, String studentName, int studentAge) {
		this.rollNo = rollNo;
		this.studentName = studentName;
		this.studentAge = studentAge;
	}

	public String getStudentName() {
		return studentName;
	}

	public void setStudentName(String studentName) {
		this.studentName = studentName;
	}

	public int getRollNo() {
		return rollNo;
	}

	public void setRollNo(int rollNo) {
		this.rollNo = rollNo;
	}

	public int getStudentAge() {
		return studentAge;
	}

	public void setStudentAge(int studentAge) {
		this.studentAge = studentAge;
	}

	@Override
	public String toString() {
		return "Student [studentName=" + studentName + ", rollNo=" + rollNo + ", studentAge=" + studentAge + "]";
	}
}

Nel codice sopra: i due oggetti che implementano Comparator sono creati tramite anonymous inner class. Una comodità, non sarebbe cambiato nulla se si creavano due ulteriori classi, esterne, che implementavano java.util.Comparator e le si utilizzavano per istanziare i due diversi oggetti di tipo comparator.

test3/ArrayListSorting.java

package test3;

import java.util.*;

public class ArrayListSorting  {

     public static void main(String args[]){
	   ArrayList<Student> arraylist = new ArrayList<Student>();
	   arraylist.add(new Student(223, "Marco", 26));
	   arraylist.add(new Student(245, "Luca", 24));
	   arraylist.add(new Student(209, "Antonio", 32));
	   
	   System.out.println("---- ORDINAMENTO PER NOME STUDENTE:");
	   Collections.sort(arraylist, Student.StuNameComparator);

	   for(Student str: arraylist){
			System.out.println(str);
	   }
	   
	   System.out.println("---- ORDINAMENTO PER ROLL NUM:");
	   Collections.sort(arraylist, Student.StuRollno);

	   for(Student str: arraylist){
			System.out.println(str);
	   }
     }
}

L'output dell'esecuzione del programma test3.ArrayListSorting:

---- ORDINAMENTO PER NOME STUDENTE:
Student [studentName=Antonio, rollNo=209, studentAge=32]
Student [studentName=Luca, rollNo=245, studentAge=24]
Student [studentName=Marco, rollNo=223, studentAge=26]
---- ORDINAMENTO PER ROLL NUM:
Student [studentName=Antonio, rollNo=209, studentAge=32]
Student [studentName=Marco, rollNo=223, studentAge=26]
Student [studentName=Luca, rollNo=245, studentAge=24]

La classe Collections ha anche i metodi statici Collections.shuffle(list) per mischiare in modo casuale gli elementi di un oggetto di tipo List<T> e Collections.reverse(list) per invertire gli ordini della lista.

Vedi javadoc java.util.Collections.

TreeSet e HashSet

L'interfaccia Set<E> rappresenta una collezione che non contiene duplicati.

Le classi che implementano l'interfaccia Set<E> sono TreeSet<E> e HashSet<E>.

HashSet è implementata internamente con una struttura dati di tipo hash table, quindi non mantiene nessun ordine nè di ordine di inserimento nè di ordine in base a un criterio di ordinamento.

Mentre TreeSet<E> è implementato con una struttura ad albero, che mantiene un ordine in base a un criterio: gli oggetti contenuti nel TreeSet devono implementare java.lang.Comparable<T> o al costruttore del TreeSet è passato un oggetto di tipo java.util.Comparator<T>.

TreeSet<String> words = new TreeSet<String>();

while there is more data in the input file:
   Let word = the next word from the file
   Convert word to lower case
   words.add(word)   // Adds the word only if not already present.

for ( String w : words ) // for each String w in words
   Output w  // words are output in sorted order

TreeSet<String> set = new TreeSet<String>();
set.addAll(coll);

TreeSet<String> set = new TreeSet<String>();
set.addAll(coll);
ArrayList<String> list = new ArrayList<String>();
list.addAll(set);

ArrayList<String> list = new ArrayList<String>( new TreeSet<String>(coll) );

Vedi javadoc java.util.Set<E>, java.util.HashSet<E> e java.util.TreeSet<E>.

Maps

Supponiamo che map è una variabile di tipo Map<K,V> per alcuni specifci tipi K e V. Questi sono alcuni dei metodi che sono definiti per map:

• map.get(key)

• map.put(key,value)

• map.putAll(map2)

• map.remove(key)

• map.containsKey(key)

• map.containsValue(value)

• map.size()

• map.isEmpty()

• map.clear()

Java include due classi the implementano l'interfaccia Map<K,V>: TreeMap<K, V> e HashMap<K,V>.

Vedi Esempio liste associative l'esempio sotto il package withMap in cui viene utilizzata una struttura di tipo HashMap<String, String> per associare nome persona e numero di telefono (memorizzato come stringa).

Vedi anche esempio sotto package addresslist in cui nella classe addresslist.AddressDirectory viene tenuta l'associazione tra oggetti di tipo Customer e tipo Address , tramite una HashMap<Customer, Address>. Le classi Customer e Address contengono i dati rispettivamente del cliente (nome, cognome) e il suo indirizzo (via, città, CAP).

Vedi javadoc java.util.Map<K, V>, java.util.HashMap<K, V> e java.util.TreeMap<K, V>.

E' possibile iterare sugli elementi della lista, sia sulle chiavi che sui valori, tramite delle viste.

Viste

map.keySet()

ritorna Set<K>, il set delle chiavi, non ci possono essere duplicati.

Avendo una collezione di tipo Map<String, Double>, possiamo ad esempio:

Set<String> keys = map.keySet();     // The set of keys in the map.
Iterator<String> keyIter = keys.iterator();
System.out.println("The map contains the following associations:");
while (keyIter.hasNext()) {
   String key = keyIter.next();  // Get the next key.
   Double value = map.get(key);  // Get the value for that key.
   System.out.println( "   (" + key + "," + value + ")" );
}

o più semplicemente senza dal set otterenere l'iteratore, così:

System.out.println("The map contains the following associations:");
for ( String key : map.keySet() ) {  // "for each key in the map's key set"
    Double value = map.get(key);
    System.out.println( "   (" + key + "," + value + ")" );
}

Se la map è una TreeMap, allora il key set della map, è un sorted set, e l'iteratore visiterà le chiavi in ordine ascendente. Per l'HashMap, le chiavi sono visitate in un ordine indefinito, non predicibile.

Mentre il metodo:

map.values()

rirorna un oggetto Collection<V>, la collezione dei valori contenuti nella mappa. E' una collezione e non un Set, come per le chiavi, perchè tra i valori ci possono essere dei duplicati.

Il metodo:

map.entrySet()

ritorna un set che contiene tutte le associazioni dalla mappa. Gli elementi del set sono oggetti del tipo Map.Entry<K, V>. Il tipo di ritorno di map.entrySet() è scritto Set<Map.Entry<K, V>>.

Set<Map.Entry<String, Double>> entries = map.entrySet();
Iterator<Map.Entry<String, Double>> entryIter = entries.iterator();
System.out.println("The map contains the following associations:");
while (entryIter.hasNext()) {
   Map.Entry<String, Double> entry = entryIter.next();
   String key = entry.getKey();  // Get the key from the entry.
   Double value = entry.getValue();  // Get the value.
   System.out.println( "   (" + key + "," + value + ")" );
}

o, utilizzando il for-each loop:

System.out.println("The map contains the following associations:");
for ( Map.Entry<String, Double> entry : map.entrySet() ) {
   System.out.println( "   (" + entry.getKey() + "," + entry.getValue() + ")" );
}

Hash table e Hash code

HashSet e HashMap sono implementati con la struttura chiamata hash table. Vedi spiegazione su implementazione hash table quando abbiamo trattato gli array associativi. Vedi figura struttura hash table: